Why does this recursive algorithm give the wrong answer on input 2,147,483,647?

user_8887582 0
Viewed 154

I'm working on the following question:

Given a positive integer n and you can do operations as follow:

  • If n is even, replace n with n/2.
  • If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Here's the code I've come up with:

class Solution {
private:
    unordered_map<int, long long> count_num;
public:
    int integerReplacement(int n) {
        count_num[1] = 0;count_num[2] = 1;count_num[3] = 2;
        if(!count_num.count(n)){
            if(n%2){
                count_num[n] = min( integerReplacement((n-1)/2), integerReplacement((n+1)/2) )+2;
            }else{
                count_num[n] = integerReplacement(n/2) +1;
            }
        }
        return(count_num[n]);
    }
};

When the input is 2147483647, my code incorrectly outputs 33 instead of the correct answer, 32. Why is my code giving the wrong answer here?

recursion algorithm c++
1 Answers

I suspect that this is integer overflow. The number you've listed (2,147,483,647) is the maximum possible value that can fit into an int, assuming you're using a signed 32-bit integer, so if you add one to it, you overflow to INT_MIN, which is −2,147,483,648. From there, it's not surprising that you'd get the wrong answer, since this value isn't what you expected to get.

The overflow specifically occurs when you compute

integerReplacement((n+1)/2)

and so you'll need to fix that case to compute (n+1) / 2 without overflowing. This is a pretty extreme edge case, so I'm not surprised that the code tripped up on it.

One way to do this is to note that if n is odd, then (n + 1) / 2 is equal to (n / 2) + 1 (with integer division). So perhaps you could rewrite this as

integerReplacement((n / 2) + 1)

which computes the same value but doesn't have the overflow.

user_5015570
Related