Tuesday, September 20, 2011

Sum of the Digits

A simple puzzle to share with today...

Write a program to find sum of all integers of a given number such that sum is always a single digit.
For instance if the given number is 6789, then answer should be 6+7+8+9 = 30 and then 3+0 =3.

A straight forward logic is to write a recursive function which calculates sum of digits until the it is less than 10. But there an efficient logic than this. Here is that

1. Calculate mod(input_integer,9)
2. if the result is 0 then
       sum of digits reduced to single digit is 9
   else
      value returned in step 1 is the sum of digits of input integer reduced to 9.

Here is my oracle SQL solution,

SELECT DECODE(MOD(INPUT_INTEGER,9),0,9,MOD(INPUT_INTEGER,9))
   FROM DUAL;       

Wednesday, September 14, 2011

Is 100!/(50! x 2^50) an integer?


I just read this puzzle somewhere and realized that this is similar to my earlier post How many zeros does 1000! end with?

Here is the solution to this puzzle,

There is no doubt that 100!/50! is an integer. Hence we just need to find whether 100 x 99 x 98 x ... x 51 will be divisible by 2^50 or not. The mathematical theorem discussed in my earlier post helps us to solve this puzzle as well
let us find the exponents of 2 in 100!
   [100/2] + [100/2^2 ] + [100/2^3 ] + [100/2^4 ] + [100/2^5 ] + [100/2^6 ]
      = 50 + 25 + 12 + 6 +3+1 = 97
Therefore 100! is multiples of 2^97
let us find the exponents of 2 in 50!
    [50/2] + [50/2^2 ] + [50/2^3 ] + [50/2^4 ] + [50/2^5 ]
       = 25 + 12 + 6 +3+1 = 47
Therefore 50! is multiples of 2^47

From the above it is evident that 100! / 50! is multiples of 2^50. Hence 100!/(50! x 2^50) is an integer