## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
0
of 2 vote

We can do it with all additions. For e.g. 5! can be calculated like. Add 5 four times and now the result is added 3 times and so on.

Comment hidden because of low score. Click to expand.
0

huh you are right..
ok let me rephrase the question: compute a factorial in the most efficient way (with the minimum no of arithmetic ops).
i.e. can we reduce the # of multiplications ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Count the powers of 2 that will be included in the factorial, and use a right shift for those. Something like:

for (m = n>>1, powers_of_two = m; m; m >>= 1, powers_of_two += m);
result = 1<<powers_of_two;
for (; n>1; n--) { if (!is_power_of_two(n)) result *= n; }

That said, 13! is already larger than 2^32, so normal arithmetic isn't really practical here.

Comment hidden because of low score. Click to expand.
0
of 0 vote

you can do factorial of n in log2(n) time.
say for 6, you shall do like this.
((1 * 2) * 3) * ((4 * 5) * 6).. its a balanced binary tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Abhishek ,
There is no improvement in no.of arthimetic operations .still it requires n-1 multiplications

Comment hidden because of low score. Click to expand.
0

Abhishek is actually right: this technique is called "binary splitting": imagine if you wish to compute factorial of a large number, then performing arithmetic on balanced operands (ie of comparable size) is more efficient than computing x! in a usual way

also to give a hint how to reduce the # of muls, observe that we can remove the power-of-two factors from the factorial expression and combine the remaining ones according to multiplicity:

e.g.: 10! = 2^8 * ( 1 * 3 * 1 * 5 * 3 * 7 * 1 * 9 * 5) =
2^8 * (3 * 5)^2 * 7 * 9

hence we need to perform 4 multiplications instead of 8..

Comment hidden because of low score. Click to expand.
0
of 0 vote

It's fast, example in C#2010:
bigintegers.blogspot.nl/2011/12/factorial-by-binary-splitting-part2.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution would be:

1.) use an array or hashtable or tree with the prime number + count.
2.) each number of n! can be represented by prime numbers so add count the prime numbers used in 1.
3.) iterate from the structure in 1.) and multiply
3.1) here you can optimize a little - shift left when there is multiplication of 2 instead of multiply

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.