A mathematical method for knowing how many carrys in a sum

Question

I saw today on URI (website programming problems) a question in which your program should read two values and say how many carrys (or "will one"s) happen in the sum of them. Ex: 555 + 555 = 3 carrys and 1 + 9999999 = 7 carrys.

I made a program to manually calculate, like a human being, first I matched the number of decimal places using a for and then I did the manual sum. Ex: 12 999999 = 000012 999999 and then the sum was made. But one person said that there was a way to answer this much more efficiently and I would like to know what it looks like, I googled but I couldn’t find it anywhere, I believe it’s similar to finding out how many zeros there are in a factorial number(Determine factor zeros).

Answer 1

I did not understand 100% the mathematical solution of Leo, maybe it is the same that I will show here. I found on the site Math Overflow a discussion indicating a relationship between the number of Carries and the sums of digits of each operand and the result. This formula is quoted:

S_b represents a sum of digits in the base b; to and c are the addition operands, and k is the number of Carries. Rearranging the formula to isolate k, and considering you’re working at base 10, we’ll have:

A C implementation, as an example:

#include <stdio.h>

int main(void) {
    int teste1 = carries(9, 1);
    int teste2 = carries(99, 1);
    int teste3 = carries(999, 1);
    int teste4 = carries(999, 10);

    printf("9+1: %i carries\n", teste1);
    printf("99+1: %i carries\n", teste2);
    printf("999+1: %i carries\n", teste3);
    printf("999+10: %i carries\n", teste4);

    return 0;
}

int carries(int a, int b) {
    return (sumDigits(a) + sumDigits(b) - sumDigits(a+b)) / 9;
}

int sumDigits(int num) {
    int sum = 0;
    while (num != 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

http://ideone.com/P8OZ5t

Answer 2

Attention, I may have misinterpreted the question and this solution may not present Carrys by mathematical method.

The mathematical solution that you want and that I developed (I don’t know if anyone has done this before, because I am an engineer and not a mathematician, if someone has a reference, please inform in the comments, that I make a point to analyze and quote here in this answer) is this:

Below is an example with the formulas of the cells shown beside (in this example, the column is "I" and the initial data line is 13)

How the calculations work:

First it is necessary to calculate the number number number number to be analyzed, this is done by means of the whole part of the result of the base logarithm 10 of that number plus one.

The base logarithm 10 for values like 10, 100 and 1000 only returns integers, respectively 1, 2 and 3 in this example (their respective powers).

Thus, an integer value that is between 10 3 (1000) and 10 4 (10000), will have the result of its base logarithm 10 between 3 and 4, never 3 (would be 1000) or 4 (would be 10000).

Thus, above 1000 (which has four digits, equal to its power plus one) and below 10000 (which has five digits, equal to its power plus one), all integers in this range must have four digits, and the result of their logarithms will always be greater than 3 and smaller than 4.

Therefore, taking the entire part of this calculation and adding one, we obtain the number of digits of the analyzed integer.

To be a Carry, all digits must be equal, so by obtaining the first digit of this number we can generate a Carry with it (of same digit numbers of the original value) and compare if they are equal.

Taking the entire part of the result of dividing this value by 10 to its number of digits and multiplying by 10, an integer is obtained which is the first digit of the analyzed value.

To repeat this digit by the number of digits of the analyzed value, it is necessary to obtain the same number of 1s, so that when multiplying by this first digit, the result returns its respective Carry.

Since 1/9 gives a tithe of 1s, just take the amount of 1s needed for multiplication.

This is done by calculating the entire part of the tithe times 10 to the number of digits.

By multiplying the first digit by the 1s, you get Carry.

By subtracting the value of the Carry obtained by the analyzed value, if the result is zero, it is a Carry, otherwise it is not a Carry.

The number of digits should be considered when Carry.

Do this for every part of your equation!

Answer 3

If I understand your problem, I believe capturing the expression as "string" and dealing with a counter, two control variables and some auxiliary variables are more efficient.

My suggestion is to develop an algorithm as follows:

It will be necessary two control variables, one for register the digit with the highest amount of Carrys in the expression (if it occurs) and another to record the respective digit of this occurrence.

There must be auxiliary variables, such as for the counter of the "loop" that you must "scan" the "string" of the expression character by character from left to right, from one to the number of characters in the expression, for example, to "12 + 999999" will be of 1 until 11.

Whenever the sequence of a single digit occurs, record the amount summing 1 in an auxiliary variable and another auxiliary variable record what this digit is.

When the next digit is different from the previous digit, check whether the quantity of the auxiliary variable is greater than that recorded in the control variable, if it’s not, zero the auxiliary variables and continue, if it is the largest amount, register it in the control variable as also in the other control variable which is this digit. If the same digit will overlap, then there will be no problem, as is the case "555 + 555".

hope I’ve helped!