 C++ program to find a number in minimum steps

//Author: Ananya Smirti (235)

Assumed: Infinite number line from -INFINITY to +INFINITY and we are on zero. We can move n steps either side at each

nth time.

Approach:

The length between +n and -n is 2*n. When negating a number from +ve to -ve it creates a difference of 2*n from the previous sum.If a number lies between n(n+1)/2 and (n+1)(n+2)/2 for any n then we go to step (n+1)(n+2)/2 and try to decrease the sum to the difference. If we go to n(n+1)/2 and then try to increase than it will ultimately lead you to the same number of steps. Since we cannot negate any number (as the sum is already less than the required sum) from n(n+1)/2 this proves that it takes a minimum number of steps.

Time and Space complexity calculation:

If t is the sum that it is required and p is the minimum steps then:
t = (p+1)*(p+2)/2 + 1 (or +2)
Hence t = O(p*p)

Therefore s = O(sqrt(t))
Space Complexity : O(sqrt(t))
Time complexity : O(sqrt(t))

Program:

#include <iostream>
#include<vector>
#include<math.h>
using namespace std;

vector<int> find(int n)
{

vector<int> an;

int s = 0;
int i;

int si = (n >= 0 ? 1 : -1);
n =
abs(n);

for (i = 1; s < n; i++) {
an.push_back(si * i);
s += i;
}

if (s > si * n) {

if (i % 2) {
s -= n;
if (s % 2) {
an.push_back(si * i);
s += i++;
}
an[(s /
2) - 1] *= -1;
}
else {

s -= n;
if (s % 2) {
s--;
an.push_back(si * i);
an.push_back(si *
-1 * (i + 1));
}
an[(s /
2) - 1] *= -1;
}
}
return an;
}

int main()
{

int n;
cout<<"Enter the number to be searched"<<endl;
cin>>n;
if (n == 0)
cout << "Number of Steps: 0"<<endl <<"Sequence of steps:\n0";
else {
vector<int> a1 = find(n);
cout << "Number of Steps: " << a1.size() << "\n Sequence of steps:\n";
for (int i : a1)
cout << i << " ";
}
return 0;
}  More Articles of ananya smirti:

Name Views Likes
C++ program to find a number in minimum steps 349 31