Step by Step | InterviewBit | Solution Explained

I explain the solution to the problem Step by Step on InterviewBit using observations and logic to build up the optimal solution. Problem Link.

0. Step by Step: Problem Discussion

0.0. IO Format

• input:
  • integer, A: -10⁹ to 10⁹
• condition:
  • starting form 0, the ith move moves you i distance
  • you have the choice of going forward and back – +i or -i
  • each time you move, i increases by 1
• output:
  • integer, minimum number of moves required to reach the target

0.1. Examples

1. Step by Step: Observations & Logic

1.0. Be Positive

One thing that we catch right away is the fact that we can have negative inputs as well. However, this won’t be any different from the positive case – since we can convert A –> -A by just flipping all the signs of all the is used. The last i remains the same.

So, we can do

class Solution:
    def solve(self, A):
        A = abs(A)

1.1. Reaching to A (and beyond)

Since we start from 0, our first goal should be to actually be able to reach the point A. So, assuming all the steps are positive, we keep on iterating till we reach A (or even a slight bit above it).

class Solution:
    def solve(self, A):
        A = abs(A)
        
        last = 0
        running_sum = 0

        while (running_sum < A):
            last += 1
            running_sum += last

1.2. Going back

This is where the problem starts to get more interesting. In reaching the point A, we may have overshot. To fix this, we need to start flipping values from the sum of values seen.

Could we try flipping 1? If we flip 1, we get the running sum as 4.

Welp. Now we are undershooting again.

Note how there is no point checking if doing +2 –> -2 or +3 –> -3 will be any better. Think why?

Since there is no point flipping the sign of any number, we have no choice but to add another number.

What about now? Even in this case, there is no flip we can make to bring the running sum to 5. Why is this happening?

1.3. Investigating the Flip

Here’s one question: What happens to the running sum when we flip the sign of a number?

Or, how much does the running sum change if we flip the sign of the number, say, x?

Try it out on your own once.

…

The running sum changes by 2*x amount.

In other words, to get a change in some y amount in the running sum, we need a number y/2 (or a bunch of numbers summing up to y/2).

But do we really care about the numbers? Or just the sum that they give?

The only thing we have to ensure is that the requested y change in amount is an even number.

Because given that y is an even number, we can always find a bunch of numbers that sum up to y, since y < running sum. (y can never be > running sum. Think why!)

2. Step by Step: Brute-force Solution [TLE]

2.0. Code

class Solution:
    def solve(self, A):
        A = abs(A)
        
        last = 0
        running_sum = 0

        while (running_sum < A) or (running_sum - A) % 2 != 0:
            last += 1
            running_sum += last

        return last

2.1. Complexity Analysis

We may have to go one by one to somehow reach 10⁹. Even if the solution is O(N) time, we won’t be able to make it in 10⁹ time.

The space complexity is O(1), since we only ever store a bunch of variables.

3. Step by Step: Optimized Implementation [Accepted]

3.0. Logic

The most time consuming step is to actually reach the A integer – the step right before it overflows.

What we can use to our advantage is the sum of first n natural numbers formula and reformat it to find the right n for the given A.

3.1. Code

from math import sqrt

class Solution:
    def solve(self, A):
        A = abs(A)
        
        last = int(sqrt(1 + 8*A) - 1) // 2
        running_sum = (last * (last + 1)) // 2

        while (running_sum < A) or (running_sum - A) % 2 != 0:
            last += 1
            running_sum += last

        return last

3.2. Complexity Analysis

• Time: O(1), since we are only <= 2 steps before our solution comes. That’s because we can only go over 2 elements at max before we come with an overflow = (running_sum – A) which is an even number.
• Space: O(1), since we only store 2 variables.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.