Similar problems: CF Educational Codeforces Round 78
Explaination
Suppose it takes n steps to reach the required target, then, we need to replace ‘+’ operator with ‘-‘ smartly in the expression
1+2+3+....+n
Here we are only concerned with the minimum number of steps taken to reach abs(target), because we can simply reverse the operators and change the sign of target.
Now, say that we reverse the sign of x in the above mentioned expression, i.e, we convert:
1+2+3+...+x+...+n
into
1+2+3+...-x+...+n
Then if sum was the result of the early expression, reversing the sign of x converts it to sum - 2*x.
Now x can take any value between 1...n, and respectively sum can change to sum - 2 or sum - 4 or .. sum - 2*n, for given value of x. Hence, by observing carefully, the parity of sum doesn’t changes.
So if the parity of sum is odd, it can take any odd value from 1 to sum, and if the parity of sum is even, it can take any even value from 0 to sum. Thus, we need to find the minimum n whose parity is same as abs(target) and sum of integers from 1....n is >= abs(target).
We can easily use Binary Search to attain the same.
class Solution {
public:
inline int sum(int x)
{
return (x*(x+1))>>1;
}
int reachNumber(int target) {
if(target == 0) return 0;
int lo = 1, hi = ceil(sqrt(2e+9));
while(lo < hi)
{
int mid = (lo+hi)>>1;
int s = sum(mid);
if(s >= abs(target)) hi = mid;
else lo = mid+1;
}
if(sum(lo) %2 == abs(target)%2) return lo;
else if(sum(lo+1) % 2 == abs(target)%2) return lo+1;
return lo+2;
}
};
Time Complexity : O(log(INT_MAX)) Space Complexity: O(1)