Linkedin Interview Question
Software DevelopersCountry: United States
Try my idea, using Java:
Ex: INPUT: 100
OUTPUT:
50*2
25*4
25*2*2
20*5
10*10
10*5*2
5*5*4
5*5*2*2
CODE:
public class PrintFactors {
public static void main(String[] args) {
printFactor(100);
}
private static void printFactor(int n) {
if (n <= 0) {
System.out.print("Wrong input!");
return;
}
if (n == 1) {
System.out.print("1");
return;
}
long[] a = new long[n/2];
findFactor(n/2, n, a, 0);
}
private static void findFactor(long i, long n, long[] arr, int index) {
if (i == 1) {
if (n == 1) {
for (int k = 0; k < index - 1; k++) {
System.out.print(arr[k]);
if (k < index - 2) {
System.out.print("*");
}
}
System.out.println();
}
return;
}
for (long k = i; k >= 1; k--) {
if (n % k == 0) {
arr[index] = k;
findFactor(k, n / k, arr, index + 1);
}
}
}
}
#!/usr/bin/env python
def breakDown(number):
if not isPrime(number):
for i in [2,3,5,7]:
if number%i==0:
val.append(i)
return breakDown(number/i)
else:
val.append(number)
return
def isPrime(Number):
return 2 in [Number,2**Number%Number]
input = input("Enter Number:")
print 1,'*',input
numberSet = []
for i in range(2,input/2):
if input%i == 0:
arr = []
arr.append(i)
arr.append(input/i)
arr.sort()
if arr not in numberSet:
print ' * '.join(str(x) for x in arr)
numberSet.append(arr)
num = input/i
if num not in [1,2,3,5,7]:
val = []
breakDown(num)
val.append(i)
val.sort()
if val not in numberSet:
print ' * '.join(str(x) for x in val)
numberSet.append(val)
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
void print_prod(vector<int>& A, int target, int pos, int prod, vector<int>& temp, vector<vector<int> >& ans) {
if (prod > target) {
return;
}
if (pos > A.size() - 1) {
return;
}
if (prod == target) {
ans.push_back(temp);
for (int i = 0; i < temp.size(); ++i) {
cout << temp[i] << " ";
}
cout << "" << endl;
}
for (int i = pos; i < A.size(); ++i) {
temp.push_back(A[i]);
prod = prod * A[i];
print_prod(A, target, i, prod, temp, ans);
prod = prod / A[i];
temp.pop_back();
}
}
int main() {
int target = 12; // Modify this for different inputs.
vector<int> factors;
// Find all factors of target;
int square = sqrt(target);
for (int i = 2; i <= square; ++i) {
if (target % i == 0) {
factors.push_back(i);
}
if (i * i != target) {
factors.push_back(target / i);
}
}
// Sort the factors vect
sort(factors.begin(), factors.end());
vector<vector<int> > ans;
vector<int> temp;
// Add 1 and target as one of the ans set. As 1 * target is one of the answers.
// We cannot use it in the recursive call above as 1 * 1 * 1 will never terminate.
temp.push_back(1);
temp.push_back(target);
ans.push_back(temp);
cout << temp[0] << " " << temp[1] << endl;
temp.clear();
print_prod(factors, target, 0, 1, temp, ans);
return 0;
}
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
void print_prod(vector<int>& A, int target, int pos, int prod, vector<int>& temp, vector<vector<int> >& ans) {
if (prod > target) {
return;
}
if (pos > A.size() - 1) {
return;
}
if (prod == target) {
ans.push_back(temp);
for (int i = 0; i < temp.size(); ++i) {
cout << temp[i] << " ";
}
cout << "" << endl;
}
for (int i = pos; i < A.size(); ++i) {
temp.push_back(A[i]);
prod = prod * A[i];
print_prod(A, target, i, prod, temp, ans);
prod = prod / A[i];
temp.pop_back();
}
}
int main() {
int target = 12; // Modify this for different inputs.
vector<int> factors;
// Find all factors of target;
int square = sqrt(target);
for (int i = 2; i <= square; ++i) {
if (target % i == 0) {
factors.push_back(i);
}
if (i * i != target) {
factors.push_back(target / i);
}
}
// Sort the factors vect
sort(factors.begin(), factors.end());
vector<vector<int> > ans;
vector<int> temp;
// Add 1 and target as one of the ans set. As 1 * target is one of the answers.
// We cannot use it in the recursive call above as 1 * 1 * 1 will never terminate.
temp.push_back(1);
temp.push_back(target);
ans.push_back(temp);
cout << temp[0] << " " << temp[1] << endl;
temp.clear();
print_prod(factors, target, 0, 1, temp, ans);
return 0;
}
void print_factors(int num) {
// O(n) time, O(n) space;
bool *solved = new bool[num/2];
for (int i = 0; i < num/2; ++i)
solved[i] = false;
for (int i = 1; i < num / 2; ++i) {
if (num % i == 0) {
if (!solved[i]) {
std::cout << i << " * " << num / i << std::endl;
solved[i] = true;
solved[num/i] = true;
}
}
}
}
# Idea :
# use recursion to print the smaller factors
# pass the partial result to recursion
import math
def print_factors(n):
if n <= 1:
return
print n,"*",1 # special case
print_factors_util("", n, n)
def print_factors_util(res, n, pfact):
for fact in range(n-1, 1, -1):
if n % fact == 0 and fact < pfact:
nfact = n/fact
if fact >= nfact:
print res, fact, "*", nfact
print_factors_util(res + " " + str(fact) + " *", nfact, fact)
import math
def print_factors(n):
if n <= 1:
return
print n,"*",1 # special case
#print_factors_util("", n, n)
res = [0 for _ in range(n)]
print_factors_util2(res, n, n, 0)
def print_factors_util(res, n, pfact):
for fact in range(n-1, 1, -1):
if n % fact == 0 and fact < pfact:
nfact = n/fact
if fact >= nfact:
print res, fact, "*", nfact
print_factors_util(res + " " + str(fact) + " *", nfact, fact)
My solution in python:
{
from math import sqrt
from itertools import product
from operator import mul
from collections import Counter
def prime_factor(n):
if n == 1:
return [n]
up_bound = int(sqrt(n))
for i in xrange(2, up_bound + 1):
if n % i == 0:
return [i] + prime_factor(n // i)
return [n]
def print_factor(n):
factors = prime_factor(n)
decompositions = [factors]
f_count = Counter(factors)
factors, powers = f_count.keys(), f_count.values()
for multiplicities in product(*[range(i+1) for i in powers]):
if sum(multiplicities) <= 1:
continue
p = reduce(mul, [k**i for k, i in zip(factors, multiplicities)])
elems = [p]
for i, kv in enumerate(zip(factors, powers)):
k, v = kv
m = multiplicities[i]
elems += [k]*(v-m)
decompositions.append(elems)
for lst in decompositions:
print ' * '.join(str(factor) for factor in lst)
if __name__ == '__main__':
print_factor(400)
}
int MultiplyStack(std::stack<int> multipliers)
{
int result = 1;
while (multipliers.size() > 0)
{
result *= multipliers.top();
multipliers.pop();
}
return result;
}
void FindFactor(std::stack<int> multipliers, int number)
{
for (int i = 2; i <= (number / 2); i++)
{
multipliers.push(i);
int stack_result = MultiplyStack(multipliers);
if (stack_result == number)
{
// So here we could use a vector of hashtables to make sure this
// combination has nor repeated with a different order.
PrintStack(multipliers);
return;
}
if (stack_result > number)
{
return;
}
FindFactor(multipliers, number);
multipliers.pop();
}
}
int main()
{
int number = 12;
std::stack<int> multipliers;
FindFactor(multipliers, number);
return 0;
}
package com.test;
import java.util.*;
import java.util.function.Predicate;
class Main {
static int factors[];
static HashSet<String> ans;
public static void main(String[] args) {
int n = 36;
ans = new HashSet<>();
ans.add(1+"*"+n);
factors =getAllFactors(n);
for(int x: factors){
System.out.print(x+" ");
}
System.out.println();
printMultipliers(factors.length-1, n, "");
for(String exp: ans){
System.out.println(exp);
}
}
public static void printMultipliers(int i, int n, String exp){
if(i<0)return;
if(n==1){
ans.add(exp);
return;
}
if(exp==""){
if(n%factors[i]==0){
printMultipliers(i-1, n/factors[i], factors[i]+"");
printMultipliers(i, n/factors[i], factors[i]+"");
printMultipliers(i-1, n, exp);
}else {
printMultipliers(i-1, n, exp);
}
}else{
if(n%factors[i]==0){
printMultipliers(i-1, n/factors[i], exp+"*"+factors[i]);
printMultipliers(i, n/factors[i], exp+"*"+factors[i]);
printMultipliers(i-1, n, exp);
}else {
printMultipliers(i-1, n, exp);
}
}
}
public static int[] getAllFactors(int n){
ArrayList<Integer> res = new ArrayList<>();
for(int i=2;i<=Math.sqrt(n);i++){
if(n%i==0){
res.add(i);
if(n/i!=i){
res.add(n/i);
}
}
}
int ans[] = new int[res.size()];
for(int i=0;i< res.size();i++){
ans[i] = res.get(i);
}
return ans;
}
}
public void printMultiNumbers(int input) {
for (int i = 1; i <= input / 2; i++) {
if (input % i == 0) {
if (!dataSet.containsKey(input / i + "*" + i)
&& !dataSet.containsKey(i + "*" + input / i)) {
dataSet.put(i + "*" + input / i, i + "*" + input / i);
}
}
}
for (String combination : dataSet.keySet()) {
System.out.println(combination);
}
}
Try my code:
- techinterviewquestion.com June 08, 2016