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 ofdistinct integers in the final array.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4

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 <= 10^5
  • 1 <= nums[i] <= 10^6

Solution

Method 1 – HashSet with Reverse Integer Calculation

Intuition

For each number, add both the number and its digit-reversed value to a set. The set will automatically keep only distinct values.

Approach

  1. Initialize an empty set.
  2. For each number in the input array:
    • Add the number to the set.
    • Reverse its digits and add the reversed number to the set.
  3. Return the size of the set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int countDistinctIntegers(vector<int>& nums) {
        unordered_set<int> s;
        for (int x : nums) {
            s.insert(x);
            int y = 0, t = x;
            while (t) {
                y = y * 10 + t % 10;
                t /= 10;
            }
            s.insert(y);
        }
        return s.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func CountDistinctIntegers(nums []int) int {
    s := make(map[int]struct{})
    for _, x := range nums {
        s[x] = struct{}{}
        y, t := 0, x
        for t > 0 {
            y = y*10 + t%10
            t /= 10
        }
        s[y] = struct{}{}
    }
    return len(s)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int countDistinctIntegers(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) {
            s.add(x);
            int y = 0, t = x;
            while (t > 0) {
                y = y * 10 + t % 10;
                t /= 10;
            }
            s.add(y);
        }
        return s.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun countDistinctIntegers(nums: IntArray): Int {
        val s = mutableSetOf<Int>()
        for (x in nums) {
            s.add(x)
            var y = 0
            var t = x
            while (t > 0) {
                y = y * 10 + t % 10
                t /= 10
            }
            s.add(y)
        }
        return s.size
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def countDistinctIntegers(self, nums: list[int]) -> int:
        s = set()
        for x in nums:
            s.add(x)
            y, t = 0, x
            while t > 0:
                y = y * 10 + t % 10
                t //= 10
            s.add(y)
        return len(s)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

use std::collections::HashSet;
impl Solution {
    pub fn count_distinct_integers(nums: Vec<i32>) -> i32 {
        let mut s = HashSet::new();
        for &x in &nums {
            s.insert(x);
            let mut y = 0;
            let mut t = x;
            while t > 0 {
                y = y * 10 + t % 10;
                t /= 10;
            }
            s.insert(y);
        }
        s.len() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    countDistinctIntegers(nums: number[]): number {
        const s = new Set<number>();
        for (const x of nums) {
            s.add(x);
            let y = 0, t = x;
            while (t > 0) {
                y = y * 10 + t % 10;
                t = Math.floor(t / 10);
            }
            s.add(y);
        }
        return s.size;
    }
}

Complexity

  • ⏰ Time complexity: O(n * d), where n is the number of elements and d is the number of digits in the largest number.
  • 🧺 Space complexity: O(n), for storing the set of distinct numbers.