633.sum-of-square-numbers.md

633. Sum of Square Numbers

Breakdowns

1. Given c, how to check if there are two integers a and b such that a + b = c?

Similar to 1. Two Sum, the differences are to find the square and that a and b do not come from the array, but from the range [0, c].

• Binary search: iterate all a in 0..c, and binary search b = c - a.
• Two pointers:
  • a: 0 -> c.
  • b: c -> 0.
• Hash table: add all possible a to set, then iterate all a and check if b = c - a exists in the set.

Key Insights

We iterate all possible a and find b so that a^2 + b^2 = c. The maximum value of a and b is sqrt(c). Why?

b^2 <= c imples b <= sqrt(c), otherwise, if b > sqrt(c) then b^2 > c and a^2 + b^2 > c, which contradicts the condition a^2 + b^2 = c.

Binary Search

We can iterate a and try to find b^2 = c - a^2 by binary search:

fun judgeSquareSum(c: Int): Boolean {
    val c = c.toLong()
    var a = 0L
    // Equivalently
    // for (a in 0..sqrt(c * 1.0).toLong())
    while (a * a <= c) {
        val bb: Long = (c - a * a)
        if (isSqrt(bb)) return true
        a++
    }
    return false
}

// Preferred way, check if the number is a perfect square
private fun isSqrt(target: Long): Boolean {
    var left = 0L
    var right = target
    while (left <= right) {
        val middle = left + (right - left) / 2
        // Equivalent: middle * middle == target
        val sqrt = target / middle
        if (sqrt * sqrt == target) {
            return true
        }

        if (middle < sqrt) left = middle + 1
        else right = middle - 1
    }
    return false
}

// Equivalent, similar to [69. Sqrt(x)](../leetcode/69.sqrt(x).md), but not rounded down!!
private fun isSqrt(num: Long): Boolean {
    var left = 0L
    var right = num
    while (left <= right) {
        val middle = left + (right - left) / 2
        // num^2 <= target -> num <= target / num
        // Find the largest number `num` which `num * num <= x`
        val isValid = (middle <= num / middle)
        if (isValid) { 
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    return right * right == num
}

• Time Complexity: O(sqrt(c) * log c).
• Space Complexity: O(1).

Two Pointers

The maximum value of a and b is sqrt(c), so we can use two pointers to find a and b:

a^2 + b^2 = c

a -> ... <- b

fun judgeSquareSum(c: Int): Boolean {
    val c = c.toLong()
    var a = 0L
    var b = sqrt(c * 1.0).toLong()
    while (a <= b) {
        val sum = a * a + b * b
        if (sum == c) return true
        if (sum < c) a++
        else b--
    }
    return false
}

• Time Complexity: O(sqrt(c)).
• Space Complexity: O(1).

Hash Table

We can add all possible a^2 to set, then iterate all a^2 and check if b^2 = c - a^2 exists in the set. Please note that we should add a^2 before checking b^2 = c - a^2 existence rather than "checking first, adding later" (different from 1. Two Sum). Why? Suppose you check if c - a^2 exists before inserting a^2 into the set. This means when a = 0, the complement is c - 0^2 = c, but set is still empty, so it never finds a match.

Key Differences: 1. Two Sum vs. 633. Sum of Square Numbers

Problem	Order	Why
1.Two Sum	Check first, add later.	Because b = target - a might already be in the set from previous elements in the array.
633. Sum of Square Numbers	Add first, then check.	Because we need to ensure that b^2 = c - a^2 is in the set before looking it up.

fun judgeSquareSum(c: Int): Boolean {
    val c = c.toLong()
    val set = HashSet<Long>()
    for (a in 0L..sqrt(c * 1.0).toLong()) {
        set.add(a * a)
    }
    set.forEach { aa ->
        val bb = c - aa
        if (bb in set) return true
    }
    return false
}

// Or equivalently, followed the general template of two sum
fun judgeSquareSum(c: Int): Boolean {
    val set = HashSet<Int>()
    for (a in 0..sqrt(c.toDouble()).toInt()) {
        // Mind the order of adding to set
        set.add(a * a)
        val complement = c - a * a
        if (complement in set) return true
    }
    return false
}

/**
WA when c = 2, why? 
 */
fun judgeSquareSum(c: Int): Boolean {
    val set = HashSet<Int>()
    for (a in 0..sqrt(c.toDouble()).toInt()) {
        val complement = c - a * a
        if (complement in set) return true
        set.add(a * a)
    }
    return false
}

• Time Complexity: O(sqrt(c)).
• Space Complexity: O(sqrt(c)).

Edge Cases

• c = 0: true, since 0^2 + 0^2 = 0.
• c = 1: true, since 0^2 + 1^2 = 1.
• c = 2: true, since 1^2 + 1^2 = 2.
• c = 4: perfect square, true. a or b can be 0.