1

I want to check whether the two numbers when added, generate a carry or not. I assume both numbers are in range 0-9.

Our constraints :

  1. we can not use any operations whose result may goes above 9 or below 0.
  2. we can not use any number out of range 0-9.
  3. we can not use any floating point operation or number.

For example, I can not use if (a+b > 9) then print("there is a carry."); as, as if a=9 and b=6 then a+b = 15. and 15 is out of range.

Is there any efficient way? If there is, answer that efficient way to check the carry in summation. (do consider the constraints as above)

6
  • Is this homework? If it is, that's ok... it's just courteous to disclose that.
    – Matthew
    May 1, 2013 at 19:47
  • a one line answer rarely can b any homework.. it is certainly not a homework.. it was a simple question just came in mind.. when i was going through some questions based on overflow in integers..
    – codeofnode
    May 1, 2013 at 19:50
  • @Matthew Specifying that it's homework is not constructive (which is exactly why the homework tag is gone), but (@Rambo) you probably should show some attempt at solving the problem yourself, questions showing no attempt from the asker are often received very negatively. May 1, 2013 at 20:05
  • @Dukeling answers to homework problems have historically been met with more exploitative answers where people assume the asker may not really understand why the answers apply.
    – Matthew
    May 1, 2013 at 20:06
  • Dukeling : yes i will mind to attempt solving myself before asking in future..
    – codeofnode
    May 1, 2013 at 20:08

4 Answers 4

5
b = 9-b;
a = 0+a;
if (a > b) return true

I'm pretty sure that's the most efficient you can get.

Edit:

Line two is useless, so only two lines, no loops, and you're done. I'm not deleting the original, though, because I think it's funny I actually did that.

5
  • 2
    What is the purpose of line 2?
    – Matthew
    May 1, 2013 at 19:51
  • Mathew, I honestly have no idea.
    – Tomcat
    May 1, 2013 at 19:53
  • Not sure why you got downvoted. I'm pretty sure this is the most efficient solution
    – Matthew
    May 1, 2013 at 19:55
  • 4
    Could as well just make it return a > 9-b now. :) May 1, 2013 at 20:09
  • My thoughts - Don't leave pointless data around just because you think it's funny that you wrote it. Future visitors will probably see this as a nuisance. May 1, 2013 at 20:19
1

Here is one rule

If a >= b and b >=5 then there is a carry
2
  • 2
    This logic has many wholes. I wasn't going to comment, but it became the accepted answer. What if a = 9 and b = 4?
    – MobA11y
    May 1, 2013 at 19:57
  • I think it was accepted by mistake. It's not a good answer, just an example of one rule
    – Matthew
    May 1, 2013 at 20:05
1

Good that @Tomcat found the pattern to this, but sometimes brute force isn't too bad. If the inputs are integers in the range [0,10], one could create a 10*10 boolean lookup table. It would be interesting to benchmark the difference with doing the single subtraction, though it would probably be senseless optimization to go for the lookup table even if it's a tiny bit faster.

4
  • +1 This is probably the most efficient way for a computer to do this. No math operations, no loops... just checking for values in a set -- only 20 possibilities
    – Matthew
    May 1, 2013 at 19:41
  • Remember loading a value from memory is really a series of operations, and is slow. Whereas addition and checks are faster. Any looping function would only ever need 10 loops, and each single loop is likely faster than any load operation would ever be.
    – MobA11y
    May 1, 2013 at 19:44
  • You could create a two dimensional array of all possible number combinations... then there is only one load and this method is then faster. Yay hashing!
    – MobA11y
    May 1, 2013 at 19:51
  • 1
    @Rambo There are, but you only need to check those that do not result in carrying. And by ordering the values, it can be reduced further. May 1, 2013 at 19:54
1

in psuedo code

while a != 0
    if(b == 9) return true
    b++;
    a--;
end

return false;
1
  • -1 In this code b could grow larger than 9 which is not allowed. May 2, 2013 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.