#2442

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Number of Distinct Integers After Reverse Operations

This problem requires counting distinct integers after performing reverse operations on each integer in an array.

Problem Statement

You are given an array of positive integers. For each integer, you must reverse its digits and add the reversed value to the end of the array. This operation must be performed on the original integers in the array, not the reversed ones.

Your task is to return the number of distinct integers in the final array. Since numbers can repeat after reversal, you need to ensure that duplicates are not counted more than once.

Examples

Example 1

Input: nums = [1,13,10,12,31]

Output: 6

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

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

Solution Approach

Reverse Digits and Track Uniqueness

For each number in the array, reverse its digits and add both the original number and its reversed version to a set or hash table. This will automatically handle uniqueness as sets and hash tables store only distinct elements.

Efficient Lookup with Hash Table

Using a hash table allows O(1) average time complexity for both insertions and lookups. This makes it efficient when checking if a number has been encountered before or if a reversed number already exists in the array.

Final Count

At the end of the process, the number of distinct integers can be found by simply taking the size of the set or hash table, as all duplicates have been automatically handled.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the number of integers in the array. Reversing each integer takes constant time, and inserting into a hash table also takes constant time on average. The space complexity is O(n), as you need to store up to n distinct integers in the hash table or set.

What Interviewers Usually Probe

Candidate understands how to handle uniqueness using hash-based data structures.
Candidate demonstrates efficient handling of large input sizes (up to 10^5).
Candidate can optimize for both time and space complexity, particularly in managing distinct elements.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reverse the digits properly, especially for numbers like 10 or 100 that result in leading zeros.
Not using a data structure like a set or hash table to track distinct elements, leading to incorrect results.
Misunderstanding the problem constraints and assuming a more complex solution when a set or hash table suffices.

Follow-up variants

Handle negative numbers by modifying the digit reversal approach.
Consider using a different data structure for tracking distinct elements, such as an array with sorting.
Extend the problem to handle larger input sizes or multiple operations (e.g., repeated reversals).

FAQ

What is the main approach to solving Count Number of Distinct Integers After Reverse Operations?

The main approach is to reverse each number, add both the original and reversed values to a set or hash table, and return the number of distinct integers.

How do you handle duplicates in this problem?

Duplicates are automatically handled by using a set or hash table, which only stores distinct elements.

Can we optimize the space complexity for this problem?

While space complexity is generally O(n), you can optimize memory usage by removing unnecessary operations or using in-place data structures if applicable.

What is the time complexity of reversing digits for each number?

Reversing the digits for each number is done in constant time, O(1), because the number of digits is small relative to the size of the array.

Is there a more efficient way to handle the uniqueness of numbers?

Using a set or hash table is the most efficient way to track distinct numbers with O(1) time complexity for insertions and lookups.

terminal

Solution

Solution 1: Hash Table

First, we use a hash table to record all integers in the array. Then, we traverse each integer in the array, reverse it, and add the reversed integer to the hash table. Finally, we return the size of the hash table.

1

2

3

4

5

6

7

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)

Continue Practicing

#2364 count number of bad pairs #2748 number of beautiful pairs #2001 number of pairs of interchangeable rectangles