You are standing at 0 on an infinite number line, you have to reach the target.
On each move, you can either move to the right or to left. During the n-th move(starting from 1), take n steps.
Return the minimum number of steps required to reach the destination.
Constraints: target will be in the range [-10^9,10^9].
Input: Target = 3
Output: 2
Solution:
In this problem, we will be taking steps like 1+2+3+.......k such that the sum is equal to the target. Now, all we have to do is place + and - signs for the steps we take.
If target<0 we can simply switch the signs of all the number which we would have taken for the absolute value of the target, therefore the result for target<0 will become as abs(target).
Now we find the sum of the above series such that is equal to or is just greater than the target. If it is equal to target we return k,
Else we have 2 cases
Case1: when difference between the sum and target is even in that case we need to switch the sign of the number (sum-target)/2. Therefore the result will be k.
Case2: when the difference between the sum and target is odd in that case we keep adding steps to sum one by one until the difference between target and sum becomes even.
Code:
int reachNumber(int target) {
target=abs(target);
int sum=0,k=0;
while(sum<target)
{
k++;
sum+=k;
}
if(sum==target||(sum-target)%2==0)
return k;
while(true)
{
if((sum-target)%2==0)
break;
k++;
sum+=k;
}
return k;
}
Programming ninja
If you have any doubts or any new insights, please share ConversionConversion EmoticonEmoticon