Leetcode 2553: Separate the Digits in an Array
You are given an array
nums consisting of positive integers. Your task is to return a new array where each integer from nums is separated into its individual digits, while maintaining the order of the integers.Problem
Approach
Steps
Complexity
Input: You are given an array `nums` where each element is a positive integer.
Example: nums = [14, 39, 58, 60]
Constraints:
• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^5
Output: Return an array where each element contains the digits of the integers from `nums`, separated in the same order.
Example: [1, 4, 3, 9, 5, 8, 6, 0]
Constraints:
Goal: To break down each integer into its individual digits and return them in the same order.
Steps:
• 1. For each number in `nums`, extract its digits by repeatedly dividing it by 10 and taking the remainder.
• 2. Store the digits of each number in a new list.
• 3. Append the digits of each number to the final result in order.
Goal: The array `nums` can have up to 1000 elements and each number can have up to 5 digits.
Steps:
• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^5
Assumptions:
• All numbers in `nums` are positive integers.
• Each number in `nums` can have up to 5 digits.
• Input: nums = [14, 39, 58, 60]
• Explanation: In this example, we separate each number into its digits and return the combined result as [1, 4, 3, 9, 5, 8, 6, 0].
• Input: nums = [3, 7, 1, 2]
• Explanation: Since all the numbers in `nums` are single digits, the output remains [3, 7, 1, 2].
Approach: The goal is to convert each integer in `nums` into its constituent digits and return them in the same order.
Observations:
• We need to handle each number separately, extract its digits, and concatenate them in the order of appearance.
• The task can be accomplished by repeatedly dividing each number by 10 to get its digits in reverse order and then reversing them.
Steps:
• 1. Loop through each number in `nums`.
• 2. For each number, extract its digits by dividing the number by 10 and taking the remainder.
• 3. Append each digit to the result array.
• 4. Return the final array containing all the digits.
Empty Inputs:
• The array `nums` will always have at least one element, as per the constraints.
Large Inputs:
• The solution must handle arrays up to 1000 integers and each integer up to 10^5.
Special Values:
• Single-digit integers in `nums` should be handled as-is.
Constraints:
• Ensure the solution works efficiently for the upper limits of input size and integer value.
vector<int> separateDigits(vector<int>& nums) {
vector<int> ans;
for(auto x: nums) {
vector<int> tmp;
while(x) {
tmp.push_back(x % 10);
x /= 10;
}
while(!tmp.empty()) {
ans.push_back(tmp.back());
tmp.pop_back();
}
}
return ans;
}
1 : Function Definition
vector<int> separateDigits(vector<int>& nums) {
This is the function definition for 'separateDigits'. It accepts a vector of integers, 'nums', and will return a vector containing all the digits from the numbers in 'nums'.
2 : Variable Initialization
vector<int> ans;
Here, a vector 'ans' is initialized to store the final result, which will contain the separated digits from all the numbers in the input vector 'nums'.
3 : Loop Through Input
for(auto x: nums) {
This is a for-loop that iterates through each number in the input vector 'nums'. The variable 'x' represents each individual number.
4 : Temporary Vector Initialization
vector<int> tmp;
For each number 'x', a temporary vector 'tmp' is initialized to store the digits of the current number in reverse order.
5 : Extract Digits
while(x) {
This while-loop runs as long as 'x' is not zero. It extracts each digit from the number by using modulo 10 and stores it in 'tmp'.
6 : Push Back Digit
tmp.push_back(x % 10);
This line extracts the last digit of 'x' using modulo 10 and adds it to the 'tmp' vector.
7 : Divide Number
x /= 10;
This divides 'x' by 10, effectively removing the last digit from the number for the next iteration.
8 : Reverse Digits to Final Vector
while(!tmp.empty()) {
This while-loop runs as long as 'tmp' is not empty, effectively reversing the digits that were collected in 'tmp'.
9 : Push Back Reversed Digits
ans.push_back(tmp.back());
This line takes the last digit from 'tmp' (which is the first digit of the original number) and adds it to the 'ans' vector.
10 : Pop Back Reversed Digits
tmp.pop_back();
This removes the last digit from 'tmp' after it has been added to 'ans', preparing for the next digit.
11 : Return Final Result
return ans;
The function returns the 'ans' vector, which now contains all the digits from the numbers in 'nums', each digit separated in the correct order.
Best Case: O(n), where `n` is the number of elements in `nums`.
Average Case: O(n * m), where `n` is the number of elements and `m` is the maximum number of digits in any number.
Worst Case: O(n * m), where `n` is the number of elements and `m` is the maximum number of digits in any number.
Description: The time complexity depends on the total number of digits across all numbers in the array.
Best Case: O(n), where `n` is the number of elements in `nums`.
Worst Case: O(n * m), where `n` is the number of elements in `nums` and `m` is the maximum number of digits in any number.
Description: The space complexity is determined by the space required to store the digits of all numbers in `nums`.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus