A square triple (a,b,c) is a triple where a, b, and c are integers and a2 + b2 = c2.
Given an integer n, return the number of square triples such that 1 <= a, b, c <= n.
Example 1:
Input: n = 5 Output: 2 Explanation: The square triples are (3,4,5) and (4,3,5).
Example 2:
Input: n = 10 Output: 4 Explanation: The square triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10).
Constraints:
1 <= n <= 250The brute force approach involves iterating through all possible values of a, b, and c within the range of 1 to n and checking if they satisfy the condition a^2 + b^2 = c^2.
This solution uses three nested loops to iterate over all values of a, b, and c from 1 to n. It checks if the sum of the squares of a and b equals the square of c. If a valid triple is found, the count is incremented. The result is the number of such valid triples.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3)
Space Complexity: O(1)
By noticing that c will always be larger than or equal to both a and b in a Pythagorean triple, we can optimize by directly iterating a and b with the constraint that their sum of squares should exactly form a square of another integer c.
This optimized C solution uses only two nested loops over a and b, calculating c using the square root of a^2 + b^2. If c is an integer and within bounds, it counts both (a, b, c) and (b, a, c) as valid triples due to symmetry, thus incrementing count by 2.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) |
| Optimized Loop Approach | Time Complexity: O(n^2) |
The Most Confusing FAANG Interview Question! | Count And Say - Leetcode 38 • Greg Hogg • 33,962 views views
Watch 9 more video solutions →Practice Count Square Sum Triples with our built-in code editor and test cases.
Practice on FleetCode