Jobs

Interviews

Discussions

Sum of Square Numbers

Medium

Asked by:

More companies

59 views

Topics:

Two PointersBinary Search

Given a non-negative integer c, decide whether there're two integers a and b such that a² + b² = c.

Example 1:

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

Example 2:

Input: c = 3
Output: false

Constraints:

0 <= c <= 2³¹ - 1

Try coding it in LeetCode

Sum of Square Numbers

Medium

Asked by:

59 views

Topics:

Two PointersBinary Search

Given a non-negative integer c, decide whether there're two integers a and b such that a² + b² = c.

Example 1:

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

Example 2:

Input: c = 3
Output: false

Constraints:

0 <= c <= 2³¹ - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the non-negative integer 'c'?
Can 'c' be zero?
If multiple pairs (a, b) satisfy the equation a^2 + b^2 = c, do I need to return all such pairs, or is it sufficient to return true as soon as I find one?
Are 'a' and 'b' allowed to be the same number?
Should I expect the solution to be performant with very large values of 'c'?

Brute Force Solution

Approach

The brute force approach involves checking all possible pairs of numbers. For each pair, we'll calculate the sum of their squares and see if it matches the given target number. It's like trying every combination until we find one that works.

Here's how the algorithm would work step-by-step:

Start with the smallest possible whole number, zero.
Find another whole number, starting from zero again.
Calculate the square of both numbers and add them together.
Check if the sum is equal to the target number. If it is, we've found a solution!
If the sum is not equal, try the next number in the sequence for the second number.
Keep repeating this process with the second number until we reach the target number itself.
If we haven't found a solution yet, move on to the next number for the first number and repeat all steps with the second number, starting from zero again.
We keep going until both numbers reach the target number or we find a pair that sums to the target number.

Code Implementation

def sum_of_square_numbers_brute_force(target_number):
    first_number = 0

    while first_number <= target_number:
        second_number = 0

        while second_number <= target_number:
            sum_of_squares = (first_number * first_number) + (second_number * second_number)

            if sum_of_squares == target_number:
                return True

            second_number += 1

        # Increment first number to check
        # against all possible second numbers
        first_number += 1

    # If no match is found, return false
    # after exhausting all combinations
    return False

Big(O) Analysis

Time Complexity

O(c) – The brute force approach involves nested loops, with each loop iterating up to the square root of c, where c is the target number. The outer loop iterates from 0 to sqrt(c), and the inner loop also iterates from 0 to sqrt(c). For each pair, we compute the sum of squares. Thus, the number of operations is proportional to sqrt(c) * sqrt(c), which equals c. Therefore, the time complexity is O(c).

Space Complexity

O(1) – The provided brute force approach does not use any auxiliary data structures. It only involves calculations and comparisons using a few variables to hold the current numbers being squared and their sum. The space required for these variables remains constant regardless of the target number's value, N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The problem asks us to determine if a given number can be expressed as the sum of two perfect squares. Instead of checking every possible combination, we'll use a two-pointer approach, starting from opposite ends, to efficiently search for a valid pair.

Here's how the algorithm would work step-by-step:

Imagine two numbers, one starting at the smallest possible square (0) and the other at the largest possible square (the square root of the target number).
Calculate the sum of the squares of these two numbers.
If the sum is equal to the target number, we've found a solution, and we're done.
If the sum is less than the target number, it means we need a larger square, so we increase the smaller number.
If the sum is greater than the target number, it means we need a smaller square, so we decrease the larger number.
Repeat steps 2-5 until the two numbers meet. If we haven't found a solution by then, it means the target number cannot be expressed as the sum of two squares.

Code Implementation

def sum_of_square_numbers(target):
    left_number = 0
    right_number = int(target**0.5)

    while left_number <= right_number:
        sum_of_squares = left_number**2 + right_number**2

        if sum_of_squares == target:
            return True

        # Need a larger sum, increment
        if sum_of_squares < target:

            left_number += 1

        # Need a smaller sum, decrement
        else:

            right_number -= 1

    # Exhausted all possibilities
    return False

