Count Number of Distinct Integers After Reverse Operations

medium hashing hash set digit reversal

Problem

You are given an array nums of positive integers. For each integer in the array, reverse its digits and append the result to the end of the array. Apply this only to the original integers. Return the number of distinct integers in the final array.

Inputnums = [1,13,10,12,31]

Output6

Reversals appended: 1, 31, 1, 21, 13 (10 reversed is 01 = 1). The full array holds the distinct values {1, 10, 12, 13, 21, 31} → 6.

Inputnums = [2,2,2]

Output1

Every value and every reversal is 2, so only one distinct integer remains.

nums (comma-separated)

def count_distinct(nums):
    seen = set()
    for v in nums:
        seen.add(v)
        rev = int(str(v)[::-1])
        seen.add(rev)
    return len(seen)

function countDistinct(nums) {
  const seen = new Set();
  for (const v of nums) {
    seen.add(v);
    const rev = Number(String(v).split("").reverse().join(""));
    seen.add(rev);
  }
  return seen.size;
}

int countDistinct(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int v : nums) {
        seen.add(v);
        int rev = 0, t = v;
        while (t > 0) { rev = rev * 10 + t % 10; t /= 10; }
        seen.add(rev);
    }
    return seen.size();
}

int countDistinct(vector<int>& nums) {
    unordered_set<int> seen;
    for (int v : nums) {
        seen.insert(v);
        int rev = 0, t = v;
        while (t > 0) { rev = rev * 10 + t % 10; t /= 10; }
        seen.insert(rev);
    }
    return seen.size();
}

Explanation

We never actually have to build the appended array. The question only asks how many distinct values the final array contains, so a hash set is the perfect tool: insert every value you would have placed in the array, and the set automatically discards duplicates.

Walk through each original number v. Add v itself to the set seen, then compute its digit reversal rev and add that too. Reversing throws away leading zeros: 10 reversed is 01, which as an integer is just 1.

In Python and JavaScript the reversal is a one-liner on the string form of the number. In Java and C++ we peel digits with rev = rev * 10 + t % 10 while t /= 10, which is the standard integer way to reverse and naturally drops leading zeros.

Because a set rejects repeats, an already-seen value (or reversal) simply does nothing when added. After processing all numbers, the answer is just the size of the set.

For [1,13,10,12,31] the inserts are 1, 1, 13, 31, 10, 1, 12, 21, 31, 13. The distinct survivors are {1, 10, 12, 13, 21, 31}, so the answer is 6.

Time: O(n · d) Space: O(n)