Count Number of Distinct Integers After Reverse Operations solution and explanation
Google
9 more videos on this problem
2442 Count Number of Distinct Integers After Reverse Operations | Leetcode Weekly 315| LeetCode 2442Bro Coders · 5:06 · 824 views
Solution of Leetcode 2442 : "Count Number of Distinct Integers After Reverse Operations" using Java.Jayesh Gupta · 4:39 · 266 views
Count Number of Distinct Integers After Reverse Operations | leetcode Weekly 315 | Leetcode MediumBinaryMagic · 8:42 · 259 views
2442. Count Number of Distinct Integers After Reverse Operations (Leetcode Medium)Programming Live with Larry · 2:33 · 216 views
Leetcode Weekly contest 315 - Medium - Count Number of Distinct Integers After Reverse OperationsPrakhar Agrawal · 3:17 · 134 views
6205. Count Number of Distinct Integers After Reverse Operations || Leetcode Contest Medium || CPPCoding Techniques with Komal | Newton School · 10:26 · 85 views
2442. Count Number of Distinct Integers After Reverse Operations | Leet #code #programmingA+ Code · 5:21 · 79 views
LeetCode | Problem 2442 Solution | Count Number of Distinct Integers After Reverse OperationsDiwakar-X-Dev · 6:01 · 35 views
Leetcode 2442 : Count Number of Distinct Integers After Reverse Operations, SetMisterMagnet · 10:21 · 34 views
Count Number of Distinct Integers After Reverse Operations | Leetcode 2442Anubhav Ghosh · 2:18 · 29 views
The 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 <= 1051 <= nums[i] <= 106
Approach overview
Problem Overview: You are given an integer array nums. For every number, reverse its digits (e.g., 123 → 321) and add that reversed value back into the collection. After processing all numbers, return the count of unique integers that appear. The core challenge is tracking distinct values efficiently.
Approach 1: Using Set for Distinct Numbers (O(n * d) time, O(n) space)
This approach uses a set (or hash set) to automatically handle duplicates. Iterate through the array once. For each number, insert the original value into the set, compute its reversed form by repeatedly extracting digits (num % 10), and insert the reversed value as well. Hash sets guarantee average O(1) insertion and lookup, so the overall complexity depends mainly on processing digits during reversal. If d is the number of digits per integer, the total runtime becomes O(n * d) with O(n) space for storing unique numbers. This method works well because you never worry about duplicates—hashing handles them automatically.
The technique relies on efficient membership tracking using a hash table. Since the input is simply iterated once, it also aligns naturally with standard array traversal patterns.
Approach 2: Direct List Deduplication (O(n^2) time, O(n) space)
Another straightforward strategy is to store values in a list and manually check whether a value already exists before inserting it. Iterate through the original array, append the number if it does not already exist in the list, compute the reversed value, and again append it only if it is not present. The reversal logic still takes O(d), but the expensive step is the membership check. List searches require scanning existing elements, which leads to O(n) per check in the worst case.
Because each insertion may require a full scan of the list, the overall runtime grows to roughly O(n^2) for large inputs. Space usage remains O(n). This approach is easy to implement in scripting languages but becomes inefficient compared to hashing when the array size increases.
The problem itself combines basic math digit manipulation with simple counting of unique values.
Recommended for interviews: The hash set approach is what interviewers expect. It demonstrates awareness of constant-time lookups and clean handling of duplicates. A brute-force list check shows understanding of the problem mechanics, but the set-based solution shows you know how to optimize with the right data structure.
Approach 1: Using Set for Distinct Numbers
This approach utilizes a Set to keep track of distinct integers. We process each number by reversing its digits and add both the original and reversed numbers to the Set, which automatically ensures there are no duplicates. The result will be the size of the Set, which represents the number of distinct integers.
def reverse(num):
rev = 0
while num > 0:
rev = rev * 10 + num % 10
num //= 10
return rev
def count_distinct_numbers(nums):
distinct_set = set()
for num in nums:
distinct_set.add(num)
distinct_set.add(reverse(num))
return len(distinct_set)
nums = [1, 13, 10, 12, 31]
print(count_distinct_numbers(nums))import java.util.HashSet;
import java.util.Set;
public class Solution {
public static int reverse(int num) {
int rev = 0;
while (num > 0) {
rev = rev * 10 + num % 10;
num /= 10;
}
return rev;
}
public static int countDistinctNumbers(int[] nums) {
Set<Integer> distinctSet = new HashSet<>();
for (int num : nums) {
distinctSet.add(num);
distinctSet.add(reverse(num));
}
return distinctSet.size();
}
public static void main(String[] args) {
int[] nums = {1, 13, 10, 12, 31};
System.out.println(countDistinctNumbers(nums));
}
}#include <iostream>
#include <unordered_set>
#include <vector>
int reverse(int num) {
int rev = 0;
while (num > 0) {
rev = rev * 10 + num % 10;
num /= 10;
}
return rev;
}
int countDistinctNumbers(std::vector<int>& nums) {
std::unordered_set<int> distinctSet;
for (int num : nums) {
distinctSet.insert(num);
distinctSet.insert(reverse(num));
}
return distinctSet.size();
}
int main() {
std::vector<int> nums = {1, 13, 10, 12, 31};
std::cout << countDistinctNumbers(nums) << std::endl;
return 0;
}function reverse(num) {
let rev = 0;
while (num > 0) {
rev = rev * 10 + (num % 10);
num = Math.floor(num / 10);
}
return rev;
}
function countDistinctNumbers(nums) {
const distinctSet = new Set();
for (let num of nums) {
distinctSet.add(num);
distinctSet.add(reverse(num));
}
return distinctSet.size;
}
const nums = [1, 13, 10, 12, 31];
console.log(countDistinctNumbers(nums));#include <stdio.h>
#include <stdlib.h>
int reverse(int num) {
int rev = 0;
while (num > 0) {
rev = rev * 10 + num % 10;
num /= 10;
}
return rev;
}
int distinctIntegers(int* nums, int numsSize) {
int* hashSet = (int*)calloc(2000001, sizeof(int));
int distinctCount = 0;
for (int i = 0; i < numsSize; i++) {
int reversedNum = reverse(nums[i]);
if (!hashSet[nums[i]]) {
hashSet[nums[i]] = 1;
distinctCount++;
}
if (reversedNum != nums[i] && !hashSet[reversedNum]) {
hashSet[reversedNum] = 1;
distinctCount++;
}
}
free(hashSet);
return distinctCount;
}
int main() {
int nums[] = {1, 13, 10, 12, 31};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", distinctIntegers(nums, size));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public static int Reverse(int num) {
int rev = 0;
while (num > 0) {
rev = rev * 10 + num % 10;
num /= 10;
}
return rev;
}
public static int CountDistinctNumbers(int[] nums) {
HashSet<int> distinctSet = new HashSet<int>();
foreach (int num in nums) {
distinctSet.Add(num);
distinctSet.Add(Reverse(num));
}
return distinctSet.Count;
}
public static void Main(string[] args) {
int[] nums = { 1, 13, 10, 12, 31 };
Console.WriteLine(CountDistinctNumbers(nums));
}
}The Python solution utilizes a set to maintain the collection of unique numbers. Each number and its reversed counterpart are added to the set, ensuring that duplicates are not present. The final count of unique numbers is determined by the length of the set.
Time Complexity: O(n * d), where d is the average number of digits in the numbers. Space Complexity: O(n) for the set to store at most 2n numbers.
Approach 2: Using Direct List Deduplication
This approach directly appends both original and reversed numbers to a new array and then extracts unique numbers by leveraging available inbuilt functions specific to each programming language. This results in a list with only distinct numbers.
def reverse(num):
# Use string manipulation to reverse digits
return int(str(num)[::-1])
def distinct_after_reversals(nums):
result = []
for num in nums:
result.append(num)
result.append(reverse(num))
return len(set(result))
nums = [1, 13, 10, 12, 31]
print(distinct_after_reversals(nums))function reverse(num) {
// Convert number to a string, split it into an array of characters, reverse and join them back
return parseInt(num.toString().split('').reverse().join(''), 10);
}
function distinctAfterReversals(nums) {
let result = [];
for (let num of nums) {
result.push(num);
result.push(reverse(num));
}
return new Set(result).size;
}
const nums = [1, 13, 10, 12, 31];
console.log(distinctAfterReversals(nums));The Python implementation utilizes string slicing to reverse numbers and accumulates both original and reversed numbers into a list, which is then converted into a set to remove duplicates, thus determining the number of unique numbers.
Time Complexity: O(n * d), where n is the number of numbers and d is the digit length. Space Complexity: O(n) due to storing numbers in a list and converting it to a Set.
Approach 3: 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.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
function countDistinctIntegers(nums: number[]): number {
const n = nums.length;
for (let i = 0; i < n; i++) {
nums.push(Number([...(nums[i] + '')].reverse().join('')));
}
return new Set(nums).size;
}func countDistinctIntegers(nums []int) int {
s := map[int]struct{}{}
for _, x := range nums {
s[x] = struct{}{}
}
for _, x := range nums {
y := 0
for x > 0 {
y = y*10 + x%10
x /= 10
}
s[y] = struct{}{}
}
return len(s)
}use std::collections::HashSet;
impl Solution {
pub fn count_distinct_integers(nums: Vec<i32>) -> i32 {
let mut set = HashSet::new();
for i in 0..nums.len() {
let mut num = nums[i];
set.insert(num);
set.insert({
let mut item = 0;
while num > 0 {
item = item * 10 + (num % 10);
num /= 10;
}
item
});
}
set.len() as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Set for Distinct Numbers | Time Complexity: O(n * d), where d is the average number of digits in the numbers. Space Complexity: O(n) for the set to store at most 2n numbers. |
| Using Direct List Deduplication | Time Complexity: O(n * d), where n is the number of numbers and d is the digit length. Space Complexity: O(n) due to storing numbers in a list and converting it to a Set. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Set for Distinct Numbers | O(n * d) | O(n) | General case. Best performance with large arrays because hash lookups are O(1). |
| Direct List Deduplication | O(n^2) | O(n) | Simple scripts or small datasets where implementing a set is unnecessary. |
Frequently asked questions
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.
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<Integer> 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.
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.
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.