Problem

Given a non-negative integer c, decide whether there’re two integers a and b such that a^2 + b^2 = c.

Examples

Example 1:

1
2
3

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

1
2

Input: c = 3
Output: false

Solution

There are some gotchas to look out for when checking for a and b:

  • 0 is also valid integer, and
  • these two numbers can be the same…

Here is the video explanation:

Method 1 - Brute Force

Run two nested loops - 1 for a and another b till √n, see if they add up to c. This takes O(√n^2) = O(n) time.

Method 2 - Using Hashset

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public class Solution {
    public boolean judgeSquareSum(int c) {
        HashSet<Integer> set = new HashSet<Integer>();
        
        for (int i = 0; i <= Math.sqrt(c); i++) {
            set.add(i * i);
            if (set.contains(c - i * i)) {
                return true;
            }
        }
        return false;
    }
}

Complexity

  • ⏰ Time complexity: O(√n)
  • 🧺 Space complexity: O(√n)

Method 3 - Loop till sqrt n and find b

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) 
        {
            double b = Math.sqrt(c - a * a);
            if (b == (int) b) {
                return true;
            }
        }
        return false;
    }
}

Complexity

  • ⏰ Time complexity: O(√n)
  • 🧺 Space complexity: O(1)

Method 4 - Two pointer approach

We can start with a = left = 0, and b = right = √c. Now, we find c such that c = left^2 + right^2. Note that c = left ^2 + right ^ 2 can overflow.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public class Solution {
    public boolean judgeSquareSum(int c) {
        int left = 0, right = (int) Math.sqrt(c);
        while (left <= right) {
            long curr = (long) left * left + (long) right * right;
            if (curr < c) {
                left++;
            } else if (curr > c) {
                right--;
            } else {
                return true;
            }
        }
        return false;
    }
}

Complexity

  • ⏰ Time complexity: O(√n)
  • 🧺 Space complexity: O(1)