Count Number of Distinct Integers After Reverse Operations Interview Question for Google

## Problem: Distinct Integers After Reversing Digits

Given an array `nums` of positive integers, reverse the digits of each integer and add it to the end of the array. Return the number of distinct integers in the final array.

**Example:**

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 number of distinct integers in this array is 6 (The numbers 1, 10, 12, 13, 21, and 31).


## Naive Solution

A straightforward approach is to iterate through the original array, reverse each number, add it to the array, and then count the distinct elements. This involves converting integers to strings for reversal and using a set to track distinct values.

```python
def distinct_integers_naive(nums):
    reversed_nums = []
    for num in nums:
        reversed_num = int(str(num)[::-1])
        reversed_nums.append(reversed_num)
    
    combined_nums = nums + reversed_nums
    return len(set(combined_nums))

Optimal Solution

This solution improves the time complexity by reversing integers directly without string conversions. We'll still use a set to efficiently determine distinct numbers.

def reverse_integer(n):
    reversed_n = 0
    while n > 0:
        reversed_n = reversed_n * 10 + n % 10
        n //= 10
    return reversed_n

def distinct_integers_optimal(nums):
    reversed_nums = [reverse_integer(num) for num in nums]
    combined_nums = nums + reversed_nums
    return len(set(combined_nums))

Big(O) Runtime Analysis

Optimal Solution:

Reversing each integer: The reverse_integer function iterates through the digits of each number. In the worst case, a number can have at most log10(n) digits. Since we do this for n numbers, the time complexity is O(N * log(M)), where N is the number of elements in nums and M is the maximum value in nums
Creating the reversed list: O(N)
Combining the lists: O(N)
Creating a set: O(N)

Therefore, the overall time complexity is O(N * log(M))

Big(O) Space Usage Analysis

Optimal Solution:

reversed_nums list: O(N)
combined_nums list: O(2N) which simplifies to O(N)
The set used to count distinct numbers: In the worst case, all 2N elements could be distinct, leading to a space complexity of O(N).

Therefore, the overall space complexity is O(N).

Edge Cases and Considerations

Numbers with Leading Zeros After Reversal: The problem statement clarifies that leading zeros should be removed after reversing (e.g., 10 becomes 1). The provided code implicitly handles this since integers don't store leading zeros.
Large Numbers: If the reversed number exceeds the maximum integer limit, it could lead to incorrect results or errors. However, the problem constraints limit the input numbers to 10⁶, which keeps the reversed numbers within reasonable bounds.
Empty Input Array: If the input array is empty, the code should return 0 since there are no distinct integers.
Duplicate Numbers: The code correctly handles duplicate numbers by using a set, which only stores unique values.

# Example Usage:
nums1 = [1, 13, 10, 12, 31]
print(f"Distinct integers: {distinct_integers_optimal(nums1)}")  # Output: 6

nums2 = [2, 2, 2]
print(f"Distinct integers: {distinct_integers_optimal(nums2)}")  # Output: 1

nums3 = []
print(f"Distinct integers: {distinct_integers_optimal(nums3)}")  # Output: 0