Jobs

Interviews

Discussions

Count Symmetric Integers

Easy

Amazon

2 views

Topics:

ArraysStrings

You are given two positive integers low and high.

An integer x consisting of 2 * n digits is symmetric if the sum of the first n digits of x is equal to the sum of the last n digits of x. Numbers with an odd number of digits are never symmetric.

Return the number of symmetric integers in the range [low, high].

For example:

If low = 1 and high = 100, the output should be 9. The symmetric integers are: 11, 22, 33, 44, 55, 66, 77, 88, and 99.
If low = 1200 and high = 1230, the output should be 4. The symmetric integers are: 1203, 1212, 1221, and 1230.

How would you approach this problem efficiently, considering that 1 <= low <= high <= 10^4?

Count Symmetric Integers

Easy

Amazon

2 views

Topics:

ArraysStrings

You are given two positive integers low and high.

Return the number of symmetric integers in the range [low, high].

For example:

If low = 1 and high = 100, the output should be 9. The symmetric integers are: 11, 22, 33, 44, 55, 66, 77, 88, and 99.
If low = 1200 and high = 1230, the output should be 4. The symmetric integers are: 1203, 1212, 1221, and 1230.

How would you approach this problem efficiently, considering that 1 <= low <= high <= 10^4?

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 range of values for the input numbers `low` and `high`?
Are `low` and `high` inclusive or exclusive in determining the range of integers to consider?
How should I handle the case where `low` is greater than `high`?
Should I consider leading zeros when determining if a number is symmetric (e.g., is '0110' a valid symmetric integer)?
For a number to be considered symmetric, does it *have* to have an even number of digits?

Brute Force Solution

Approach

The brute force approach to counting symmetric integers involves checking every single number within the given range. For each number, we determine if it's symmetric based on a specific rule: If the sum of the digits in the first half of the number equals the sum of the digits in the second half, the number is symmetric.

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

Start by looking at the first number in the range.
Figure out how many digits this number has.
Split the number in half. If the number has an odd number of digits, it's not symmetric so skip ahead.
Add up all the digits in the first half of the number.
Add up all the digits in the second half of the number.
If the sum of the first half equals the sum of the second half, mark this number as symmetric.
Move on to the next number in the range and repeat the process from step 2.
Continue doing this for every number in the range.
Finally, count how many numbers were marked as symmetric. That count is the answer.

Code Implementation

def count_symmetric_integers_brute_force(low, high):
    symmetric_integer_count = 0

    for current_number in range(low, high + 1):
        number_string = str(current_number)
        number_length = len(number_string)

        # Symmetric integers must have an even number of digits
        if number_length % 2 != 0:
            continue

        half_length = number_length // 2
        first_half = number_string[:half_length]
        second_half = number_string[half_length:]

        first_half_sum = 0
        for digit in first_half:
            first_half_sum += int(digit)

        second_half_sum = 0
        for digit in second_half:
            second_half_sum += int(digit)

        # Check if the number is symmetric based on the sums
        if first_half_sum == second_half_sum:
            symmetric_integer_count += 1

    return symmetric_integer_count

Big(O) Analysis

Time Complexity

O(n*log(b)) – The algorithm iterates through each number within the range [low, high], where n = high - low + 1. For each number, the algorithm determines the number of digits (logarithmic complexity with base 10 which we can treat as base b since it will just change by a constant factor). The algorithm then computes the sum of the digits in the first and second halves which is bounded by the number of digits. Therefore, the time complexity for each number is log(b), resulting in a total time complexity of O(n*log(b)).

Space Complexity

O(1) – The algorithm iterates through a range of numbers but doesn't create any data structures that scale with the size of the range. It only uses a few integer variables to store the current number being checked, the digit sums of the two halves, and a counter for symmetric numbers. Therefore, the auxiliary space used is constant and does not depend on the input range, resulting in O(1) space complexity.

Optimal Solution

Approach

To efficiently count symmetric integers within a range, we first need to define what makes an integer symmetric. Then, instead of checking every number in the range individually, we will identify patterns and constraints that allow us to quickly recognize or generate symmetric numbers, significantly reducing the number of checks needed.

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

First, determine the number of digits the integers in the range could have, as symmetry depends on this.
For each possible number of digits (e.g., two-digit, three-digit, etc.), figure out how to construct symmetric numbers.
To construct, think about how each half of the number must relate to the other. For even length, the left half is related to the right, and for odd, the middle digit is by itself.
Build symmetric numbers by intelligently generating the 'left half' and then mirroring or relating it to the 'right half'.
As you generate the symmetric number, make sure it falls within the given range. If it doesn't, discard it. Avoid generating numbers outside the range.
Keep a count of all the symmetric numbers you find within the range.
Finally, return the total count.

Code Implementation

