# 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: -109 to 109
• 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

## 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 `i`s 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 109. Even if the solution is O(N) time, we won’t be able to make it in 109 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.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Assign Mice to Holes | InterviewBit | Solution Explained

June 13, 2022

2. This solution need an amendment for 2 digit number.

3. Please write a Proof for this

4. Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

This site uses Akismet to reduce spam. Learn how your comment data is processed.