A LeetCode Daily Series — Day 78

Welcome to today’s blog post where we delve into an intriguing mathematical problem: determining whether a given non-negative integer can be expressed as the sum of two square numbers. This problem is a classic example of how mathematics and computer science can intersect to solve real-world problems efficiently.

Sum Of Square Numbers - LeetCode leetcode.com

Can you solve this real interview question? Sum Of Square Numbers

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

A LeetCode Daily Series — Introduction | Ritesh Shakya riteshakya.com.np

Hey everyone, I’m excited to announce that I’m embarking on a journey to conquer LeetCode!

Understanding the Problem#

The problem is to determine if there exist two non-negative integers, a and b, such that the equation a^2 +b^2 = c holds true for a given non-negative integer c.

Problem Definition#

Given a non-negative integer c, decide whether there are two integers a and b such that a^2 +b^2 = c

Example 1:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5
Copy

Example 2:

Input: c = 3
Output: false
Copy

Using Efficient Approach 1 (Two-Pointer Approach)#

One efficient way to solve this problem is by using a two-pointer technique. This approach leverages the properties of squares and aims to reduce the number of calculations needed to determine if the condition is met.

def judgeSquareSum(self, c: int) -> bool:
    left = 0
    right = int(c ** (1 / 2))
    while left <= right:
        total = left * left + right * right
        if total == c:
            return True
        elif total > c:
            right -= 1
        else:
            left += 1
    return False
Copy

Explanation#

1. Initialization: We start with two pointers: left initialized to 0 and right initialized to the integer square root of c.
2. While Loop: The loop runs as long as left is less than or equal to right.
3. Calculation: For each iteration, compute the sum of the squares of left and right.
4. Comparison:
   • If the sum equals c, return True.
   • If the sum is greater than c, decrement the right pointer.
   • If the sum is less than c, increment the left pointer.
5. Termination: If no valid pair is found, return False.

Time Complexity: 𝑂(√𝑐) – The algorithm performs a linear scan up to the square root of c.

Space Complexity: O(1) – The algorithm uses a constant amount of extra space.

Using Efficient Approach 2 (Fermat’s Theorem)#

This approach is based on Fermat’s Theorem, which states:

Any positive number n is expressible as a sum of two squares if and only if in the prime factorization of n, every prime of the form 4𝑘 + 3 occurs an even number of times.

By using this theorem, we can directly determine if the given number c can be expressed as a sum of two squares.

Algorithm#

1. Find all prime factors of the given number c, which could range from [2,√𝑐], along with the count of those factors, by repeated division.
2. If at any step, we find that the number of occurrences of any prime factor of the form 4𝑘 + 3 is odd, return False.
3. If c itself is a prime number and of the form 4𝑘 + 3, return False.
4. Otherwise, return True.

The proof of this theorem includes the knowledge of advanced mathematics and is beyond the scope of this article. However, interested reader can refer to this documentation.

def judgeSquareSum(self, c: int) -> bool:
    i = 2
    while i * i <= c:
        count = 0
        if c % i == 0:
            while c % i == 0:
                count += 1
                c //= i
            if count % 2 and i % 4 == 3:
                return False
        i += 1
    return c % 4 != 3
Copy

Explanation#

1. Initialization: Start with i initialized to 2.
2. While Loop: The loop runs as long as i * i is less than or equal to c.
3. Prime Factorization: For each i, count how many times i divides c.
4. Validation:
   • If i % 4 == 3 and the count of i is odd, return False.
5. Termination: After processing all factors, check if the remaining c is of the form 4𝑘 + 3. If so, return False; otherwise, return True.

Time complexity : O(√c x log⁡c). We find the factors of c and their count using repeated division. We check for the factors in the range [0,√c]. The maximum number of times a factor can occur (repeated division can be done) is log⁡n(considering 2 as the only factor, c=2^x. Thus, x=log⁡c).

Space complexity : O(1). Constant space is used.

Conclusion#

In this post, we explored two efficient approaches to determine if a given non-negative integer can be expressed as the sum of two square numbers. The two-pointer technique and the approach based on Fermat’s Theorem both provide efficient solutions with their unique advantages.

Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series#

A LeetCode Daily Series — Day 79 | Ritesh Shakya riteshakya.com.np

Today’s problem is called "Most Profit Assigning Work"