Reputation: 49
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?
Upvotes: 4
Views: 170
Reputation: 373512
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.
Upvotes: 4