006.md

2442. Count Number of Distinct Integers After Reverse Operations

Difficulty: 🟡 Medium

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.

Examples:

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^5
• 1 <= nums[i] <= 10^6

Solutions

O(n) solution

Python3

class Solution:
    def countDistinctIntegers(self, nums: List[int]) -> int:
        def reverse(number):
            result = 0
            while number:
                result = result * 10 + number % 10
                number //= 10
            return result

        for num in nums[:]:
            nums.append(reverse(num))
            
        return len(set(nums))

The given solution solves the problem by iterating through each number in the nums array, reversing its digits, and appending the reversed number to the end of the array. It then returns the count of distinct integers in the final array.

The algorithm follows these steps:

1. Define a helper function reverse that takes a number as input and reverses its digits. This function uses a variable result initialized to 0.
2. Inside the reverse function, enter a while loop that continues as long as the input number is non-zero.
3. Inside the while loop, calculate the next digit of the reversed number by using the expression result = result * 10 + number % 10, where number % 10 gives the last digit of the number and result * 10 shifts the existing digits to the left.
4. Divide the input number by 10 using the floor division operator number //= 10 to remove the last digit.
5. Repeat steps 3-4 until the input number becomes zero.
6. After defining the reverse function, iterate through each number num in the nums array using a for loop.
7. Inside the for loop, append the reversed number reverse(num) to the nums array using the append method.
8. Finally, return the length of the set of distinct integers in the nums array using the len and set functions.

Complexity Analysis

The time complexity of the algorithm is O(N * D), where N is the length of the nums array and D is the maximum number of digits in the input numbers. This is because the algorithm iterates through each number in the array and reverses its digits, which takes O(D) time.

The space complexity of the algorithm is O(N), where N is the length of the nums array. This is because the algorithm uses additional space to store the reversed numbers in the nums array.

Summary

The given solution calculates the number of distinct integers in an array by reversing the digits of each number and appending the reversed number to the end of the array. The algorithm has a time complexity of O(N * D) and a space complexity of O(N), where N is the length of the array.

NB: If you want to get community points please suggest solutions in other languages as merge requests.