Leetcode 2442: Count Number of Distinct Integers After Reverse Operations
You are given an array
nums consisting of positive integers. For each number in the array, you need to reverse its digits and append the reversed number to the end of the array. After performing this operation for all numbers, return the number of distinct integers in the resulting array.Problem
Approach
Steps
Complexity
Input: The input consists of an array `nums` of positive integers.
Example: nums = [21, 32, 12, 43]
Constraints:
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
Output: Return the number of distinct integers in the final array after reversing and appending each number.
Example: Output: 6
Constraints:
• The result should be a non-negative integer.
Goal: The goal is to count the distinct integers in the final array formed by reversing and appending each integer from the original array.
Steps:
• 1. Reverse the digits of each integer in the array and append the reversed number to the array.
• 2. Use a set to store the integers from the original and reversed numbers to ensure uniqueness.
• 3. Return the size of the set, which gives the number of distinct integers.
Goal: The solution should handle arrays with up to 10^5 elements efficiently and ensure that the reversed integers are correctly calculated and counted.
Steps:
• The number of elements in the array can be large, so time complexity should be optimized.
Assumptions:
• Each element in the array is a positive integer.
• There will be no empty arrays.
• Input: nums = [21, 32, 12, 43]
• Explanation: For this array, the reversed numbers would be [12, 23, 21, 34]. The resulting array would be [21, 32, 12, 43, 12, 23, 21, 34]. The distinct integers are {21, 32, 12, 43, 23, 34}, so the result is 6.
• Input: nums = [5, 15, 25, 55]
• Explanation: After reversing the numbers, the array becomes [5, 15, 25, 55, 5, 51, 52, 55]. The distinct integers are {5, 15, 25, 55, 51, 52}, so the result is 6.
Approach: The approach involves reversing each integer and storing the original and reversed integers in a set to count only distinct values.
Observations:
• Reversing each number can be done efficiently by converting the number to a string, reversing the string, and converting it back to an integer.
• A set will help us store only unique numbers, ensuring no duplicates.
• We should reverse each integer, insert both the original and reversed numbers into a set, and return the size of the set.
Steps:
• 1. Create a function to reverse the digits of an integer.
• 2. Iterate through each element of the input array, reverse the number and insert both the number and its reversed counterpart into a set.
• 3. Return the size of the set to get the number of distinct integers.
Empty Inputs:
• The input array is guaranteed to have at least one integer.
Large Inputs:
• The solution should handle arrays with up to 10^5 integers efficiently.
Special Values:
• When the array contains numbers that become identical after reversal (e.g., 10 becomes 1), it should correctly count distinct values.
Constraints:
• The algorithm must work within the constraints and should use optimized data structures for performance.
int rev(int num) {
int res = 0;
while(num > 0) {
res = res * 10 + num % 10;
num /= 10;
}
return res;
}
int countDistinctIntegers(vector<int>& nums) {
set<int> cnt;
int n = nums.size();
for(int i = 0; i < n; i++) {
cnt.insert(nums[i]);
cnt.insert(rev(nums[i]));
}
return cnt.size();
}
1 : Function Definition
int rev(int num) {
Defining the `rev` function, which takes an integer `num` and returns its reversed value.
2 : Variable Initialization
int res = 0;
Initializing `res` to store the reversed number, starting with a value of 0.
3 : Loop
while(num > 0) {
A loop that continues as long as `num` is greater than 0, reversing the digits of `num`.
4 : Mathematical Operation
res = res * 10 + num % 10;
Extracting the last digit of `num` and adding it to `res` after shifting `res` one place to the left.
5 : Integer Update
num /= 10;
Removing the last digit from `num` by dividing it by 10.
6 : Return Statement
return res;
Returning the reversed integer `res`.
7 : Function Definition
int countDistinctIntegers(vector<int>& nums) {
Defining the `countDistinctIntegers` function, which takes a vector `nums` and returns the count of distinct integers after considering both the original integers and their reversed counterparts.
8 : Set Initialization
set<int> cnt;
Creating a set `cnt` to store distinct integers, ensuring that duplicates are automatically removed.
9 : Variable Initialization
int n = nums.size();
Storing the size of the `nums` vector in variable `n`.
10 : Loop
for(int i = 0; i < n; i++) {
Starting a loop that iterates through each element `i` in the `nums` vector.
11 : Insert Element
cnt.insert(nums[i]);
Inserting the current element `nums[i]` into the set `cnt`.
12 : Insert Reversed Element
cnt.insert(rev(nums[i]));
Inserting the reversed version of the current element `nums[i]` into the set `cnt`.
13 : Return Statement
return cnt.size();
Returning the size of the set `cnt`, which represents the number of distinct integers considering both original and reversed elements.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of elements in the array. Each operation (reversing a number and inserting it into the set) takes constant time.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space used by the set to store distinct integers.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus