Count Number of Distinct Integers After Reverse Operations Python/Java solution

In Python, use a set and reverse numbers using arithmetic or string conversion before inserting them. In Java, use a HashSet and reverse digits with a loop using modulo and division. Both implementations follow the same logic and run in O(n * d) time with O(n) space.

What is the best approach for Count Number of Distinct Integers After Reverse Operations?

The most efficient approach uses a hash set to store both the original numbers and their reversed values. Insert each number and its reversed form into the set while iterating through the array. Because hash set operations are O(1) on average, the overall complexity becomes O(n * d), where d is the number of digits in each number.

Is Count Number of Distinct Integers After Reverse Operations asked at Google/Amazon/Meta?

Problems involving hash sets, digit manipulation, and counting unique values frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the pattern of combining hashing with simple math operations is common in coding interviews.

What data structure is used in Count Number of Distinct Integers After Reverse Operations?

A hash set is the primary data structure used in the optimal solution. It allows constant-time insertion and automatically removes duplicates. This makes it ideal for tracking unique integers after adding both original and reversed numbers.

What is the time complexity of Count Number of Distinct Integers After Reverse Operations?

The optimal solution runs in O(n * d) time. The algorithm iterates through n numbers and reverses each integer digit by digit, which costs O(d). Hash set insertions are O(1) on average, so the digit reversal dominates the runtime.

Description Hints 2 Solution Video 5:06

2442. Count Number of Distinct Integers After Reverse Operations

Q: Is Count Number of Distinct Integers After Reverse Operations easy or hard?

The problem is generally considered Easy to Medium depending on familiarity with sets and digit manipulation. The algorithm itself is straightforward once you recognize that tracking unique values with a hash set avoids duplicate handling logic.

Q: How to solve Count Number of Distinct Integers After Reverse Operations in O(n)?

Treat digit length as a small constant and use a hash set. Traverse the array once, insert each number into the set, compute its reversed value, and insert that as well. After processing all numbers, return the size of the set. In practice this behaves like O(n) because integer digit length is small.

Medium81.4% acceptance1 company

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 <= 10⁵
1 <= nums[i] <= 10⁶

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

What data structure allows us to insert numbers and find the number of distinct numbers in it?

Hint 2

Try using a set, insert all the numbers and their reverse into it, and return its size.

5:06

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution