CHEFSQRS - Editorial

PROBLEM LINK:

Practice

Contest

DIFFICULTY:

Easy

PREREQUISITES:

Mathematics, Factorization

PROBLEM:

Find the smallest perfect square X > 0 such that N + X = Y where Y is another perfect square.

EXPLANATION:

Let N + b^2 = a^2

\implies N = a^2 - b^2

\implies N = (a + b)(a - b)

Thus, we can find the factors of N. We iterate i from 1 to \sqrt{N} and if i is a factor of N then, so is \frac{N}{i}.

Considering a + b = \frac{N}{i} and a - b = i

\implies b = \frac{\frac{N}{i} - i}{2}

We find the minimum value of b over all possible values that satisfy N + b^2 = a^2.

If there is no such value, the answer is -1.

Time Complexity: \mathcal{O}(\sqrt{N}) per test case.

SOLUTION:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        int a, b;
        bool possible = false;
        ll ans = -1;
        for (int i = sqrt(n); i >= 1; --i) {
            if (n % i == 0 && i != (n/i)) {
                a = (n/i + i)/2;
                b = (n/i - i)/2;
                if (b*b + n == a*a) {
                    possible = true;
                    if (ans == -1) {
                        ans = b;
                    } else {
                        ans = min(ans, 1ll*b);
                    }
                }
            }
        }
        if (possible) {
            ans = ans * ans;
        }
        cout << ans << endl;
    }
    return 0;
}
5 Likes

Can we check n%4 to not equal to 2 before hand since difference of two squares cannot be 2(mod 4)?

And why are you using a reverse loop?

Yes, we can actually say that result doesn’t exist if n = 2 (mod 4).

Well, the reverse loop was used thinking that we might be able to assign ans = b directly without taking the min but that didn’t work.

1 Like

After we have values of “a” and “b” which satisfies the equation, we should had break out from the loop because value of “b” will increase as “i” will decrease than why we continued in the loop and why we used min function , i inferred that the solution is suggesting that value of “b” can further decrease as “i” will decrease as it uses a min function but i am not able to see how it can happen?

1 Like

@karanverma96 Yes, you are right, we can break once we have found one value for b.