Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/633.html

633. Sum of Square Numbers

Level

Easy

Description

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a² + b² = c.

Example 1:

Input: 5

Output: True

*Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3

Output: False

Solution

Maintain two numbers low and high, which are 0 and the greatest integer less than or equal to the square root of c. While low < high, calculate sum = low * low + high * high. If sum == c, then the two integers are found, so return true. If sum > c, then sum is too large, so decrease high by 1. If sum < c, then sum is too small, so increase low by 1. If the two integers can’t be found, return false.

• Java
• Python
• C++
• Go
• TypeScript
• RenderScript

• class Solution {
      public boolean judgeSquareSum(int c) {
          int low = 0, high = (int) Math.sqrt(c);
          while (low <= high) {
              int sum = low * low + high * high;
              if (sum == c)
                  return true;
              else if (sum > c)
                  high--;
              else
                  low++;
          }
          return false;
      }
  }
  

• class Solution:
      def judgeSquareSum(self, c: int) -> bool:
          a, b = 0, int(sqrt(c))
          while a <= b:
              s = a**2 + b**2
              if s == c:
                  return True
              if s < c:
                  a += 1
              else:
                  b -= 1
          return False
  
  ############
  
  class Solution(object):
    def judgeSquareSum(self, c):
      """
      :type c: int
      :rtype: bool
      """
      n = int(c ** 0.5)
      start = 0
      end = n
      while start <= end:
        mid = start ** 2 + end ** 2
        if mid == c:
          return True
        elif mid < c:
          start += 1
        else:
          end -= 1
      return False
  
  

• class Solution {
  public:
      bool judgeSquareSum(int c) {
          long a = 0, b = (long) sqrt(c);
          while (a <= b) {
              long s = a * a + b * b;
              if (s == c) return true;
              if (s < c)
                  ++a;
              else
                  --b;
          }
          return false;
      }
  };
  

• func judgeSquareSum(c int) bool {
  	a, b := 0, int(math.Sqrt(float64(c)))
  	for a <= b {
  		s := a*a + b*b
  		if s == c {
  			return true
  		}
  		if s < c {
  			a++
  		} else {
  			b--
  		}
  	}
  	return false
  }
  

• function judgeSquareSum(c: number): boolean {
      let a = 0,
          b = Math.floor(Math.sqrt(c));
      while (a <= b) {
          let sum = a ** 2 + b ** 2;
          if (sum == c) return true;
          if (sum < c) {
              ++a;
          } else {
              --b;
          }
      }
      return false;
  }
  
  

• use std::cmp::Ordering;
  impl Solution {
      pub fn judge_square_sum(c: i32) -> bool {
          let c = c as i64;
          let mut left = 0;
          let mut right = (c as f64).sqrt() as i64;
          while left <= right {
              let num = left * left + right * right;
              match num.cmp(&c) {
                  Ordering::Less => left += 1,
                  Ordering::Greater => right -= 1,
                  Ordering::Equal => return true,
              }
          }
          false
      }
  }
  
  

All Problems

All Solutions