2024-06-17 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge
|

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

June LeetCoding Challenge 17

Description

Sum of Square Numbers

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 - 1

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  bool judgeSquareSum(int c) {
    for(int i = 2; i * i <= c; ++i) {
      if(c % i == 0) {
        int count = 0;
        while(c % i == 0) {
          count += 1;
          c /= i;
        }
        if(i % 4 == 3 && (count & 1)) {
          return false;
        }
      }
    }
    return c % 4 != 3;
  }
};

// Accepted
// 124/124 cases passed (4 ms)
// Your runtime beats 54.21 % of cpp submissions
// Your memory usage beats 10.72 % of cpp submissions (6.4 MB)
Algorithm