LeetCode Entry

633. Sum of Square Numbers

17.06.2024 medium 2024 kotlin rust

Is c sum of squares? search

633. Sum of Square Numbers medium blog post substack youtube 2024-06-17_05-53.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/642

Problem TLDR

Is c sum of squares? #medium #binary_search

Intuition

From simple brute force of 0..c for a and b we can do the following optimizations:

  • use sqrt upper bound O(n^2) -> O((sqrt(n))^2)
  • notice that sum function grows linearly and we can do a Binary Search of c in it O((sqrt(n))^2) -> O(sqrt(n)log(n))
  • the trickiest part: a and b can themselves be the upper and lower bounds -> O(sqrt(n))

Approach

Let’s implement both solutions.

Complexity

  • Time complexity: \(O(sqrt(n)log(n))\) and \(O(sqrt(n))\)

  • Space complexity: \(O(1)\)

Code


    fun judgeSquareSum(c: Int): Boolean {
        val s = Math.sqrt(c.toDouble()).toLong()
        for (a in 0..s) {
            var lo = 0L; var hi = s
            while (lo <= hi) {
                val mid = lo + (hi - lo) / 2
                val sum = a * a + mid * mid
                if (sum == c.toLong()) return true
                if (sum > c.toLong()) hi = mid - 1
                else lo = mid + 1
            }
        }
        return false
    }



    pub fn judge_square_sum(c: i32) -> bool {
        let (mut lo, mut hi) = (0u64, (c as f64).sqrt() as u64);
        while lo <= hi {
            let sum = lo * lo + hi * hi;
            if sum == c as u64 { return true }
            if sum > c as u64 { hi -= 1 } else { lo += 1 }
        }; false
    }