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 a2 + b2 = 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.

  • 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