# Count Number of Distinct Integers After Reverse Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-number-of-distinct-integers-after-reverse-operations)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-distinct-integers-after-reverse-operations
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
You are given an array `nums` consisting of **positive** integers.

You have to take each integer in the array, **reverse its digits**, and add it to the end of the array. You should apply this operation to the original integers in `nums`.

Return _the number of **distinct** integers in the final array_.

**Example 1:**

**Input:** nums = [1,13,10,12,31]
**Output:** 6
**Explanation:** After including the reverse of each number, the resulting array is [1,13,10,12,31,1,31,1,21,13].
The reversed integers that were added to the end of the array are underlined. Note that for the integer 10, after reversing it, it becomes 01 which is just 1.
The number of distinct integers in this array is 6 (The numbers 1, 10, 12, 13, 21, and 31).

**Example 2:**

**Input:** nums = [2,2,2]
**Output:** 1
**Explanation:** After including the reverse of each number, the resulting array is [2,2,2,2,2,2].
The number of distinct integers in this array is 1 (The number 2).

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 106`

# Approaches
## Brute Force: Build and Count
This approach literally follows the steps described in the problem. First, we construct the final array by taking the original numbers and appending the reverse of each original number. After the final array is built, we count the number of unique elements within it by converting it to a Set.
**Time:** O(N * M), where N is the number of elements in `nums` and M is the maximum number of digits in a number. We iterate through `nums` (length N) to populate a list. The reversal of each number takes O(M) time. Then we create a set from a list of size 2N, which takes O(N) time. The total time is dominated by the O(N * M) part. Since M is a small constant (at most 7 for numbers up to 10^6), the effective complexity is O(N). · **Space:** O(N), to store the intermediate `finalArray` of size 2N and the `HashSet` which can also store up to 2N elements.
**Pros:** Simple to understand as it directly maps to the problem statement.
**Cons:** Uses extra memory to create an intermediate list (`finalArray`) which is not strictly necessary.; Slightly less efficient due to the overhead of creating and populating the intermediate list before creating the set.
### Explanation
The core idea is to simulate the process exactly as stated. We first create a new list that is large enough to hold both the original numbers and their reversed versions. We populate this list first with the numbers from the input `nums` array. Then, we iterate through `nums` again, and for each number, we compute its digit-reversed counterpart and add it to our list. Finally, to find the number of distinct integers, we leverage a `HashSet`. By adding all elements from our constructed list into a `HashSet`, we automatically filter out duplicates. The size of the resulting set gives us the desired count.
```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    // Helper function to reverse the digits of an integer
    private int reverseInteger(int n) {
        int reversed = 0;
        while (n > 0) {
            int digit = n % 10;
            reversed = reversed * 10 + digit;
            n /= 10;
        }
        return reversed;
    }

    public int countDistinctIntegers(int[] nums) {
        List<Integer> finalArray = new ArrayList<>();
        
        // 1. Add original numbers to the list
        for (int num : nums) {
            finalArray.add(num);
        }
        
        // 2. Add reversed numbers to the list
        for (int num : nums) {
            finalArray.add(reverseInteger(num));
        }
        
        // 3. Count distinct elements using a Set
        Set<Integer> distinctNumbers = new HashSet<>(finalArray);
        
        return distinctNumbers.size();
    }
}
```
### Algorithm
- Initialize a new dynamic array or list, let's call it `finalArray`.
- Iterate through the input `nums` array and add each element to `finalArray`.
- Iterate through the input `nums` array again. For each number:
  - Reverse the digits of the number.
  - Add the reversed number to `finalArray`.
- To count the distinct elements, create a `HashSet` from `finalArray`.
- The size of the `HashSet` is the final answer.

## Optimized Approach: Direct Population using a HashSet
A more efficient approach avoids creating the intermediate large array. We can directly populate a `HashSet` with both the original numbers and their reversed counterparts in a single pass. A `HashSet` automatically handles duplicates, so by the end of the process, its size will give us the count of distinct integers.
**Time:** O(N * M), where N is the length of `nums` and M is the maximum number of digits. We iterate through N numbers, and for each, we perform a reversal (O(M)) and two set insertions (average O(1)). The complexity is dominated by the iteration and reversal. Since M is a small constant, the complexity is effectively O(N). · **Space:** O(N). In the worst case, where all original numbers and their reverses are unique, the set will store up to 2N distinct integers.
**Pros:** More memory-efficient as it avoids the creation of an intermediate list of size 2N.; More concise and a direct solution to the core problem of finding unique elements.
**Cons:** Slightly deviates from the literal step-by-step description of the problem, which might be less intuitive for a beginner.
### Explanation
Instead of building a temporary list of all 2N numbers, we can directly insert the numbers into a `HashSet`. The `HashSet` data structure is designed to store only unique elements. We iterate through the input `nums` array just once. In each iteration, we take the current number, add it to the set, compute its reverse, and add the reversed number to the set as well. If a number (either original or reversed) is already in the set, the `add` operation does nothing. After iterating through all the numbers in `nums`, the set will contain all unique integers from the original array and their reversed versions. The final answer is simply the size of the set.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    // Helper function to reverse the digits of an integer
    private int reverseInteger(int n) {
        int reversed = 0;
        while (n > 0) {
            int digit = n % 10;
            reversed = reversed * 10 + digit;
            n /= 10;
        }
        return reversed;
    }

    public int countDistinctIntegers(int[] nums) {
        Set<Integer> distinctNumbers = new HashSet<>();
        
        for (int num : nums) {
            // Add the original number to the set
            distinctNumbers.add(num);
            
            // Compute and add the reversed number to the set
            int reversedNum = reverseInteger(num);
            distinctNumbers.add(reversedNum);
        }
        
        return distinctNumbers.size();
    }
}
```
### Algorithm
- Initialize an empty `HashSet<Integer>` called `distinctNumbers`.
- Iterate through each number `num` in the input `nums` array.
- For each `num`:
  - Add `num` to the `distinctNumbers` set.
  - Calculate the reverse of `num`.
  - Add the reversed number to the `distinctNumbers` set.
- After the loop finishes, return the size of the `distinctNumbers` set.

# Solutions
### Java

```java
class Solution {
public
  int countDistinctIntegers(int[] nums) {
    Set<Integer> s = new HashSet<>();
    for (int x : nums) {
      s.add(x);
    }
    for (int x : nums) {
      int y = 0;
      while (x > 0) {
        y = y * 10 + x % 10;
        x /= 10;
      }
      s.add(y);
    }
    return s.size();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countDistinctIntegers(vector<int> &nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    for (int x : nums) {
      int y = 0;
      while (x) {
        y = y * 10 + x % 10;
        x /= 10;
      }
      s.insert(y);
    }
    return s.size();
  }
};

```

### Python

```python
class Solution:
    def countDistinctIntegers(self, nums: List[int]) -> int: s = set(nums) for x in nums: y = int(str(x)[:: - 1]) s . add(y) return len(s)

```