Last updated on January 10th, 2025 at 05:08 am

Here, we see a Sum of Square Numbers LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Recursion, Tree

Companies

Google

Level of Question

Medium

Sum of Square Numbers LeetCode Solution

1. Problem Statement

Given a non-negative integer c, decide whether there are two integers a and b such that a² + b² = c.

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

Example 2:
Input: c = 3
Output: false

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Two Pointers. This pattern involves using two pointers (or indices) to traverse the input space from two different directions (e.g., left and right). In this case, the two pointers (l and r or s and e) are used to find two numbers whose squares sum up to the given number c.

3. Code Implementation in Different Languages

3.1 Sum of Square Numbers C++

class Solution {
public:
    bool judgeSquareSum(int c) {
         if(c==1 || c==0)return true;
        for(long int i=0;i*i<=c;i++){
           long int x=i*i;
           if (isPerfectSquare(c-x))
               return true;
        }
                   return false;        
    }
     bool isPerfectSquare( long int n) {
        if(n==1 || n==0)return true;
      long int s=0,e=n;
        
        while(s<=e){
            long int m=s+(e-s)/2;
            if(m*m==n)return true;
           else if(m*m<n)
                s=m+1;
            else e=m-1;
        }
        return false;
    }
};

3.2 Sum of Square Numbers Java

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

3.3 Sum of Square Numbers JavaScript

var judgeSquareSum = function(c) {
    var r = Math.floor(Math.sqrt(c));
    var l = 0;
    while(l <= r){
        var sum  = l**2 + r**2
        if( sum === c){
            return true
        }else if(sum < c){
            l++
        }else{
            r--
        }
    }
    return false
};

3.4 Sum of Square Numbers Python

class Solution(object):
    def judgeSquareSum(self, c):
        cc = int(c ** 0.5)
        left = 0
        right = cc
        while left <= right:
            res = left ** 2 + right ** 2
            if res == c:
                return True
            elif res < c:
                left += 1
            elif res > c:
                right -= 1
        return False

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(c⋅log⁡c)	O(1)
Java	O(c)	O(1)
JavaScript	O(c)	O(1)
Python	O(c)	O(1)

Here, c can be expressed as the sum of two squares, i.e., c=a²+b², where a and b are non-negative integers.

• The Two Pointers pattern is used in all implementations except for the C++ code, which combines a loop with a binary search.
• The Java, JavaScript, and Python implementations are more efficient than the C++ implementation due to the direct use of the Two Pointers approach.
• The time complexity for Java, JavaScript, and Python is O(c), while for C++, it is O(c⋅log⁡(c)). All implementations have O(1) space complexity.