Use only '+' operator

Computer Science Level 4

3 × 4 = 3 + 3 + 3 + 3 = 4 + 4 + 4 3 \times 4 = 3+3+3+3=4+4+4 n ! = n × ( n − 1 ) × ( n − 2 ) × ⋯ × 3 × 2 × 1 n!=n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1

Finding the factorial of any natural number is just finding the product of first n n natural numbers, moreover product of two positive numbers m m and n n is just the summation of m m n ′ s n's or n n m ′ s m's . Therefore the factorial of a number can also be calculated using only the addition operator.

For example:

0 ! = 1 0!=1 (No addition)

1 ! = 1 1!=1 (No addition)

2 ! = 2 2!=2 (No addition)

3 ! = 3 × 2 ! 3!=3 \times 2! OR 3 ! = 2 ! + 2 ! + 2 ! 3!=2!+2!+2! (2 additions)

4 ! = 4 × 3 ! 4!=4 \times 3! OR 4 ! = 3 ! + 3 ! + 3 ! + 3 ! 4!=3!+3!+3!+3! (How many addition here? Do you see a pattern?)

What is the minimum number of additions that you need to perform to find the factorial of 10 10 when you are allowed to use only (+) operation ? ( Hint: Generalize it for the factorial of any non-negative integer N N )


The answer is 44.

Zeeshan Ali by Zeeshan Ali , 25, Pakistan

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Zeeshan Ali
Mar 5, 2016

0 ! = 1 0!=1 (No addition)

1 ! = 1 1!=1 (No addition)

2 ! = 2 2!=2 (No addition)

3 ! = 3 × 2 ! = ( 2 ! ) + ( 2 ! ) + ( 2 ! ) 3!=3 \times 2! = (2!)+(2!)+(2!) (2 additions)

4 ! = 4 × 3 ! = ( 3 ! ) + ( 3 ! ) + ( 3 ! ) + ( 3 ! ) 4!=4 \times 3! = (3!)+(3!)+(3!)+(3!) (2+4-1=5 additions)

5 ! = 5 × 4 ! = ( 4 ! ) + ( 4 ! ) + ( 4 ! ) + ( 4 ! ) + ( 4 ! ) 5!=5 \times 4! = (4!)+(4!)+(4!)+(4!)+(4!) (5+5-1=9 additions)

6 ! = 6 × 5 ! = ( 5 ! ) + ( 5 ! ) + ( 5 ! ) + ( 5 ! ) + ( 5 ! ) + ( 5 ! ) 6!=6 \times 5! = (5!)+(5!)+(5!)+(5!)+(5!)+(5!) (9+6-1=14 additions)

7 ! = 7 × 6 ! = ( 6 ! ) + ( 6 ! ) + ( 6 ! ) + ( 6 ! ) + ( 6 ! ) + ( 6 ! ) + ( 6 ! ) 7!=7 \times 6! = (6!)+(6!)+(6!)+(6!)+(6!)+(6!)+(6!) (14+7-1=20 additions)

8 ! = 8 × 7 ! = ( 7 ! ) + ( 7 ! ) + ( 7 ! ) + ( 7 ! ) + ( 7 ! ) + ( 7 ! ) + ( 7 ! ) + ( 7 ! ) 8!=8 \times 7! = (7!)+(7!)+(7!)+(7!)+(7!)+(7!)+(7!)+(7!) (20+8-1=27 additions)

9 ! = 9 × 8 ! = ( 8 ! ) + ( 8 ! ) + ( 8 ! ) + ( 8 ! ) + ( 8 ! ) + ( 8 ! ) + ( 8 ! ) + ( 8 ! ) + ( 8 ! ) 9!=9 \times 8! = (8!)+(8!)+(8!)+(8!)+(8!)+(8!)+(8!)+(8!)+(8!) (27+9-1=35 additions)

10 ! = ( 9 ! ) + ( 9 ! ) + ( 9 ! ) + ( 9 ! ) + ( 9 ! ) + ( 9 ! ) + ( 9 ! ) + ( 9 ! ) + ( 9 ! ) + ( 9 ! ) 10! = (9!)+(9!)+(9!)+(9!)+(9!)+(9!)+(9!)+(9!)+(9!)+(9!) (35+10-1=44 additions)

Generally, if there are N N number of additions performed to find ( n − 1 ) ! (n-1)! then n ! n! can be found by performing N + n − 1 N+n-1 number of additions such that the base cases are 0 ! 0! , 1 ! 1! and 2 ! 2! that require no addition.

You can recursively find out the number of additions performed using the function: 

1
2
3
4
5
 
int N(int num){
    if(num==0 || num==1 || num==2)
        return 0;
    return N(num-1)+num-1;
}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...