Big(O) Analysis

Time Complexity

O(sqrt(c)) – The algorithm uses a two-pointer approach where one pointer starts at 0 and the other at the square root of the input number c. In the worst-case scenario, these pointers will iterate towards each other until they meet. The number of iterations is proportional to the square root of c because the right pointer starts at sqrt(c) and decrements, while the left pointer starts at 0 and increments. Therefore, the time complexity is O(sqrt(c)).

Space Complexity

O(1) – The algorithm uses two variables to represent the two numbers whose squares are summed. These variables, representing the lower and upper bounds, require constant space. The amount of space needed does not depend on the input number N, so the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
c = 0	Handles this correctly as a=0, b=0 is a valid solution; solution should return true.
c = 1	Handles this correctly as a=1, b=0 is a valid solution (or a=0, b=1); solution should return true.
c is a large perfect square (e.g., c = 2147483649 = 46341^2)	The square root calculation should be performed using a double to avoid potential integer overflow, and then convert to long for further calculations to avoid integer overflow on squaring.
c is a number that requires a large 'a' or 'b' to be a valid solution but 'a' and 'b' still fit in integer	The solution should correctly handle cases where a and b are close to the square root of c and within the integer range.
Integer overflow in aa or bb	Use long data type for a and b to prevent overflow in aa + bb, or perform sqrt operation on doubles which is safe.
c is negative	The problem states c is non-negative, but ideally, the code should return false since squares are always non-negative.
No valid integer solution exists	The algorithm must correctly identify when no such 'a' and 'b' exist and return false, such as c = 3.
Floating point precision errors during square root calculation	Avoid using == for checking perfect square of sqrt(c), instead use a tolerance or compare squares directly, ensuring a and b are integers after casting sqrt(c).

c = 0

How to Handle:

Handles this correctly as a=0, b=0 is a valid solution; solution should return true.

c = 1

How to Handle:

Handles this correctly as a=1, b=0 is a valid solution (or a=0, b=1); solution should return true.

c is a large perfect square (e.g., c = 2147483649 = 46341^2)

How to Handle:

The square root calculation should be performed using a double to avoid potential integer overflow, and then convert to long for further calculations to avoid integer overflow on squaring.

c is a number that requires a large 'a' or 'b' to be a valid solution but 'a' and 'b' still fit in integer

How to Handle:

The solution should correctly handle cases where a and b are close to the square root of c and within the integer range.

Integer overflow in a*a or b*b

How to Handle:

Use long data type for a and b to prevent overflow in a*a + b*b, or perform sqrt operation on doubles which is safe.

c is negative

How to Handle:

The problem states c is non-negative, but ideally, the code should return false since squares are always non-negative.

No valid integer solution exists

How to Handle:

The algorithm must correctly identify when no such 'a' and 'b' exist and return false, such as c = 3.

Floating point precision errors during square root calculation

How to Handle:

Avoid using == for checking perfect square of sqrt(c), instead use a tolerance or compare squares directly, ensuring a and b are integers after casting sqrt(c).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the non-negative integer 'c'?
Can 'c' be zero?
If multiple pairs (a, b) satisfy the equation a^2 + b^2 = c, do I need to return all such pairs, or is it sufficient to return true as soon as I find one?
Are 'a' and 'b' allowed to be the same number?
Should I expect the solution to be performant with very large values of 'c'?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the smallest possible whole number, zero.
Find another whole number, starting from zero again.
Calculate the square of both numbers and add them together.
Check if the sum is equal to the target number. If it is, we've found a solution!
If the sum is not equal, try the next number in the sequence for the second number.
Keep repeating this process with the second number until we reach the target number itself.
If we haven't found a solution yet, move on to the next number for the first number and repeat all steps with the second number, starting from zero again.
We keep going until both numbers reach the target number or we find a pair that sums to the target number.

