Count Number of Distinct Integers After Reverse Operations

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

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.

Examples:

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 are underlined. Note that for the integer 10, after reversing 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).

Input: nums = [2,2,2]

Output: 1

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

Input: nums = [10,20,30]

Output: 5

Explanation: After including the reverse of each number, the resulting array is [10,20,30,1,2,3]. The number of distinct integers is 5 (1, 2, 3, 10, 20, 30).

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Editorial

Intuition:

The final array after the operation consists of all original numbers and their reversed digits. The number of distinct integers equals the size of the union of these two sets. By using a hash set, we can efficiently collect all unique values while processing each number and its reverse exactly once.

Approach:

Initialize an empty hash set to store distinct integers.
For each integer x in the array nums: add x and its reversed form to the set (reverse by converting to string, reversing, and converting back).
Return the size of the set as the answer.

#include <vector>
#include <unordered_set>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int countDistinct(vector<int> nums) {
        unordered_set<int> s;
        for (int x : nums) {
            s.insert(x);
            string rev = to_string(x);
            reverse(rev.begin(), rev.end());
            s.insert(stoi(rev));
        }
        return s.size();
    }
};
import java.util.*;

class Solution {
    public int countDistinct(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);
            String rev = new StringBuilder().append(x).reverse().toString();
            set.add(Integer.parseInt(rev));
        }
        return set.size();
    }
}
class Solution:
    def count_distinct(self, nums):
        s = set()
        for x in nums:
            s.add(x)
            rev = int(str(x)[::-1])
            s.add(rev)
        return len(s)
class Solution {
    countDistinct(nums) {
        const set = new Set();
        for (const x of nums) {
            set.add(x);
            const rev = Number(String(x).split('').reverse().join(''));
            set.add(rev);
        }
        return set.size;
    }
}

Complexity Analysis:

Time Complexity: O(n), where n is the length of nums. Each number is processed in constant time (reversing up to 7 digits) and set insertions are average O(1).

Space Complexity: O(n) for storing the distinct numbers in the worst case.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories