Count Number of Distinct Integers After Reverse Operations

Count Number of Distinct Integers After Reverse Operations - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,5,1,3]

› Output: 6

💡 Note: Original: [2,5,1,3]. After adding reverses: [2,5,1,3,2,5,1,3]. Distinct values: {1,2,3,5} = 4 unique numbers. Wait, let me recalculate: reverse(2)=2, reverse(5)=5, reverse(1)=1, reverse(3)=3. So we have [2,5,1,3,2,5,1,3] which gives us {1,2,3,5} = 4 distinct.

Example 2 — Some Different Reverses

$ Input: nums = [13,32,13]

› Output: 4

💡 Note: Original: [13,32,13]. Reverses: reverse(13)=31, reverse(32)=23, reverse(13)=31. Final array: [13,32,13,31,23,31]. Distinct values: {13,32,31,23} = 4 unique numbers.

Example 3 — All Same Digits

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

› Output: 6

💡 Note: Original: [1,13,10,12,31]. Reverses: reverse(1)=1, reverse(13)=31, reverse(10)=1, reverse(12)=21, reverse(31)=13. Final: [1,13,10,12,31,1,31,1,21,13]. Distinct: {1,13,10,12,31,21} = 6 unique numbers.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array of positive integers

Add Reverses

Append digit-reversed version of each number

Count Distinct

Count unique values in final array

Key Takeaway

🎯 Key Insight: Use a hash set to automatically eliminate duplicates while processing original numbers and their digit-reversed versions

Asked in

A Amazon 15 G Google 10 M Microsoft 8

Use a hash set to automatically eliminate duplicates while adding original numbers and their digit-reversed versions. The key insight is that sets handle uniqueness automatically, so we just add all values and return the size. Best approach is hash set with Time: O(n × d), Space: O(n) where d is average digits per number.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with List	O(n²)	O(n)	Create new array with originals and reverses, then count unique values
Hash Set Approach	O(n × d)	O(n)	Use hash set to automatically handle uniqueness while adding numbers and reverses

Brute Force with List — Algorithm Steps

Step 1: Create array with original numbers
Step 2: Add reversed version of each number
Step 3: Count distinct values by checking duplicates

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Array

Start with input array

Add Reverses

Append reversed numbers

Count Distinct

Manually check for duplicates

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int reverseNumber(int n) {
    int reversed = 0;
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return reversed;
}

int solution(int* nums, int numsSize) {
    // Create array with originals and their reverses
    int* allNumbers = (int*)malloc(2 * numsSize * sizeof(int));
    int allSize = 0;
    
    // Add original numbers
    for (int i = 0; i < numsSize; i++) {
        allNumbers[allSize++] = nums[i];
    }
    
    // Add reversed numbers
    for (int i = 0; i < numsSize; i++) {
        allNumbers[allSize++] = reverseNumber(nums[i]);
    }
    
    // Count distinct values manually
    int* distinct = (int*)malloc(2 * numsSize * sizeof(int));
    int distinctCount = 0;
    
    for (int i = 0; i < allSize; i++) {
        int found = 0;
        for (int j = 0; j < distinctCount; j++) {
            if (distinct[j] == allNumbers[i]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            distinct[distinctCount++] = allNumbers[i];
        }
    }
    
    free(allNumbers);
    free(distinct);
    return distinctCount;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing - assumes format [1,2,3,...]
    int nums[100];
    int numsSize = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

O(n) to create array with reverses, O(n²) to count distinct values by checking each against all others

⚠ Quadratic Growth

Space Complexity

O(n)

Extra array to store original numbers and their reverses

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

285 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with List — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler