1925. Count Square Sum Triples

Description

A square triple (a,b,c) is a triple where a, b, and c are integers and a² + b² = c².

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

Solutions

Solution: Math

Time complexity: O(n²)
Space complexity: O(1)

JavaScript

js

/**
 * @param {number} n
 * @return {number}
 */
const countTriples = function (n) {
  const maxSquare = n ** 2;
  let result = 0;

  for (let a = 1; a <= n; a++) {
    const square = a ** 2;

    for (let b = 1; square + b ** 2 <= maxSquare; b++) {
      const sum = square + b ** 2;

      if (Math.sqrt(sum) % 1) continue;

      result += 1;
    }
  }

  return result;
};