Count Distinct Integers After Reverse Operations

You are given an array nums of positive integers. For each number, reverse its digits and add the result to the end of the array. Return the number of distinct integers in the final array. This is LeetCode 2442.

Example 1

Input: nums = [1, 13, 10, 12, 31] Output: 6 Explanation: the reversed numbers are 1, 31, 1, 21 and 13 (10 reversed is 01, which is 1). The distinct values are 1, 10, 12, 13, 21 and 31.

Example 2

Input: nums = [2, 2, 2] Output: 1

How to Think About It

Step 1: No need to build the longer array

We only need to count distinct values, not keep the array. Put every original number and every reversed number into a HashSet; its size is the answer.

Step 2: Reverse a number with arithmetic

Take digits off the end of x and put them on the end of r:

x % 10 is the last digit of x;
r * 10 + digit appends it to r;
x / 10 removes it from x.

Leading zeros vanish on their own: 10 reverses to 0 × 10 + 1 = 1.

Step 3: Why a set

Checking each new value against all the others would take O(n²). A HashSet ignores repeats on its own and answers "seen before?" in O(1) on average, so the whole job is one pass.

Walkthrough

nums = [1, 13, 10, 12, 31].

Number	Reversed	Set after
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}

The set has 6 values.

Java Solution

The digit reversal uses only integer arithmetic, with no conversion to String.

Java

import java.util.HashSet;
import java.util.Set;

public class CountDistinctIntegersAfterReverseOperations {

    public static int countDistinctIntegers(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            seen.add(x);
            seen.add(reverse(x));
        }
        return seen.size();
    }

    private static int reverse(int x) {
        int r = 0;
        while (x > 0) {
            r = r * 10 + x % 10;              // move the last digit of x to the end of r
            x /= 10;
        }
        return r;
    }

    public static void main(String[] args) {
        System.out.println(countDistinctIntegers(new int[] {1, 13, 10, 12, 31}));   // 6
        System.out.println(countDistinctIntegers(new int[] {2, 2, 2}));             // 1
    }
}

Complexity

Time: O(n × d), where d is the number of digits (at most 7 for values up to 10⁶).
Space: O(n) for the set.

Reversing digits this way is also the core of Palindrome Number.