I have dry run many times but code is not working properly-CodePudding

I have dry run many times but code is not working properly. If i use formula instead of loops then it is working but in case of loops, it is not working. Please cheak what is the mistake in the loops and what will be the right code.

#include <iostream>
using namespace std;

int main()
{
    int n;
    cout << "enter value of n = ";
    cin >> n;
    int pivotNumber = 1;
    int sum1 = 0;
    int sum2 = 0;
    while (pivotNumber <= n)
    {
        for (int i = 1; i <= pivotNumber; i  )
        {
            sum1 = sum1   i;
        }
        for (int j = pivotNumber; j <= n; j  )
        {
            sum2 = sum2   j;
        }
        if (sum1 == sum2)
        {
            cout << "pivotNumber = " << pivotNumber;
            break;
        }
        pivotNumber  ;
    }

    if (pivotNumber > n)
    {
        cout << -1 << "\n";
    }
}

CodePudding user response：

the loop sum 1 and sum 2 should be initialised within the while loop

#include <iostream>
using namespace std;

int main()
{
    int n;
    cout << "enter value of n = ";
    cin >> n;
    int pivotNumber = 1;

    while (pivotNumber <= n)
    {
        int sum1 = 0;
        int sum2 = 0;
        for (int i = 1; i <= pivotNumber; i  )
        {
            sum1 = sum1   i;
        }
        for (int j = pivotNumber; j <= n; j  )
        {
            sum2 = sum2   j;
        }
        // cout<<sum1<<' '<<sum2;
        if (sum1 == sum2)
        {
            cout << "pivotNumber = " << pivotNumber;
            break;
        }
        pivotNumber  ;
    }

    if (pivotNumber > n)
    {
        cout << -1 << "\n";
    }
}

CodePudding user response：

Your mistake is quite simple (and quite common)

int sum1 = 0;
int sum2 = 0;
while (pivotNumber <= n)
{
    ...
}

should be

while (pivotNumber <= n)
{
    int sum1 = 0;
    int sum2 = 0;
    ...
}

In your version when you start testing a new pivot number you still have the old values of sum1 and sum2 from the previous pivot number. You should declare sum1 and sum2 inside your while loop so each pivot number starts with sums of zero.

CodePudding user response：

The other answers are steering you in the right direction with regards to your bug. But when N gets large, your solution may take a long time to run. It's an O(N²) solution.

We can skip the summation loops and take advantage of a binary search.

The sum of any sequence of numbers between 1..X is ((1 X)*2) / 2.

E.g 1 2 3 4 5 = (1 5)*5/2 == 6*5/2 == 30/2 == 15

And more generally, the sum of any sequence of numbers between X..N is ((X N) * (N-X 1))/2

E.g 6 7 8 9 = (6 9)*(9-6 1)/2 == 15*4/2 == 30

So you can do a quick binary search to find the pivot like this:

   int low = 1;
   int high = n;
   while (low < high) {

      int pivot = (low high)/2;
      int leftSum = ((1 pivot)*pivot)/2;        // SUM of 1..X
      int rightSum = ((n-pivot 1)*(pivot n))/2; // SUM of X..N

      if (leftSum == rightSum) {
         return pivot;
      }

      if (leftSum < rightSum) {
         low = pivot   1;
      } else {
         high = pivot - 1;
      }
   }
   return -1;

Run time is O(lg N)