LeetCode 2442 - Count Number of Distinct Integers After Reverse Operations

The problem asks us to compute the number of distinct integers in an array after performing a specific operation on each element: reversing its digits and adding it to the array. In other words, for every integer in nums, we generate its reverse and append it.

leetcodemediumarrayhash-tablemathcounting

LeetCode Problem 2442

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Counting

Solution

Problem Understanding

The problem asks us to compute the number of distinct integers in an array after performing a specific operation on each element: reversing its digits and adding it to the array. In other words, for every integer in nums, we generate its reverse and append it. After processing all original elements, we count how many unique numbers are present in the resulting array.

The input nums is an array of positive integers, and the output is a single integer representing the count of distinct numbers. The constraints tell us that the array can have up to $10^5$ elements, and each integer can be as large as $10^6$. This implies that any solution iterating over nums multiple times or performing expensive operations for every number may become inefficient. Edge cases include arrays with repeated numbers, numbers that become the same after reversal (e.g., 10 reversed becomes 1), and single-element arrays.

Approaches

A brute-force approach would be to explicitly create a new array containing all original elements and their reversed forms, and then use a set to find distinct numbers. This works correctly because sets inherently remove duplicates, but it is not optimal because it creates additional arrays, increasing memory usage and performing unnecessary insertions.

The key observation for an optimal solution is that we do not need to maintain the full array. We only need to track distinct numbers, which can be efficiently done using a hash set. For each number in nums, we insert both the number itself and its reversed form into the set. This guarantees that all numbers we care about are tracked without constructing a larger array.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) for reversal + O(n) for set O(2n) Explicitly builds a larger array with original and reversed numbers
Optimal O(n log m) O(n) Uses a set to track distinct numbers while reversing digits on the fly, where m is the max number of digits

Algorithm Walkthrough

  1. Initialize an empty hash set called distinct_numbers to store unique values.
  2. Iterate over each number num in the input array nums.
  3. For each num, insert it into the distinct_numbers set. This ensures the original number is counted.
  4. Reverse the digits of num. This can be done by repeatedly extracting the last digit and constructing the reversed number.
  5. Insert the reversed number into the distinct_numbers set.
  6. After processing all numbers, the size of distinct_numbers represents the number of distinct integers in the final array. Return this count.

Why it works: The hash set guarantees uniqueness automatically, and we are systematically adding both the original and reversed numbers. No number is omitted, and duplicates are ignored, ensuring the count is correct.

Python Solution

from typing import List

class Solution:
    def countDistinctIntegers(self, nums: List[int]) -> int:
        distinct_numbers = set()
        
        for num in nums:
            distinct_numbers.add(num)
            
            reversed_num = 0
            temp = num
            while temp > 0:
                reversed_num = reversed_num * 10 + temp % 10
                temp //= 10
            
            distinct_numbers.add(reversed_num)
        
        return len(distinct_numbers)

The Python solution iterates over each number in the input array. For every number, we compute its reversed form manually using integer arithmetic. Both the original and reversed numbers are added to a set, which handles duplicates automatically. Finally, we return the number of elements in the set.

Go Solution

func countDistinctIntegers(nums []int) int {
    distinctNumbers := make(map[int]struct{})

    for _, num := range nums {
        distinctNumbers[num] = struct{}{}

        reversedNum := 0
        temp := num
        for temp > 0 {
            reversedNum = reversedNum*10 + temp%10
            temp /= 10
        }

        distinctNumbers[reversedNum] = struct{}{}
    }

    return len(distinctNumbers)
}

In Go, we use a map with empty struct values to emulate a set. The reversing logic is identical to Python, using integer arithmetic. We handle slices safely and do not need to worry about nil slices since iterating over an empty slice works correctly.

Worked Examples

Example 1: nums = [1,13,10,12,31]

num reversed_num distinct_numbers set
1 1 {1}
13 31 {1, 13, 31}
10 1 {1, 10, 13, 31}
12 21 {1, 10, 12, 13, 21, 31}
31 13 {1, 10, 12, 13, 21, 31}

Final count = 6

Example 2: nums = [2,2,2]

num reversed_num distinct_numbers set
2 2 {2}
2 2 {2}
2 2 {2}

Final count = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n * d) n is the number of elements, d is the number of digits in each number (max 6), reversing each number takes O(d)
Space O(n) Storing all distinct numbers in a set or map

Since d is at most 6, O(n * d) is effectively O(n), which is acceptable for n up to $10^5$.

Test Cases

# Provided examples
assert Solution().countDistinctIntegers([1,13,10,12,31]) == 6  # mix of reversals and original numbers
assert Solution().countDistinctIntegers([2,2,2]) == 1           # all duplicates

# Edge cases
assert Solution().countDistinctIntegers([1]) == 1               # single element
assert Solution().countDistinctIntegers([10,100,1000]) == 6     # reversals create new numbers
assert Solution().countDistinctIntegers([121,12,21]) == 3      # reversals match existing numbers
assert Solution().countDistinctIntegers([123456,654321]) == 2  # large numbers, reversals
Test Why
[1,13,10,12,31] Tests mixed numbers and reversals
[2,2,2] Tests repeated numbers
[1] Single element edge case
[10,100,1000] Numbers whose reversals remove zeros
[121,12,21] Reversals can match other numbers
[123456,654321] Large numbers near upper constraint

Edge Cases

One edge case is when all numbers are the same, e.g., [2,2,2]. The algorithm correctly handles duplicates because the set automatically ignores repeated inserts.

Another edge case is numbers ending with zero, such as 10 or 100. When reversed, leading zeros disappear, e.g., 10 becomes 1. The algorithm correctly handles this by constructing the reversed integer numerically, not as a string.

A third edge case is single-element arrays, such as [1]. The set will correctly contain the number and its reversal, which is the same as the original, resulting in a count of 1. This ensures the algorithm is robust for minimal input sizes.