Lesson: 3
Problem: 10035
Title: Primary Arithmetic
Difficulty Level: 1
Date: Dec 05, 2008
Site: UVA
You are given two integers, you have to count and print the number of carry operations that would result from adding the two numbers.
When i first time attempted to solve this problem, i did the following steps:
1.First Convert the two number into strings.
2.Formating those two strings that i can add properly.
Example:
let 2 numbers are 1234 and 99. I convert these into string in this format-
"1234" and "0099", added them and finally count the carry operations.
After few seconds of my submmision, judge responded smartly, "WRONG ANSWER".
Hmmm... that was a stupid procedure to solve this problem. Actually we do not need the sum at all. We need only carry operations. Lets we try...
First number is 1234 and second one is 99 as an example.
First time, we have to add 4 ( last digit of the first number) and 9 ( last digit of the first number)
2nd time, 3 + 9
3rd time 2 + 0 ( i think you know, 99 = 0099)
4th time 1 + 0
For each step, we will add two digits and count carry.
How can we separate each digit from the numbers ? This is most important portion for this problem for beginners.
int k = 1234%10;
what is the value of k ? i think you get it, it's 4. So we can get last digit of an integer by this way. But how can we get 2nd last digit, i.e 3 ? ok, follow me..
int n = 1234;
n = 1234, n%10 = 4
n = n/10; // n = 123, n%10 = 3
n = n/10; // n = 12, n%10 = 2
n = n/10 // n = 1, n%10 = 1
clear ?? if not, send me an email.
put it togather...
int n = 1234, m = 99;
int carry = 0, result = 0;
int sum;
while(n > 0 && m > 0) {
sum = n%10 + m%10 + carry;
if(sum > 9) result++;
carry = sum/10;
n/= 10;
m/= 10;
}
do you get it ??
1st time.....
n = 1234 and m = 99
sum = n%10 + m%10 +carry = 4 + 9 + 0 = 13
sum > 9 ? yes, result = 1;
carry = sum/10, carry = 1;
2nd time....
n = 123, m = 9
sum = n%10 + m%10 +carry = 3 + 9 + 1 = 13
sum > 9 ? yes, result = 2;
carry = sum/10, carry = 1;
3rd time...
n = 12 and m = 0
sum = n%10 + m%10 +carry = 2 + 0 + 1 = 3
sum > 9 ? no, result = 2;
carry = sum/10, carry = 0;
..........
..........
Pop quiz: why does the condition is sum > 9 to increment result ?
Answer: Back to your primary school math book.
Input Specification: input contains two unsigned integers less than 10 digits...
unsigned.. so there is no negative numbers in input.
Output Specification: Very careful..
1.Print "No carry operation." when result is 0
2.Print nnn carry operations. when result is > 1 ( operations, not operation)
3.Print nnn carry operation. when result = 1
And it's very common mistake for beginners to forget to print a full-stop "." after each line.
Source code: Search at my ACM UVA Solution achieve section.