CHEFSQRS - Editorial

editorial
, ,
1

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;
}
6 Likes
2

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?

3

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
5

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
6

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

7

sir for a given N what will be the ranges of a and b

8

because i want to store all perfect squares in an array and i will iterate over the loop and i will check if (arr[i]+N) is present in that array

9

I have a solution to this problem correct me if I am wrong. the difference between the perfect squares are eg. for 1, 4, 9, 16, 25 , 36, 49, 64 are → 3, 5, 7, 9, 11, 13, 15 … here we can notice all the difference are an AP of odd numbers so if a odd number comes then we can simply return the square of the nth value
eg, if N = 3 then the nth value in AP is 1 so we will return 1 * 1 = 1
eg, if N = 11 then the nth value in AP is 5 so we will return 5 * 5 = 25
eg, if N = 15 then the nth value in AP is 7 so we will return 7 * 7 = 49
and, if N is even we can return -1.
the sample test cases work for this approach but I am getting WA on submission.

10

Check the case when N=8;
Answer should be 1

1 Like
11

Why i m getting WA on submission but the logic is right ?

#include <bits/stdc++.h>
using namespace std;

void setIO() {
  cin.tie(0)->ios_base::sync_with_stdio(0);
}

int minsqr(int n) {
  int k = __builtin_ctz(n);
  if(n == 1 or k == 1) return -1;
  if(k == 0) {
    int ans = n;
    for(int i = 1;i*i <= n;++i) {
      if(n % i == 0 && n != i*i) ans = min(ans,abs(n/i-i)/2);
    }
    return ans*ans;
  }
  else {
    int l = abs(n/(1<<(k-1))-(1<<(k-1)))/2;
    return (l ? l*l : -1);
  }
}

int main() {
  setIO();
  int t;
  cin >> t;
  while(t--) {
    int n;
    cin >> n;
    cout << minsqr(n) << '\n';
  }
  return 0;
}