Count Number of Distinct Integers After Reverse Operations

Count Number of Distinct Integers After Reverse Operations

What is this problem about?

In this coding problem, you are given an array of positive integers. For each integer in the array, you must reverse its digits and add the reversed number to the array. After performing this operation for every original element, you need to return the count of distinct integers in the final collection.

Why is this asked in interviews?

Google uses this problem to test basic simulation skills and the use of Set data structures. It evaluates whether a candidate can correctly implement a reversal algorithm (without necessarily converting to strings) and efficiently find unique elements. It’s a straightforward task that tests attention to detail regarding large numbers and unique counts.

Algorithmic pattern used

The pattern is Simulation with a Hash Set.

1. Initialize a Hash Set with all the numbers from the original array.
2. For each number in the array, calculate its reverse (e.g., using reverse = reverse * 10 + num % 10).
3. Add the reversed number to the Hash Set.
4. The size of the Hash Set is the answer.

Example explanation

Array: [13, 10, 2]

1. Set: {13, 10, 2}
2. Reverse 13: 31. Add to set: {13, 10, 2, 31}
3. Reverse 10: 01 (which is 1). Add to set: {13, 10, 2, 31, 1}
4. Reverse 2: 2. Add to set: {13, 10, 2, 31, 1} (2 is already there). Final Set Size: 5.

Common mistakes candidates make

A common mistake is converting integers to strings to reverse them, which is generally slower than using mathematical operations. Another error is not handling the "10" to "1" case correctly (trailing zeros becoming leading zeros and then disappearing). Some candidates also forget that the original numbers must be counted as well.

Interview preparation tip

Practice reversing integers mathematically. The loop while(n > 0) { res = res * 10 + n % 10; n /= 10; } is a classic snippet that shows you understand how digits are stored in base-10.