Count Number of Distinct Integers After Reverse Operations

Medium

Google

6 views

Topics:

ArraysStringsTwo Pointers

You are given an array nums consisting of positive integers.

You have to take each integer in the array, reverse its digits, and add it to the end of the array. You should apply this operation to the original integers in nums.

Return the number of distinct integers in the final array.

Example 1:

Input: nums = [1,13,10,12,31]
Output: 6
Explanation: After including the reverse of each number, the resulting array is [1,13,10,12,31,1,31,1,21,13].
The reversed integers that were added to the end of the array are underlined. Note that for the integer 10, after reversing it, it becomes 01 which is just 1.
The number of distinct integers in this array is 6 (The numbers 1, 10, 12, 13, 21, and 31).

Example 2:

Input: nums = [2,2,2]
Output: 1
Explanation: After including the reverse of each number, the resulting array is [2,2,2,2,2,2].
The number of distinct integers in this array is 1 (The number 2).

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Try coding it in LeetCode

Count Number of Distinct Integers After Reverse Operations

Medium

Google

6 views

Topics:

ArraysStringsTwo Pointers

You are given an array nums consisting of positive integers.

You have to take each integer in the array, reverse its digits, and add it to the end of the array. You should apply this operation to the original integers in nums.

Return the number of distinct integers in the final array.

Example 1:

Input: nums = [1,13,10,12,31]
Output: 6
Explanation: After including the reverse of each number, the resulting array is [1,13,10,12,31,1,31,1,21,13].
The reversed integers that were added to the end of the array are underlined. Note that for the integer 10, after reversing it, it becomes 01 which is just 1.
The number of distinct integers in this array is 6 (The numbers 1, 10, 12, 13, 21, and 31).

Example 2:

Input: nums = [2,2,2]
Output: 1
Explanation: After including the reverse of each number, the resulting array is [2,2,2,2,2,2].
The number of distinct integers in this array is 1 (The number 2).

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

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 range of values for the integers in the input array?
Can the input array contain negative numbers or zero?
Are there any duplicate numbers in the initial input array, and if so, how should they be handled after the reverse operation?
Should I handle the case where the reversed number results in leading zeros? (e.g., reversing 120 should result in 21, not 021)
Is there a specific data type expected for the returned count, or should I just return an integer?

Brute Force Solution

Approach

The basic idea is to go through each number we're given, reverse it, and then compare it with all the other numbers to see how many different ones we have. We're doing this in a simple, straightforward way without trying to be clever or efficient.

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

Take the first number.
Reverse the digits of that number.
Now, check if this reversed number is already in our list of distinct numbers we've found so far.
If it's not, add it to the list.
Repeat this process for the rest of the numbers in the original list: reverse them and see if they're already in our list of distinct numbers.
After processing all the numbers, count how many numbers are in our distinct numbers list. That's the answer.

Code Implementation

def count_distinct_integers_after_reverse_operations(numbers):
    distinct_numbers = []

    for number in numbers:
        # Convert the number to a string to easily reverse it
        number_string = str(number)
        reversed_number_string = number_string[::-1]
        reversed_number = int(reversed_number_string)

        # Check if the reversed number is already in the list
        if reversed_number not in distinct_numbers:

            # Only add if the reversed number is new to the list
            distinct_numbers.append(reversed_number)

    original_numbers = []

    for number in numbers:
        # Avoid duplicates from original numbers
        if number not in original_numbers:
            original_numbers.append(number)

    # Combine the distinct reversed numbers with the originals
    combined_numbers = distinct_numbers + original_numbers

    distinct_set = set(combined_numbers)

    # Get the count of the distinct numbers in the set
    distinct_count = len(distinct_set)
    return distinct_count

Big(O) Analysis

Time Complexity

O(n²) – The provided approach iterates through each of the n numbers in the input array. For each number, it reverses the digits, which takes time proportional to the number of digits (we'll assume this is constant for the sake of overall complexity). Then, it checks if the reversed number already exists in the list of distinct numbers. In the worst case, this check requires iterating through the entire distinct numbers list, which can grow up to size n. Thus, for each of the n input numbers, we potentially perform an O(n) operation to check for distinctness, leading to a total time complexity of O(n * n) or O(n²).

Space Complexity

O(N) – The algorithm maintains a list of distinct integers found after reversing each number. In the worst case, all N input numbers are distinct after reversal, so the list can grow to a size of N. Therefore, the auxiliary space used to store this list of distinct numbers is proportional to the number of input integers, N, leading to a space complexity of O(N).

Optimal Solution

Approach

The most efficient way to solve this problem is to focus on the distinct integers we encounter. We can leverage a simple data structure to keep track of these distinct integers, eliminating redundant calculations and comparisons.

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

First, create a container to store the distinct integers we find.
Go through each number in the original list of integers.
Add the original integer to our container.
Now, reverse the digits of the current integer.
Add the reversed integer to the same container.
After processing all numbers, the number of items in the container represents the total number of distinct integers.

Code Implementation

def count_distinct_integers(numbers):
    distinct_integers = set()

    for number in numbers:
        # Adding original number to set.
        distinct_integers.add(number)

        number_string = str(number)
        reversed_string = number_string[::-1]
        reversed_number = int(reversed_string)

        # Adding the reversed number to set.
        distinct_integers.add(reversed_number)

    # The size of the set corresponds to distinct integer count.
    return len(distinct_integers)

Big(O) Analysis

Time Complexity

O(n*k) – We iterate through each of the n numbers in the input array. Inside the loop, we reverse each number. Reversing a number takes time proportional to the number of digits k in that number, where k is the maximum number of digits in an integer. Adding elements to the set takes approximately O(1) on average. Thus, for each of the n elements, we perform an O(k) operation. Therefore, the overall time complexity is O(n*k).

Space Complexity

O(N) – The algorithm uses a container (like a set or hash table) to store distinct integers. In the worst-case scenario, where all the original integers and their reversed counterparts are distinct, the container will store up to 2N integers, where N is the number of integers in the input list. Therefore, the auxiliary space used scales linearly with the input size N. This means the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty, as there are no numbers to process.
Array with only one element	Return 1 if the array has only one element, as reversing it won't create a new distinct element.
Array with maximum allowed size (e.g., 10^4 or 10^5)	Ensure the chosen data structures and algorithm (e.g., using a HashSet) provide efficient lookup and insertion to avoid exceeding time limits.
Array containing only identical numbers	The reversed number will be the same, so the distinct count should be 1.
Numbers with trailing zeros (e.g., 10, 100, 1000)	Reversing such numbers will remove the trailing zeros, which needs to be accounted for in the comparison to determine distinct count.
Large integer values that could lead to overflow after reversal	Use a larger data type (e.g., long) or handle potential overflow during reversal to prevent incorrect results.
Array containing zero	Reversing 0 results in 0, so it should be handled correctly within the distinct count.
Array containing very large numbers close to the maximum integer value, that result in the same reversed integer as another element.	The solution must efficiently determine all reversed numbers and count only distinct values accurately even with close reversed numbers.