We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Number of Distinct Integers After Reverse Operations

Number: 2525

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of positive integers, for each integer, reverse its digits and append the reversed number to the array. Return the total count of distinct integers present in the final array.

Key Insights

  • Reverse the digits of an integer by converting it to a string (or use arithmetic), which automatically discards any leading zeros.
  • Use a hash set to keep track of distinct numbers while processing both the original and reversed integers.
  • Process each integer only once, adding both the original and its reversed form to the set.

Space and Time Complexity

Time Complexity: O(n * d), where d is the average number of digits per integer (effectively O(n) for the given constraints).
Space Complexity: O(n), for storing the distinct integers in a set.

Solution

Iterate through the array of integers. For each integer:

  1. Add the original integer to a set.
  2. Reverse its digits (by converting it to a string, reversing the string, and converting it back to an integer) and add the reversed integer to the set. The final answer is the size of the set, which represents the number of distinct integers after all reverse operations. The key data structure here is a hash set, which provides O(1) average time complexity for insertion and lookup.

Code Solutions

def countDistinctIntegers(nums):
    # Create a set to store distinct numbers
    distinct_numbers = set()
    # Iterate over each number in the list
    for num in nums:
        # Add the original number
        distinct_numbers.add(num)
        # Reverse the digits by converting to a string, reversing, and converting back to int
        reversed_num = int(str(num)[::-1])
        # Add the reversed number
        distinct_numbers.add(reversed_num)
    # Return the count of distinct numbers
    return len(distinct_numbers)

# Example usage:
print(countDistinctIntegers([1, 13, 10, 12, 31]))  # Expected Output: 6
← Back to All Questions