Code Implementation

def sum_of_square_numbers_brute_force(target_number):
    first_number = 0

    while first_number <= target_number:
        second_number = 0

        while second_number <= target_number:
            sum_of_squares = (first_number * first_number) + (second_number * second_number)

            if sum_of_squares == target_number:
                return True

            second_number += 1

        # Increment first number to check
        # against all possible second numbers
        first_number += 1

    # If no match is found, return false
    # after exhausting all combinations
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine two numbers, one starting at the smallest possible square (0) and the other at the largest possible square (the square root of the target number).
Calculate the sum of the squares of these two numbers.
If the sum is equal to the target number, we've found a solution, and we're done.
If the sum is less than the target number, it means we need a larger square, so we increase the smaller number.
If the sum is greater than the target number, it means we need a smaller square, so we decrease the larger number.
Repeat steps 2-5 until the two numbers meet. If we haven't found a solution by then, it means the target number cannot be expressed as the sum of two squares.

Code Implementation

def sum_of_square_numbers(target):
    left_number = 0
    right_number = int(target**0.5)

    while left_number <= right_number:
        sum_of_squares = left_number**2 + right_number**2

        if sum_of_squares == target:
            return True

        # Need a larger sum, increment
        if sum_of_squares < target:

            left_number += 1

        # Need a smaller sum, decrement
        else:

            right_number -= 1

    # Exhausted all possibilities
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
c = 0	Handles this correctly as a=0, b=0 is a valid solution; solution should return true.
c = 1	Handles this correctly as a=1, b=0 is a valid solution (or a=0, b=1); solution should return true.
c is a large perfect square (e.g., c = 2147483649 = 46341^2)	The square root calculation should be performed using a double to avoid potential integer overflow, and then convert to long for further calculations to avoid integer overflow on squaring.
c is a number that requires a large 'a' or 'b' to be a valid solution but 'a' and 'b' still fit in integer	The solution should correctly handle cases where a and b are close to the square root of c and within the integer range.
Integer overflow in aa or bb	Use long data type for a and b to prevent overflow in aa + bb, or perform sqrt operation on doubles which is safe.
c is negative	The problem states c is non-negative, but ideally, the code should return false since squares are always non-negative.
No valid integer solution exists	The algorithm must correctly identify when no such 'a' and 'b' exist and return false, such as c = 3.
Floating point precision errors during square root calculation	Avoid using == for checking perfect square of sqrt(c), instead use a tolerance or compare squares directly, ensuring a and b are integers after casting sqrt(c).

c = 0

How to Handle:

Handles this correctly as a=0, b=0 is a valid solution; solution should return true.

c = 1

How to Handle:

Handles this correctly as a=1, b=0 is a valid solution (or a=0, b=1); solution should return true.

c is a large perfect square (e.g., c = 2147483649 = 46341^2)

How to Handle:

The square root calculation should be performed using a double to avoid potential integer overflow, and then convert to long for further calculations to avoid integer overflow on squaring.

c is a number that requires a large 'a' or 'b' to be a valid solution but 'a' and 'b' still fit in integer

How to Handle:

The solution should correctly handle cases where a and b are close to the square root of c and within the integer range.

Integer overflow in a*a or b*b

How to Handle:

Use long data type for a and b to prevent overflow in a*a + b*b, or perform sqrt operation on doubles which is safe.

c is negative

How to Handle:

The problem states c is non-negative, but ideally, the code should return false since squares are always non-negative.

No valid integer solution exists

How to Handle:

The algorithm must correctly identify when no such 'a' and 'b' exist and return false, such as c = 3.

Floating point precision errors during square root calculation

How to Handle:

Avoid using == for checking perfect square of sqrt(c), instead use a tolerance or compare squares directly, ensuring a and b are integers after casting sqrt(c).