633. Sum of Square Numbers

Problem

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

Intuition

• Tương tự như bài 2sum. Mình xem a^2 + b^2 = c như là x + y = c thì đây chính là dạng bài của 2 sum
• Để ý constraint của bài thì nên xài long thay cho int để tránh trường hợp bị overflow

Approach

• Dùng 2 con trỏ left l, và con trỏ right r.
• Trỏ l tiến từ trái sang phải, trỏ r tiến từ phải sang trái
• Ta có: s = l*l + r*r
  • Nếu s = c => return true vì tồn tại (l, r) thoả mãn l*l + r*r = c
  • Nếu s > c => giảm giá trị con trỏ right 1 đơn vị r-- để làm giảm giá trị của tổng bình phương s
  • Nếu s < c => tăng giá trị con trỏ left 1 đơn vị l++ để làm tăng giá trị của tổng bình phương s

Implementation

class Solution {
    public boolean judgeSquareSum(int c) {
        long n = (long)Math.sqrt(c);
        if (n * n == c) return true;

        long l = 1; long r = n;
        while (l <= r) {
            long s = l*l + r*r;
            if (s == c) return true;
            if (s > c) {
                r--;
            } else {
                l++;
            }
        }

        return false;
    }
}