Count Square Sum Triples solution and explanation
Google
9 more videos on this problem
Count Square Sum Triples | Simple and Easy Solution | Leetcode 1925 | codestorywithMIKcodestorywithMIK · 9:49 · 4K views
1925. Count Square Sum Triples (Leetcode Easy)Programming Live with Larry · 3:12 · 1K views
1925. Count Square Sum Triples | Leetcode Daily - PythonLeetcode Daily · 8:59 · 748 views
LeetCode 1925. Count Square Sum TriplesSakura Programming · 2:25 · 622 views
Count Square Sum Triples 🔥 Leetcode 1925 | Number Theory | Optimal Approach Explained Study Placement · 2:44 · 402 views
Daily Leetcode #2078: Dec 08, 2025 - 1925. Count Square Sum TriplesProgramming Live with Larry · 4:46 · 397 views
Count Square Sum Triples | Leetcode 1925 | DSA | Hindi | Code With DeepakCode with Deepak · 2:19 · 303 views
Count Square Sum Triples | LeetCode 1925 - Pythonimpoldev · 11:10 · 247 views
Count Square Sum Triples | LeetCode 1925 | Java Code | Developer CoderDeveloper Coder · 7:37 · 245 views
question no.- 1925 || Count Square Sum Triples|| Leetcode Daily ProblemLeetCodewithManish · 5:05 · 196 views
The problem
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 <= 250
Approach overview
Problem Overview: Given an integer n, count the number of ordered triples (a, b, c) such that 1 ≤ a, b, c ≤ n and a² + b² = c². The task is essentially finding all Pythagorean triples within the range [1, n].
Approach 1: Brute Force Enumeration (O(n³) time, O(1) space)
Iterate over every possible combination of a, b, and c from 1 to n. For each triple, compute a*a + b*b and compare it with c*c. If they match, increment the count. This method directly checks the Pythagorean condition without any optimization. It’s useful for understanding the problem constraints and validating smaller inputs, but the cubic time complexity becomes expensive as n grows.
Approach 2: Optimized Loop with Square Root Check (O(n²) time, O(1) space)
Instead of iterating over all three variables, iterate only over a and b. Compute sum = a*a + b*b and check whether it forms a perfect square. If c = sqrt(sum) is an integer and c ≤ n, a valid triple exists. This removes the third loop and reduces the complexity to quadratic. The key insight is treating c as a derived value rather than iterating through all candidates. This approach relies on basic math properties and systematic enumeration of pairs.
Recommended for interviews: Start by describing the brute force enumeration to show you understand the constraint a² + b² = c². Then move to the optimized two-loop approach that computes c using a square root check. Interviewers typically expect the O(n²) solution because it removes unnecessary iteration while keeping the implementation simple.
Approach 1: Brute Force Approach
The 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.
def count_square_triples(n):
count = 0
for a in range(1, n + 1):
for b in range(1, n + 1):
for c in range(1, n + 1):
if a * a + b * b == c * c:
count += 1
return count
n = 10
print(count_square_triples(n))public class SquareTriples {
public static int countSquareTriples(int n) {
int count = 0;
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
for (int c = 1; c <= n; c++) {
if (a * a + b * b == c * c) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
int n = 10;
System.out.println(countSquareTriples(n));
}
}#include <iostream>
using namespace std;
int countSquareTriples(int n) {
int count = 0;
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
for (int c = 1; c <= n; c++) {
if (a * a + b * b == c * c) {
count++;
}
}
}
}
return count;
}
int main() {
int n = 10;
cout << countSquareTriples(n) << endl;
return 0;
}function countSquareTriples(n) {
let count = 0;
for (let a = 1; a <= n; a++) {
for (let b = 1; b <= n; b++) {
for (let c = 1; c <= n; c++) {
if (a * a + b * b === c * c) {
count++;
}
}
}
}
return count;
}
const n = 10;
console.log(countSquareTriples(n));#include <stdio.h>
int countSquareTriples(int n) {
int count = 0;
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
for (int c = 1; c <= n; c++) {
if (a * a + b * b == c * c) {
count++;
}
}
}
}
return count;
}
int main() {
int n = 10;
printf("%d", countSquareTriples(n));
return 0;
}using System;
public class SquareTriples {
public static int CountSquareTriples(int n) {
int count = 0;
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
for (int c = 1; c <= n; c++) {
if (a * a + b * b == c * c) {
count++;
}
}
}
}
return count;
}
static void Main(string[] args) {
int n = 10;
Console.WriteLine(CountSquareTriples(n));
}
}This Python solution iterates through all integers a, b, and c in the range from 1 to n and checks for valid Pythagorean triples. Each time a valid triple is found, the count is incremented.
Time Complexity: O(n^3)
Space Complexity: O(1)
Approach 2: Optimized Loop Approach
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.
import math
def count_square_triples(n):
count = 0
for a in range(1, n + 1):
for b in range(a, n + 1):
c = int(math.sqrt(a * a + b * b))
if c <= n and c * c == a * a + b * b:
count += 2
return count
n = 10
print(count_square_triples(n))public class SquareTriples {
public static int countSquareTriples(int n) {
int count = 0;
for (int a = 1; a <= n; a++) {
for (int b = a; b <= n; b++) {
int c = (int)Math.sqrt(a * a + b * b);
if (c <= n && c * c == a * a + b * b) {
count += 2;
}
}
}
return count;
}
public static void main(String[] args) {
int n = 10;
System.out.println(countSquareTriples(n));
}
}#include <iostream>
#include <cmath>
using namespace std;
int countSquareTriples(int n) {
int count = 0;
for (int a = 1; a <= n; a++) {
for (int b = a; b <= n; b++) {
int c = sqrt(a * a + b * b);
if (c <= n && c * c == a * a + b * b) {
count += 2;
}
}
}
return count;
}
int main() {
int n = 10;
cout << countSquareTriples(n) << endl;
return 0;
}function countSquareTriples(n) {
let count = 0;
for (let a = 1; a <= n; a++) {
for (let b = a; b <= n; b++) {
let c = Math.sqrt(a * a + b * b);
if (c <= n && c === Math.floor(c)) {
count += 2;
}
}
}
return count;
}
const n = 10;
console.log(countSquareTriples(n));#include <stdio.h>
#include <math.h>
int countSquareTriples(int n) {
int count = 0;
for (int a = 1; a <= n; a++) {
for (int b = a; b <= n; b++) {
int c = sqrt(a * a + b * b);
if (c <= n && c * c == a * a + b * b) {
count += 2; // (a, b, c) and (b, a, c)
}
}
}
return count;
}
int main() {
int n = 10;
printf("%d", countSquareTriples(n));
return 0;
}using System;
public class SquareTriples {
public static int CountSquareTriples(int n) {
int count = 0;
for (int a = 1; a <= n; a++) {
for (int b = a; b <= n; b++) {
int c = (int)Math.Sqrt(a * a + b * b);
if (c <= n && c * c == a * a + b * b) {
count += 2;
}
}
}
return count;
}
static void Main(string[] args) {
int n = 10;
Console.WriteLine(CountSquareTriples(n));
}
}The Python implementation uses an optimization that computes c when iterating through a and b. When c is valid, it assumes symmetrical pairs and increments the count by 2.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 3: Enumeration
We enumerate a and b in the range [1, n), then calculate c = \sqrt{a^2 + b^2}. If c is an integer and c leq n, then we have found a Pythagorean triplet, and we increment the answer by one.
After the enumeration is complete, return the answer.
The time complexity is O(n^2), where n is the given integer. The space complexity is O(1).
function countTriples(n: number): number {
let ans = 0;
for (let a = 1; a < n; a++) {
for (let b = 1; b < n; b++) {
const x = a * a + b * b;
const c = Math.floor(Math.sqrt(x));
if (c <= n && c * c === x) {
ans++;
}
}
}
return ans;
}func countTriples(n int) (ans int) {
for a := 1; a < n; a++ {
for b := 1; b < n; b++ {
x := a*a + b*b
c := int(math.Sqrt(float64(x)))
if c <= n && c*c == x {
ans++
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) |
| Optimized Loop Approach | Time Complexity: O(n^2) |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n³) | O(1) | When demonstrating the direct definition of the problem or validating small constraints |
| Optimized Loop with Square Root Check | O(n²) | O(1) | Preferred approach for interviews and production due to reduced iteration |
Frequently asked questions
Is Count Square Sum Triples easy or hard?
Count Square Sum Triples is classified as an Easy problem on LeetCode with an acceptance rate above 70%. The challenge mainly involves recognizing the Pythagorean relation a² + b² = c² and optimizing the brute force enumeration.
Count Square Sum Triples Python/Java solution
Most implementations use two nested loops and a square root check. Python solutions typically use math.sqrt while Java implementations use Math.sqrt and verify that the result is an integer before counting the triple.
How to solve Count Square Sum Triples in O(n²)?
Loop through all pairs (a, b) from 1 to n. For each pair, compute sum = a² + b² and calculate c = sqrt(sum). If c is an integer and c ≤ n, increment the count. This avoids the third loop and keeps the algorithm at O(n²) time.
What is the best approach for Count Square Sum Triples?
The optimized enumeration approach using two loops is the best solution. Iterate over values of a and b, compute a² + b², and check if the result is a perfect square c where c ≤ n. This reduces the complexity to O(n²) with O(1) space.
Is Count Square Sum Triples asked at Google/Amazon/Meta?
This problem is categorized as Easy and focuses on math-based enumeration. Variations of Pythagorean triple checks and enumeration problems appear in interviews at companies like Amazon and Google to test basic algorithmic reasoning.
What data structure is used in Count Square Sum Triples?
No advanced data structure is required. The problem primarily uses mathematical computation and simple loops. Some implementations optionally use a set of squares for faster lookups, but the standard optimized solution works with constant extra space.
What is the time complexity of Count Square Sum Triples?
The brute force approach runs in O(n³) time because it checks every combination of a, b, and c. The optimized solution reduces this to O(n²) by computing c directly from a² + b² and verifying whether it is a valid integer within range.