Friday, November 9, 2012

Sum of Digits until it becomes a single digit


You are given a huge number and the task is to add the number till it becomes a single digit.
E.g.
Number = 9580658690133945975556610984511994659
 9+5+8+0+6+5+8+6+9+0+1+3+3+9+4+5+9+7+5+5+5+6+6+1+0+9+8+4+5+1+1+9+9+4+6+5+9     =195
  1+9+5 =  15
  1+5 = 6
  Result = 6
 
  Wait!! Can I do it in one pass?? Yes O(N) solution
  Add the values. If sum is divisible by 9, result is 9.
  Else result is (sum mod 9). In the above case, after the first pass the result is 195. Hence 195%9 = 6, the   desired answer.

Solution

No comments:

Post a Comment

UA-36403895-1