Counting carry operations

Question

Can anybody tell me why my program keeps getting wrong answer? It must count the number of carry operations in a sum. I tried every testcase came to my mind. I didn't get wrong output.

Problem Description:

Children are taught to add multi-digit numbers from right-to-left one digit at a time. Many find the "carry" operation - in which a 1 is carried from one digit position to be added to the next - to be a significant challenge. Your job is to count the number of carry operations for each of a set of addition problems so that educators may assess their difficulty.

Input

Each line of input contains two unsigned integers less than 10 digits. The last line of input contains 0 0.

Output

For each line of input except the last you should compute and print the number of carry operations that would result from adding the two numbers, in the format shown below.

Sample Input

123 456
555 555
123 594
0 0

Sample Output

No carry operation.
3 carry operations.
1 carry operation.

Here's my current code:

#include<stdio.h>
int main()
{
    unsigned long long int a,b,m,n,rem_m,rem_n,judge=0,sum,count;
    while((scanf("%llu%llu",&m,&n))==2)
    {
        if(m==0 && n==0)
        {
            break;
        }
        count=0;
        while(m!=0 && n!=0)
        {
            rem_m=m%10;
            rem_n=n%10;
            if(judge==1)
            {
                rem_m++;
            }
            sum = rem_m+rem_n;
            judge=0;
            if(sum>=10)
            {
                count++;
                judge++;
            }
            m=m/10;
            n=n/10;
        }
        if(count==0)
        {
            printf("No carry operation.\n");
        }
        else
        {
            printf("%llu carry operations.\n",count);
        }
    }
    return 0;
}

Answer 1

count the number of carry operations in a sum

Asserting a,b are >= 0:

Terse solution

For fun :)

"ds" stands for digit sum.

int ds(int n){return n == 0 ? 0 : n%10 + ds(n/10);}
int numberOfCarryOperations(int a,int b){return (ds(a) + ds(b) - ds(a+b)) / 9;}

Readable

Here is a more readable variation.

int digitSum(int n)
{
    int sum;
    for (sum=0; n > 0; sum+=n%10,n/=10);
    return sum;
}

int numberOfCarryOperations(int a,int b){
    // a, b >= 0
    return (digitSum(a) + digitSum(b) - digitSum(a+b)) / 9;
}

You can prove mathematically: every time you have a carry, the digitSum decreases by 9.

9, because we are in number system 10, so we "lose 10" on one digit if we have carry, and we gain +1 as the carry.

Pythonic version

I do not know how to do this in C, but in python it is easy to write a better digitSum function. In python we can easily create the list of digits from a number, and then just use sum() on it to get digitSum of the given number.

Here is a terse python one-liner solution:

def numberOfCarryOperations(a, b):
    # f is the digitSum function
    f=lambda n:sum(map(int,str(n)));return(f(a)+f(b)-f(a+b))/9
    

Answer 2

Java program for people interested

static int numberOfCarryOperations(int num1, int num2) {
        int counter = 0;
        int result1 = 0;
        int result2 = 0;
        int carryNum = 0;
        while(  num1 != 0 || num2 != 0) {
            result1 = num1%10;
            result2 = num2%10;
            
            if(num1 > 0 ) {
                num1 = num1/10;
            }
            if( num2 > 0) {
                num2 = num2/10;
            }
            
            if( (result1 + result2+carryNum) > 9 ) {
                counter++;
                carryNum = 1;
            } else {
                carryNum = 0;
            }
        }
        return counter;
    }
    
    
    public static void main(String[] args) {
        System.out.println(numberOfCarryOperations(123, 456)); // 0
        System.out.println(numberOfCarryOperations(555, 555)); // 3
        System.out.println(numberOfCarryOperations(900, 11)); // 0
        System.out.println(numberOfCarryOperations(145, 55)); // 2
        System.out.println(numberOfCarryOperations(0, 0));// 0
        System.out.println(numberOfCarryOperations(1, 99999) );// 5
        System.out.println(numberOfCarryOperations(999045, 1055) );// 5
        System.out.println(numberOfCarryOperations(101, 809)); // 1
        System.out.println(numberOfCarryOperations(189, 209) );// 1
    }

Answer 3

A java solution would be:

public class Main {

    public  static int carry_count=0,carry_number=0;
    public static void main(String[] args) {
        System.out.println(Carry(99511,512));
    }
    private  static  int Carry(int num1,int num2){
       if(num1/10==0 || num2/10==0){
           int sum=num1%10+num2%10+carry_number;
           if(sum>=10){
               carry_number=1;
               carry_count++;
               return Carry(num1/10,num2/10);
           }else{
           return carry_count;}
       }else {
           int sum=num1%10+num2%10+carry_number;
           if(sum>=10){
               carry_number=1;
               carry_count++;
           }else {
               carry_number=0;
           }
           return Carry(num1/10,num2/10);
       }
    }
}

Answer 4

A ruby solution would be:

def count_carry_operations x, y
  return 0 if x == 0 && y == 0

  count = 0
  carry = 0

  while true
    return count if x == 0 && y == 0

    while x != 0 || y != 0
      xr = x % 10
      yr = y % 10

      xr += 1 if carry == 1

      sum = xr + yr
      carry = 0

      if sum >= 10
        count += 1
        carry += 1
      end

      x /= 10
      y /= 10
    end

    carry = 0
  end

  count
end

Answer 5

The loop condition is wrong. You want while(m!=0 || n!=0) (i.e. while at least one of them is not zero) instead of while(m!=0 && n!=0), otherwise the answer will be wrong for things like 999 9, it will incorrectly stop after one iteration and report 1 carry operation whereas the correct answer should be 3. Think of it like this: you only want to stop when both of them are 0, so the loop must continue as long as at least one of the numbers is not 0.

Also, you forgot to clean up judge after printing output. You need to clear it before reading input again, or you could mistakenly have judge == 1 from a previous computation that ended with a carry (the name choice for this variable seems odd to me, you should rename it to something more meaningful like carry, but it's not the main issue here).

a and b are unused (you should enable compiler warnings).

The sample output shows the word operation (as in, singular) when the count is 1; your program always writes operations (plural). If you're submitting this to an automatic judge, the code will not pass because the output does not match exactly the expected output. To fix that small little detail, replace this:

else
{
    printf("%llu carry operations.\n",count);
}

With:

else
{
    printf("%llu carry operation%s.\n",count, count > 1 ? "s" : "");
}

Here's the fixed version:

#include <stdio.h>

int main(void)
{
    unsigned long long int m,n,rem_m,rem_n,judge=0,sum,count;
    while((scanf("%llu%llu",&m,&n))==2)
    {
        if(m==0 && n==0)
        {
            break;
        }
        count=0;

        /* We want || here, not && */
        while(m!=0 || n!=0)
        {
            rem_m=m%10;
            rem_n=n%10;
            if(judge==1)
            {
                rem_m++;
            }
            sum = rem_m+rem_n;
            judge=0;
            if(sum>=10)
            {
                count++;
                judge++;
            }
            m=m/10;
            n=n/10;
        }

        /* Clean up for next iteration */    
        judge = 0;

        if(count==0)
        {
            printf("No carry operation.\n");
        }
        else
        {
            printf("%llu carry operations.\n",count);
        }
    }
    return 0;
}