Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:
Input: c = 5 Output: true Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: c = 3 Output: false
Constraints:
0 <= c <= 231 - 1The first approach involves using the two-pointer technique. Given an integer c, you start with two pointers a initialized at 0 and b initialized at the square root of c. You calculate a^2 + b^2 and compare it with c. If it equals c, return true. If the sum is less than c, increment a to increase the sum. If the sum is greater than c, decrement b to decrease the sum. Continue this until a exceeds b.
We use a two-pointer approach with a starting from 0 and b from the square root of c. We check the sum of squares and return accordingly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(sqrt(c))
Space Complexity: O(1)
This approach is a brute-force method. Start with a single loop iterating from a = 0 to sqrt(c). For each value of a, calculate a^2 and check if c - a^2 is a perfect square. If it is, return true, otherwise continue. If the loop completes without finding such values, return false.
This solution checks every value of a up to sqrt(c) and verifies if c - a^2 is a perfect square.
C++
Java
Python
C#
JavaScript
Time Complexity: O(sqrt(c) * log(c)) due to the isPerfectSquare check.
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Using Two Pointers | Time Complexity: O(sqrt(c)) |
| Mathematical Interpretation and Brute Force | Time Complexity: O(sqrt(c) * log(c)) due to the isPerfectSquare check. |
Perfect Squares - Dynamic Programming - Leetcode 279 - Python • NeetCode • 62,696 views views
Watch 9 more video solutions →Practice Sum of Square Numbers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor