Problem link : EQUALNUMBERS

Solution:

[theorem] We are given a set of natural numbers from 1 to N. We can always express any value between 1 and N*(N+1)/2 as sum of elements from 1 to N.

Eg. Given set S = {1,2,3,4,5}. We can express any value from 1 to 15, as a sum of an subset of elements in set S.

Lets say, the absolute difference between A and B be D.

D = |A - B|.

Let the sum of set of first n natural numbers be X.

From the above theorem we can always split the set into two subsets of sum (X - Y) and Y respectively. Y can take any value in the range of [0,X].

So, that being said,

We might go with a solution as,

Find the smallest possible value of N(N+1)/2 which is greater than or equal to D, where N is a natural number.

Does this work? Lets check…

Lets say A = 10, B = 22. Then, D = 12.

Smallest value of N(N+1)/2 which is greater than or equal to 12 is 15(N = 5).

We divide 15 into 13 and 2.

A = 10 + 13 = 23

B = 22 + 2 = 24.

ok, now we divide 15 into 14 and 1

A = 10 + 14 = 24

B = 22 + 1 = 23.

As you might have observed that we are unable to make them equal.An important oberservation to make here is that we can make them equal if both D and N(N+1)/2 have same parity(If D is even, N(N+1)/2 should be even, if D is odd, N(N+1)/2 should be odd).

Lets Try with 28 (N=7).

We divide 28 into 20 and 8.

A = 10 + 20 = 30.

B = 22 + 8 = 30.

A = B. → (N = 7)

Solution:

Let X = N(N+1)/2

D = |A - B|

- X > D (From theorem)
- X%2 == D%2 (Observation)

Solution Code:

int A,B;

cin >> A >> B;

int X = 1;

int D = abs(A - B);

while((X*(X+1)/2) < D || ((X*(X+1)/2)%2 != D%2 )

{

X++;

}

cout << X << “\n”;

Complete Code: C++14

```
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int a,b;
cin >> a >> b;
int x = 0;
int n = 0;
while(n < abs(a-b) || n%2 != abs(a-b)%2){
x++;
n += x;
}
cout << x << "\n";
return;
}
int main()
{
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
```

Thank you! : )