0

Here is the thing. I solved kata on Codewars with task: Find number of carries.

I solved this task trivially. I reversed both numbers and sum each digit one by one. I accumulate sum / 10 (integer division). I increase counter each time when accumulator isn't equal 0. My solution is 41 lines-long. I submitted my solution and I founded another solution and I don't understand how to works! I tried it on paper all works! Please explain it to me.

The smart solution

  1. sum_a = sum of digits for first number
  2. sum_b = sum of digits for second number
  3. sum_sum = sum of digits for sum of numbers
  4. (sum_a + sum_b - sum_sum) / 9(integer division)

examples:

### first
sum(543) = 12
sum(3456) = 18

543 + 3456 = 3999
sum(3999) = 30


(12 + 18 - 30) => 0/9 = 0 right!


second


sum(1927) = 19
sum(6426) = 18


1927 + 6426 = 8153
sum(8153) = 17


(19 + 18 - 17) => 20/9 = 2 right!
Thomas Andrews
  • 177,126
Ian Kirsh
  • 1
  • You should start with the formal definition of the question, or at the very least, a link to the external problem. It only became clear what you are asking in the examples. – Thomas Andrews Sep 06 '21 at 17:28
  • How can the definition be better in your opinion? @ThomasAndrews Sorry, I fixed it! – Ian Kirsh Sep 06 '21 at 17:31
  • “Find number of carries” is vague, at best. Be specific. “When doing addition of two numbers base $10$ using the standard technique…” There is nothing implicit in addition about carries. Rather, it is peculiar to the algorithm we apply to the process of addition given a certain notation for numbers. – Thomas Andrews Sep 06 '21 at 17:32
  • Okay, thank you @ThomasAndrews for the answer! – Ian Kirsh Sep 06 '21 at 17:39

1 Answers1

1

If you didn’t do any carries, then you’d get $$1927+6426=7(13)4(13)$$

and $$7+13+4+13=(1+9+2+7)+(6+4+2+6)$$

But each time we do a carry, in the left we reduce one term on the left by $10$ and one term is increased by $1.$ So we get $9$ reduction in terms with each carry.

The tricky part is you need to consider the cases when a carry in turn causes a carry.

For example: $56+47=103.$

We start with $9(13)=56+47,$ and $9+13=(5+6)+(4+7),$ with one carry to get to $(10)+3.$ This reduces the sum by $9,$ but we need to do one more carry to get $103.$ That reduces the digit sum again by $9.$

It takes an inductive argument to prove this result, and technically it requires a full definition of the algorithm of addition.

For the sum of three numbers. In the sum of the two integers, we can only carry $1$ per carry. But when summing $19+29+59=107,$ there are two carries, one of $1,$ the other of $2.$

This works more general, for sums $k$. When $k\geq 11,$ it depends on how you count a “carry” when you get a digit sum plus carry $\geq 100.$

Thomas Andrews
  • 177,126