633. Sum of Square Numbers

Given a non-negative integer c, decide whether there’re 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

Constraints:

• 0 <= c <= 2³¹ - 1

Approach 01:

class Solution {
public:
    bool judgeSquareSum(int c) {
        if (c == 0) {
            return true;
        }

        int limit = std::floor(sqrt(c));

        for (int i = 1; i <= limit; ++i) {
            int a = i * i;
            int data = c - a;
            int b = std::floor(sqrt(data));

            if ((a + b * b) == c) {
                return true;
            }
        }

        return false;
    }
};

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        
        if(c == 0):
            return True
        
        limit = math.floor(c**(1/2))

        for i in range(1, limit+1):
            a = i*i
            data = c - a
            b = (data**(1/2))
            b = math.floor(b)

            print(a)
            print(b)
            if((a + b*b) == c):
                return True
        return False

Space Complexity:

O(1): The code uses a constant amount of extra space regardless of the input value c. This is because it declares a limited number of variables (limit, i, a, data, and b) that hold integer values. These variables do not grow with the input size.

Time Complexity:

O(sqrt(c)): The main loop iterates from i = 1 to limit (which is the square root of c). In the worst case, the loop might iterate through all possible a values (up to the square root of c) without finding a match. The number of iterations is directly related to the input value’s square root, leading to a time complexity of O(sqrt(c)).