Use addition or subtraction to get the minimum number of steps for N at each step

From the above problem statement, our task is to get the minimum number of steps in which a given number N can be obtained using addition or subtraction in each step. We can understand that we need to print the minimum number of steps that can be performed and the order of steps for any given integer N, by adding and subtracting the step numbers to arrive at a number starting from 0.

In this problem set, we can add or subtract a number equal to the number of steps to the current position at each step. For example, we can add 1 or -1 in step 1. Further we can add 2 or -2 in step 2 and so on. We can add or subtract numbers at each step depending on the situation.

The main challenge of this problem is that we need to perform the minimum number of steps starting from 0 to reach N. Let us understand this issue better with an example.

The example given below will show you every number we can get in 2 steps starting from 0 by doing the above operations.

For example, assume we have N=1.

Output

Minimum no of steps: 1
Sequence of steps: 1

illustrate

We can achieve this in two ways 1 -

• Just add 1 to step 1 to move from 0 to 1, which takes 1 step.

• Subtract 1 in step 1 to move from 0 to -1, then add 2 in step 2 to move from -1 to 1, which takes 2 steps.

Since the question states that we need a minimum number of steps to reach any number N, the desired output for this input will be 1.

For, N=3

Output

Minimum no of steps: 2
Sequence of steps: 1 2

illustrate

We add 1 in step 1 to move from 0 to 1, then add 2 in step 2 to move from 1 to 3.

method

The best way to solve the problem is to first figure out whether N is a positive or negative number. We must add or subtract the appropriate number of steps respectively to solve the problem.

• If N is a positive number, continue adding steps until the sum is greater than or equal to N.

• Similarly, if N is a negative number, continue subtracting the number of steps until the sum is greater than or equal to N.

• If the sum equals N in the above case, return the number of steps and the order of the steps. The main problem is handling the situation when N is exceeded.

Once the sum exceeds N, check if (sum-N) is even or odd.

• If (sum-N) is even, then we must perform subtraction in steps of (sum-N)/2 to reach N.

  Let us understand this case better with a suitable example.

  For, N=8

  1 2 3 4=10, which is more than 8.

  Because 10-8=2 is an even number. So we're going to subtract in steps of 2/2, which is

  step 1. So the order of steps will be -1 2 3 4 and minimum

  The number of steps to reach N will be 4.

• If (sum-N) is an odd number, first determine whether the number whose sum exceeds N in the previous step is even or odd.

  If the previous step was odd, then perform a step by adding the next step number which will make our (sum-N) even and then perform the above steps to get the desired result.

  For example, N=9

  1 2 3 4=10, which is more than 9.

  Because 10-9=1, this is an odd number. The next step is 5, which is an odd number, so we just do one step and add 5 to the sum to get 15, making (sum-N)=6. Performing the subtraction in step 3 will give you the sequence 1 2 -3 4 5, which is the desired output.

  Assume that the previous step is an even number, in this case, we need to perform two steps, add the i-th step and subtract the (i 1) step, and get (sum- N) as an even number to obtain the desired sequence of steps.

  For N=5

  1 2 3=6, more than 5.

  Since (sum-N) =1, we will consider the last step when su exceeds the number N. Since it is an even number, we will perform two steps, step 4 and step 5. Our task is to make (sum-N) even so, by adding in step 4 and subtracting in step 5 we can make (sum-N) even if 1 is subtracted from the sum. Since (sum-N) is equal to 0, we get N. Therefore, the sequence is 1 2 3 4 -5.

Example

The following is the C code of this method -

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void minimumStep(int n){
   vector <int> steps; // for storing the sequence
   int totalSum=0; 
   int temp=0;
   if(n>=0){   // if n is positive then temp will store positive
      temp=1;
   } else {
      temp=-1;  // n is negative then temp will store negative
   }
   n=abs(n);
   int step=0;
   for(step=1;totalSum<n;step++){  // for storing the steps till sum is not greater than n
      steps.push_back(temp*step);
   
      totalSum=totalSum+step;
   }
   if(totalSum>temp*n) {  //when sum greater than n 
      if(step%2==0) {   //when step is even 
         totalSum=totalSum-n; 
         if((totalSum)%2!=0) { // when totalSum-n is odd
            steps.push_back(temp*step);  //store the addition of next step 
            steps.push_back((temp*-1)*(step+1));  // store the subtraction of next step 
            totalSum--;  //make totalSum even
         }
         int check=(totalSum)/2;
         check--;
         steps[check]=steps[check]*-1; 
		} else {        //when step is odd
         totalSum=totalSum-n;
         if((totalSum)%2!=0)  {  // when totalSum-n is odd 
            steps.push_back(temp*step);   //store the next addition value 
            totalSum+=step; 
            step++;
         }
         int check=(totalSum)/2;
         check--;
         steps[check]=steps[check]*-1;
   
      }
   }
   //print the minimum number of steps taken 
   cout<<"The minimum number of steps : "<<steps.size()<<endl;
   //print the steps is stored in vector
      cout<<"Sequence of steps : ";
   for(int i=0;i<steps.size();i++){
      cout<<steps[i]<<" ";
   }
   
}
int main(){
   int m=17;
   minimumStep(m);
   
   return 0;
}

Output

The minimum number of steps : 6
Sequence of steps : 1 -2 3 4 5 6

Time complexity: O(sqrt(N))

Space complexity: O(sqrt(N))

in conclusion

In this article we try to explain the method to find the minimum number of steps to reach N by adding or subtracting at each step and printing the sequence. I hope this article helps you learn this concept better.

The above is the detailed content of Use addition or subtraction to get the minimum number of steps for N at each step. For more information, please follow other related articles on the PHP Chinese website!