Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 8

Description

Count Square Sum Triples

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

Solution

constexpr int isqrt(int n) {
  if (n < 0) return -1;
  int x = n;
  int y = (x + 1) / 2;
  while (y < x) {
    x = y;
    y = (x + n / x) / 2;
  }
  return x;
}

// Using std::array is the standard way to return fixed-size arrays in constexpr
constexpr array<int, 251> answer = []() {
  array<int, 251> result{}; // Initialize with 0s

  // Iterate to find Pythagorean triples
  for (int i = 1; i < 250; ++i) {
    for (int j = i + 1; j < 250; ++j) {
      int sum_sq = i * i + j * j;
      
      if (sum_sq >= 251 * 251) break; 

      int k = isqrt((int)sum_sq);

      if (k * k == sum_sq && k < 251) {
        result[k] += 1 + (i != j); 
      }
    }
  }

  for (int i = 1; i < 251; ++i) {
    result[i] += result[i - 1];
  }

  return result;
}();
class Solution {
public:
  int countTriples(int n) {
  return answer[n];
  }
};

// Accepted
// 91/91 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 55.32 % of cpp submissions (7.8 MB)