A mathematical method to know how many carrys in a sum

3

I saw today in the URI (site of programming problems) an issue in which your program should read two values and say how many carrys (or "go one" s ) occur in the sum of them. Ex: 555 + 555 = 3 carrys and 1 + 9999999 = 7 carrys .

I did a program to calculate manually, just like a human, first I equalized 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 performed. But some people said that there was a way to answer this much more efficiently and I would like to know how it is, I looked it up on google but found nowhere, I believe it is similar to how to find out how many zeros there are in a factorial number (< a href="http://www.tutorbrasil.com.br/forum/matematica-ensino-medio/fatorial-t16640.html"> Determine zeros of factorial ).

    
asked by anonymous 03.07.2016 / 14:57

3 answers

5

I did not understand Leo's mathematical solution 100%, maybe it's the same as I'll show here. I found on the Math Overflow site a discussion that indicates there a relation between the number of carries and the sums of the digits of each operand and the result. This formula is quoted:

Sbrepresentsasumofdigitsinthebaseb;aandcaretheoperandsofaddition,andkisthenumberofcarries.Rearrangingtheformulatoisolatek,andconsideringthatyouareworkingonbase10,wewillhave:

ACimplementation,asanexample:

#include<stdio.h>intmain(void){intteste1=carries(9,1);intteste2=carries(99,1);intteste3=carries(999,1);intteste4=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;
}

link

    
05.07.2016 / 16:40
1

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

My suggestion is to develop an algorithm as follows:

It will take two control variables , one to register the digit with the most Carrys in the expression (if it occurs) and another to register the digit of this occurrence.

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

Whenever the sequence of the same digit occurs, record the quantity by adding 1 to an auxiliary variable and to another auxiliary variable record what that digit .

>

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

I hope to have helped!

    
03.07.2016 / 18:08
1

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

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

Belowisanexamplewiththecellformulasshownnext(inthisexample,thecolumnis"I" and the initial data line is 13)

Howcalculationswork:

First you have to calculate the number of digits of the number to be analyzed, this is done through the entire part of the result of the base 10 logarithm of that number plus one.

The base log 10, for values such as 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 log 10 between 3 and 4, never 3 (would be 1000) or 4 (would be 10000 ).

In this way, 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 integer values in this range will necessarily have four digits , and the result of their logarithms will always be greater than 3 and less than 4.

So, by taking the whole part of this calculation and adding one, we get the number of digits of the integer parsed.

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

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

To repeat this digit by the number of digits of the analyzed value, you must obtain the same number of 1s, so that, by multiplying by this first digit, the result returns its respective Carry.

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

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

When you multiply the first digit by 1s, you get Carry.

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

The number of digits should be considered when obtaining Carry.

Do this for every part of your equation!

    
04.07.2016 / 23:55