InterView Bit

Question

Given a non negative integer A,
following code tries to find all pair of integers (a, b) such that

• a and b are positive integers
• a <= b, and
• a² + b² = A.
• 0 <= A <= 100000

However, the code has a small bug. Correct the bug and submit the code.

vector<vector<int> > Solution::squareSum(int A) {
    vector<vector<int> > ans;
    for (int a = 0; a * a < A; a++) {
        for (int b = 0; b * b < A; b++) {
            if (a * a + b * b == A) {
                vector<int> newEntry;
                newEntry.push_back(a);
                newEntry.push_back(b);
                ans.push_back(newEntry);
            }
        }
    }
    return ans;
}

Comments

as per logic, don't know about syntax of the programming language

  if (a * a + b * b == A) {

should be check before a ≤ b

  if ( (a ≤ b) && ( (a * a + b * b) ==  A ) ) {

 

and 

for (int b = 0; b * b < A; b++) {

should be as

for (int b = 0; b * b ≤ A; b++) {

---

also i think there is no need to run the outer loop(i.e; loop for a) upto A. running it upto A/2 would be sufficient. because anyhow we don't want a to contribute more than A^2/2, as a should not be greater than b.

---

also i think there is no need to run the outer loop(i.e; loop for a) upto A. running it upto A/2 would be sufficient. because anyhow we don't want a to contribute more than A^2/2, as a should not be greater than b.

yes... but it is optimization of the code

---

Yeah it's optimisation. I just said it's a side note.:D