Problem Description

You start with an array nums containing positive integers. Your task is to process each integer in the original array by reversing its digits and adding the reversed number to the end of the array.

For example, if you have the number 123, reversing its digits gives you 321. This reversed number would be added to the array.

The process works as follows:

• Take each integer from the original array
• Reverse its digits (e.g., 123 becomes 321, 100 becomes 1)
• Add the reversed integer to the end of the array
• Count how many distinct (unique) integers exist in the final array after all reversals are added

The solution uses a set to track unique integers. It starts by adding all original numbers to the set, then for each number, it reverses the digits by converting to string (str(x)), reversing the string ([::-1]), and converting back to integer (int()). The reversed number is added to the set. Since sets automatically handle duplicates, the final size of the set gives us the count of distinct integers.

For instance, if nums = [1, 13, 10, 12, 31], after adding reversed numbers, we'd have [1, 13, 10, 12, 31, 1, 31, 1, 21, 13] (conceptually). The distinct integers are {1, 10, 12, 13, 21, 31}, so the answer would be 6.

Intuition

The key insight is that we need to count distinct integers, not track their positions or order. When counting unique elements, a set is the natural data structure choice since it automatically handles duplicates for us.

We could simulate the actual array extension process - literally adding reversed numbers to the end of the array and then counting unique values. However, since we only care about the count of distinct integers, we don't need to maintain the actual expanded array. We just need to know which unique values would exist in it.

The approach becomes clear when we realize:

1. All original numbers will be in the final array (they're already there)
2. All reversed numbers will also be in the final array (we add them)
3. Some reversed numbers might be duplicates of existing numbers (like 121 reverses to 121)
4. Some reversed numbers might duplicate each other (if 13 and 31 are both in the original array, they produce each other when reversed)

By using a set and adding both original and reversed numbers to it, we let the set's property of storing only unique values handle all the duplicate cases automatically. The string reversal technique str(x)[::-1] is a simple way to reverse digits without complex mathematical operations like extracting digits one by one using modulo and division.

This transforms the problem from "build an array and count distinct elements" to simply "collect all unique values that would appear" - a much more efficient approach.

Learn more about Math patterns.

Solution Approach

The solution uses a hash table (set) to efficiently track distinct integers. Here's the step-by-step implementation:

1. Initialize a set with original numbers:

   s = set(nums)

   This immediately stores all unique integers from the original array. If nums = [1, 2, 2, 3], the set s would contain {1, 2, 3}.

2. Iterate through each number and reverse it:

   for x in nums:
       y = int(str(x)[::-1])
       s.add(y)

   For each integer x in the original array:

   • Convert it to a string: str(x)
   • Reverse the string using slicing: [::-1]
   • Convert back to integer: int(...)
   • Add the reversed integer to the set

   The digit reversal process works as follows:

   • 123 → "123" → "321" → 321
   • 100 → "100" → "001" → 1

3. Return the count of distinct integers:

   return len(s)

   The size of the set gives us the total number of distinct integers.

The beauty of using a set is that it automatically handles all duplicate scenarios:

• If a reversed number already exists in the set (either from the original array or from a previous reversal), add() simply does nothing
• The time complexity is O(n) where n is the length of the array, as we iterate through each element once
• The space complexity is O(n) for storing the set of distinct integers

Example Walkthrough

Let's walk through a small example with nums = [21, 13, 4].

Step 1: Initialize the set with original numbers

• Start with s = {21, 13, 4}
• These are all the unique integers from the original array

Step 2: Process each number and add its reversal

First iteration (x = 21):

• Convert to string: "21"
• Reverse the string: "12"
• Convert back to integer: 12
• Add to set: s = {21, 13, 4, 12}

Second iteration (x = 13):

• Convert to string: "13"
• Reverse the string: "31"
• Convert back to integer: 31
• Add to set: s = {21, 13, 4, 12, 31}

Third iteration (x = 4):

• Convert to string: "4"
• Reverse the string: "4" (single digit stays the same)
• Convert back to integer: 4
• Add to set: s = {21, 13, 4, 12, 31} (4 already exists, so no change)

Step 3: Count distinct integers

• Final set: {21, 13, 4, 12, 31}
• Return len(s) = 5

The conceptual final array would be [21, 13, 4, 12, 31, 4], which contains 5 distinct integers. Notice how the set automatically handled the duplicate 4 without us needing to check for it explicitly.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × m), where n is the length of the array and m is the average number of digits in each element. Converting an integer to a string takes O(m) time, reversing the string takes O(m) time, and converting back to an integer takes O(m) time. Since we perform these operations for each of the n elements, the total time complexity is O(n × m). However, if we consider m to be bounded by a constant (since integers have a maximum number of digits in practice), we can simplify this to O(n).

The space complexity is O(n). The set s can contain at most 2n elements (original numbers plus their reversed versions), which is O(n). The string conversion creates temporary strings of length m for each element, but these are not stored simultaneously, so they don't add to the overall space complexity beyond O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Trailing Zeros

One of the most common mistakes is not understanding how digit reversal handles trailing zeros. When reversing a number like 100, students often forget that it becomes 1, not 001.

Incorrect assumption:

# Some might think 100 reversed stays as a 3-digit number
# 100 -> "001" -> they expect 001 as output

Why this happens: The conversion int("001") automatically removes leading zeros, resulting in 1. This is actually the correct behavior, but it can cause confusion when manually tracing through examples.

Solution: Remember that int() conversion always removes leading zeros from string representations.

2. Using List Instead of Set

A critical mistake is using a list to track distinct numbers and manually checking for duplicates:

Incorrect approach:

def countDistinctIntegers(self, nums: List[int]) -> int:
    result = []
    for num in nums:
        if num not in result:  # O(n) operation each time!
            result.append(num)
        reversed_num = int(str(num)[::-1])
        if reversed_num not in result:  # Another O(n) operation!
            result.append(reversed_num)
    return len(result)

Problem: This creates O(n²) time complexity because checking membership in a list is O(n) for each element.

Solution: Always use a set for tracking unique elements, as membership checking and insertion are O(1) operations.

3. Modifying the Original Array

Some might interpret "adding to the end of the array" literally and try to modify the input:

Incorrect approach:

def countDistinctIntegers(self, nums: List[int]) -> int:
    original_length = len(nums)
    for i in range(original_length):  # Only iterate original length
        reversed_num = int(str(nums[i])[::-1])
        nums.append(reversed_num)  # Modifying during iteration
    return len(set(nums))

Problem: While this might work, it unnecessarily modifies the input array and uses extra space. Also, iterating while modifying can lead to unexpected behavior if not careful with loop bounds.

Solution: Use a separate set to track distinct values without modifying the original input.

4. Edge Case: Single-Digit Numbers

Overlooking that single-digit numbers reverse to themselves (e.g., 5 reversed is still 5):

What to remember:

• Numbers like 1, 2, ..., 9 remain unchanged when reversed
• This means they won't add any new distinct integers to the count
• The solution handles this automatically since sets ignore duplicates

5. Integer Overflow Concerns

In some languages, reversing large integers might cause overflow:

Example scenario:

# In Python, this isn't an issue due to arbitrary precision
# But in languages like Java/C++, reversing 2147483647 could overflow

Solution for other languages: Check constraints and handle overflow if necessary. Python handles arbitrary precision integers automatically, so this isn't a concern here.