def count_symmetric_integers(low_range, high_range):
    symmetric_count = 0

    for number in range(low_range, high_range + 1):
        number_string = str(number)
        number_length = len(number_string)

        # Symmetry requires at least two digits
        if number_length < 2:
            continue

        if number_length % 2 == 0:
            # Check for even-length symmetry
            left_half = number_string[:number_length // 2]
            right_half = number_string[number_length // 2:]
            if left_half == right_half[::-1]:
                symmetric_count += 1
        else:
            # Odd length numbers cannot be symmetric.
            continue

    return symmetric_count

Big(O) Analysis

Time Complexity

O(sqrt(high)) – The algorithm iterates through possible number of digits (up to the number of digits in the high bound). The dominant cost comes from generating symmetric numbers. The number of symmetric numbers we generate and check is related to the square root of the higher bound because we construct numbers by generating a 'left half' and mirroring it or relating it to the right half. Thus, the number of generated candidates scales roughly with the square root of 'high'. Therefore, the time complexity is O(sqrt(high)).

Space Complexity

O(1) – The described algorithm primarily utilizes a constant number of integer variables for digit counts, constructing symmetric numbers, and tracking the count of symmetric integers. The generation of symmetric numbers involves creating intermediate numbers, but these operations occur within a fixed range determined by the maximum number of digits (which is small), leading to constant space usage. No auxiliary data structures like arrays or hash maps that scale with the input range are employed. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
low > high	Return 0 immediately as the input range is invalid.
low == high and low is a symmetric number	Return 1 if low is a symmetric number, otherwise 0.
low and high are single-digit numbers	Return 0 because no single-digit number is symmetric according to the problem definition.
low is a single-digit number and high is a two-digit or larger number.	Start the iteration from 11 (smallest two digit symmetric integer) if low is less than 11.
Integer overflow when reversing a large number	Use a data type that can accommodate larger values or handle overflow appropriately (e.g., use long or check for overflow during reversal).
Input range contains leading zeros	The definition in the prompt implies that we're given integers, and integer data types don't have leading zeroes, thus, not an issue.
All numbers within the range are not symmetric	The algorithm should correctly iterate through the range and return 0 if no symmetric numbers are found.
Maximum possible values for low and high (close to Integer.MAX_VALUE)	Ensure the reversal and comparison logic doesn't cause integer overflow or incorrect results at the boundaries.

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 range of values for the input numbers `low` and `high`?
Are `low` and `high` inclusive or exclusive in determining the range of integers to consider?
How should I handle the case where `low` is greater than `high`?
Should I consider leading zeros when determining if a number is symmetric (e.g., is '0110' a valid symmetric integer)?
For a number to be considered symmetric, does it *have* to have an even number of digits?

Brute Force Solution

Approach

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

Start by looking at the first number in the range.
Figure out how many digits this number has.
Split the number in half. If the number has an odd number of digits, it's not symmetric so skip ahead.
Add up all the digits in the first half of the number.
Add up all the digits in the second half of the number.
If the sum of the first half equals the sum of the second half, mark this number as symmetric.
Move on to the next number in the range and repeat the process from step 2.
Continue doing this for every number in the range.
Finally, count how many numbers were marked as symmetric. That count is the answer.

Code Implementation

def count_symmetric_integers_brute_force(low, high):
    symmetric_integer_count = 0

    for current_number in range(low, high + 1):
        number_string = str(current_number)
        number_length = len(number_string)

        # Symmetric integers must have an even number of digits
        if number_length % 2 != 0:
            continue

        half_length = number_length // 2
        first_half = number_string[:half_length]
        second_half = number_string[half_length:]

        first_half_sum = 0
        for digit in first_half:
            first_half_sum += int(digit)

        second_half_sum = 0
        for digit in second_half:
            second_half_sum += int(digit)

        # Check if the number is symmetric based on the sums
        if first_half_sum == second_half_sum:
            symmetric_integer_count += 1

    return symmetric_integer_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, determine the number of digits the integers in the range could have, as symmetry depends on this.
For each possible number of digits (e.g., two-digit, three-digit, etc.), figure out how to construct symmetric numbers.
To construct, think about how each half of the number must relate to the other. For even length, the left half is related to the right, and for odd, the middle digit is by itself.
Build symmetric numbers by intelligently generating the 'left half' and then mirroring or relating it to the 'right half'.
As you generate the symmetric number, make sure it falls within the given range. If it doesn't, discard it. Avoid generating numbers outside the range.
Keep a count of all the symmetric numbers you find within the range.
Finally, return the total count.

Code Implementation

def count_symmetric_integers(low_range, high_range):
    symmetric_count = 0

    for number in range(low_range, high_range + 1):
        number_string = str(number)
        number_length = len(number_string)

        # Symmetry requires at least two digits
        if number_length < 2:
            continue

        if number_length % 2 == 0:
            # Check for even-length symmetry
            left_half = number_string[:number_length // 2]
            right_half = number_string[number_length // 2:]
            if left_half == right_half[::-1]:
                symmetric_count += 1
        else:
            # Odd length numbers cannot be symmetric.
            continue

    return symmetric_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
low > high	Return 0 immediately as the input range is invalid.
low == high and low is a symmetric number	Return 1 if low is a symmetric number, otherwise 0.
low and high are single-digit numbers	Return 0 because no single-digit number is symmetric according to the problem definition.
low is a single-digit number and high is a two-digit or larger number.	Start the iteration from 11 (smallest two digit symmetric integer) if low is less than 11.
Integer overflow when reversing a large number	Use a data type that can accommodate larger values or handle overflow appropriately (e.g., use long or check for overflow during reversal).
Input range contains leading zeros	The definition in the prompt implies that we're given integers, and integer data types don't have leading zeroes, thus, not an issue.
All numbers within the range are not symmetric	The algorithm should correctly iterate through the range and return 0 if no symmetric numbers are found.
Maximum possible values for low and high (close to Integer.MAX_VALUE)	Ensure the reversal and comparison logic doesn't cause integer overflow or incorrect results at the boundaries.