Bloomberg LP Interview Question
Financial Software DevelopersFirst find the factors of N (36)
Then iterate through the factors
for (i = factor1; i != null; i = i->nextfactor)
for (j = i->nextfactor; j != null; j = j->nextfactor)
for (k = j->nextfactor; k != null; k = k->nextfactor)
if (i * j * k == N)
answer.
The code above produces too much repitition. Here is a better way
for (i=1,2,3) // factors of 36 up to cube root of 36
for (j in factors of 36/i up to sqrt(36/i)
print (i,j,36/(i*j)
This will produce all the triples in non-decreasing order. Can be easily generalized to other numbers and number-of-factors.
Neat!
One improvement: Check for duplicate printing. That is, combination 1, 1, 36 should be considered same as 1, 36, 1.
The unique key could be as simple as i+j+k.
Create an array check of size [36*3] and use it like a bit vector.
One more improvement to code by Anonymous,
j has to be a factor of (36/i) and k has to be of (36/i*j)
so if loops of internal for loops can be changed,
-----------
for(i=1;i<=36;i++)
{
//if i is a factor of 36
if(36%i==0)
{
for(j=1;j<=36;j++)
//if j is a factor of 36
if((36/i)%j == 0)
{
for(k=1;k<=36;k++)
//if k is a factor of 36
if((36/i*j)%k==0)
{
if(i*j*k == 36)
print(i,j,k)
}
}
}
}
}
---------------
I think the solution by Anonymous is nice; nevertheless, the solution provided by John Smith is much better.
It is O(N^2) and not O(N^3) and the code is neat and easily extensible, as he said. Just play with n^th roots in descending order.
Only a small caveat: the second loop should exclude (i) itself. Suppose i =1, j would go from 1 to 36/1 (36), so the code would also produce 1,1,36 which has a repetition. The same problem arises for the combination (3,3,4) which is permitted by the code
(i=3, j>36/3 and j<sqrt(12) therefore j=3 is permitted)
For generalization any loop has to exclude the precedent indexes; anyhow really great solution, I enjoyed it. Thanks, John
The Thing to note here is that not only that we should not allow duplicate combinations like [2,3,6] and [3,6,2] , but also combos like [1,1,36] are not allowed as said in the question.
My logic goes like this:-
1) Find out all the divisors say 'i' of 36 less than the sqrt of 36 i.e. 6
2) Now , for each 'i', compute 'j' and 'k' such that i*j*k=36 and all are distinct
We can find out 'j' too in a similar fashion as 'i' i.e. divisors of 36 less than it's square root.
Following this fashion, we would end up getting i,j and k in the increasing order and it would avoid duplicates as we are considering divisors only upto the square root.
So ultimately we get the age combos as follows:-
1 2 18
1 3 12
1 4 9
2 3 6
1,1,36
1,2,18
1,3,12
1,4,9
1,6,6
2,2,9
2,3,6
2,6,3
Only these age combo are unique, and this set is what interviewer is looking for.
#1 (1, 1, 36)
#2 (1, 2, 18)
#3 (1, 3, 12)
#4 (1, 4, 9)
#5 (1, 6, 6)
#6 (2, 2, 9)
#7 (2, 3, 6)
#8 (3, 3, 4)
Is there a mathematical way to do this?
Its the product and not the sum that should be 36
- Anonymous November 19, 2009for(i=1;i<=36;i++)
{
//if i is a factor of 36
if(36%i==0)
{
for(j=1;j<=36;j++)
//if j is a factor of 36
if(36%j == 0)
{
for(k=1;k<=36;k++)
//if k is a factor of 36
if(36%k==0)
{
if(i*j*k == 36)
print(i,j,k)
}
}
}
}