2553. Separate the Digits in an Array
Problem Description
The given problem provides an array of positive integers, nums
. The objective is to produce a new array, answer
, containing all the individual digits of each number in the original array, with the digits appearing in the same order as they do in those integers. Effectively, the process involves 'separating' the digits of each integer in nums
. For example, if you have an integer 10921
, you separate its digits to get the sequence [1,0,9,2,1]
. It is like 'unpacking' each number into its constituent digits and listing them in sequence.
Intuition
To solve this problem, we can break it down into a few manageable steps. Here's how we can think about the approach:
- We iterate through each number in the
nums
array since we need to process each number individually. - For each integer, we need to separate its digits. A standard way to do this is by continually dividing the number by 10 and collecting the remainders. This process will give us the digits in reverse order.
- We capture the reverse of the individual digits of an integer in a temporary list to preserve the correct order.
- After reversing, we append the individual digits into the answer list.
- We repeat this process for each integer in
nums
until we have processed all integers and collected all their digits, preserving the original order.
The intuition behind this approach is recognizing that dividing an integer by 10 and taking the remainder gives us its last digit. By continually doing this, we get the digits in reverse. We use a temporary list for each number to reverse the order of the digits, then concatenate it to our answer list. By iterating through all numbers in nums
and concatenating their digit lists, we achieve the required separation of digits while maintaining their original sequence.
Solution Approach
The solution uses a simple algorithm and basic Python list operations to achieve the desired result. Here's a step-by-step breakdown of the solution implementation:
-
An empty list called
ans
is created. This list will contain the final sequence of all individual digits from each number innums
. -
The process begins by iterating over each number (
x
) in thenums
array using afor
loop. -
Within each iteration, a temporary list called
t
is created to hold the digits of the current number (x
) in reverse order. -
A
while
loop runs as long as the current number (x
) is greater than zero. Inside this loop:- The expression
x % 10
is used to get the last digit ofx
. - This digit is appended to the temporary list
t
. - The number
x
is then divided by 10 (using floor divisionx //= 10
) to remove its last digit.
- The expression
-
After the
while
loop exits (meaningx
is now zero and all digits have been processed), the listt
contains the digits ofx
in reverse order. To correct the order, we reverset
usingt[::-1]
. -
The reversed list of digits is then extended into the
ans
list withans.extend(t[::-1])
. This means the digits ofx
are now added toans
in the correct order. -
Steps 3 to 6 are repeated for each number in the
nums
array. -
After the
for
loop completes, theans
list, now containing the individual digits of all the numbers in their correct order, is returned as the result.
Notice how the code makes use of modulo and floor division operations to separate the digits, and list operations like append and extend to collect digits in the correct order. Using these operations and control structures effectively, the code walks through each integer, extracts its digits, and assembles the final answer, while maintaining both the inner order of the digits in each number and overall order in which the numbers appear in the input list.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a simple example to illustrate the solution approach. Consider an array nums = [123, 45]
. We want to create an array that 'unpacks' each of these numbers into its individual digits [1, 2, 3, 4, 5]
.
Here is how the solution will walk through this example:
-
An empty list
ans
is created to store the answer. -
We start with the first number in the
nums
array, which is123
. -
A temporary list
t
is initialized to hold the digits of123
in reverse order. -
We enter a
while
loop because123
is greater than zero. Inside the loop:- We calculate
123 % 10
which equals3
. We append3
to the listt
. - We then divide
123
by10
using floor division, so123
becomes12
.
- We calculate
-
The loop runs again because
12
is still greater than zero.- Calculating
12 % 10
gives us2
. We append2
tot
. - Floor division of
12
by10
reduces it to1
.
- Calculating
-
The loop runs a final time with the value of
1
.- We append
1 % 10
(which is1
) tot
. - Floor division of
1
by10
gives us0
, and the loop exits asx
is now zero.
- We append
-
The list
t
now contains[3, 2, 1]
. We reverse it to get[1, 2, 3]
and extendans
by this list. -
Now we move to the second number,
45
, and repeat steps 3 to 7.t
starts empty, we add5
then4
after iterations of the loop.- We reverse
[5, 4]
to get[4, 5]
and extend it toans
.
-
At the end of the iteration,
ans
now contains[1, 2, 3, 4, 5]
. -
We return the
ans
list as the result.
This walk-through shows how the algorithm correctly takes each integer in the array nums
and breaks it down into individual digits, preserving the order within and between the numbers in the array.
Solution Implementation
1from typing import List
2
3class Solution:
4 def separateDigits(self, nums: List[int]) -> List[int]:
5 # Initialize an empty list to store the result
6 result = []
7
8 # Iterate over each number in the input list
9 for number in nums:
10 # Initialize a temporary list to store the digits of the current number
11 temp = []
12
13 # Loop to separate out each digit of the current number
14 while number:
15 # Append the last digit to the temporary list
16 temp.append(number % 10)
17 # Remove the last digit from the current number
18 number //= 10
19
20 # Reverse the temporary list because digits are stored from least significant to most significant
21 # Then extend the result list with the reversed list of digits
22 result.extend(temp[::-1])
23
24 # Return the result list containing all digits in order
25 return result
26
27# Example usage:
28# solution = Solution()
29# print(solution.separateDigits([123, 456])) # Output would be [1, 2, 3, 4, 5, 6]
30
1class Solution {
2
3 // Method to separate digits of each number in an array and return a new array with all the digits
4 public int[] separateDigits(int[] nums) {
5
6 // Initialize a list to hold individual digits
7 List<Integer> result = new ArrayList<>();
8
9 // Iterate over each number in the input array
10 for (int number : nums) {
11
12 // List to temporarily hold the digits of the current number
13 List<Integer> digits = new ArrayList<>();
14
15 // Extract digits from the number and add them to the temporary list
16 while (number > 0) {
17 int digit = number % 10; // get the last digit
18 digits.add(digit); // add digit to the list
19 number /= 10; // remove the last digit from the number
20 }
21
22 // Since digits are collected in reverse order, reverse the list to correct the order
23 Collections.reverse(digits);
24
25 // Add all the digits to the result list
26 result.addAll(digits);
27 }
28
29 // Convert the List<Integer> to an int array
30 int[] answer = new int[result.size()];
31 for (int i = 0; i < answer.length; i++) {
32 answer[i] = result.get(i); // Retrieve each integer from result list and store it in the array
33 }
34
35 // Return the array with separated digits
36 return answer;
37 }
38}
39
1#include <vector> // Include the necessary header for std::vector
2
3class Solution {
4public:
5 // Function to separate digits of numbers in a vector and return them as a new vector
6 vector<int> separateDigits(vector<int>& nums) {
7 vector<int> result; // This will store the final sequence of digits
8
9 // Loop through all numbers in the input vector
10 for (int number : nums) {
11 vector<int> temp; // Temporary vector to store the digits of the current number
12
13 // Extract digits of the current number from the end to the start
14 for (; number != 0; number /= 10) { // Continue until the number is 0
15 temp.push_back(number % 10); // Get the last digit and push it into temp
16 }
17
18 // While there are still digits in the temp vector
19 while (!temp.empty()) {
20 result.push_back(temp.back()); // Add the last digit from temp to the result vector
21 temp.pop_back(); // Remove the last element from temp
22 }
23 }
24
25 return result; // Return the final digit sequence
26 }
27};
28
1function separateDigits(nums: number[]): number[] {
2 // We will store the final array of separated digits here
3 const separatedDigits: number[] = [];
4
5 // Iterate over each number in the array
6 for (let num of nums) {
7 // Temporary array to store the digits of the current number
8 const digits: number[] = [];
9
10 // Extract digits of the current number and add them to the 'digits' array
11 while (num > 0) {
12 // Get the last digit of 'num' by modulo 10 (num % 10)
13 digits.push(num % 10);
14 // Remove the last digit from 'num'
15 num = Math.floor(num / 10);
16 }
17
18 // 'digits' array is in reverse order, so we reverse it to maintain the original order
19 separatedDigits.push(...digits.reverse());
20 }
21
22 // Return the array containing all the separated digits in correct order
23 return separatedDigits;
24}
25
Time and Space Complexity
The time complexity of the given code can be analyzed as follows:
- There is a loop that iterates over each number in the input list
nums
. - For each number, the inner while loop executes once for each digit in the number. So if a number
x
hask
digits, the while loop iteratesk
times.
Considering an input list with n
numbers, and each number has an average of d
digits, the total operations for separating digits of all numbers would be O(n * d)
. Therefore, the time complexity is O(n * d)
.
The space complexity is determined by:
- The list
ans
that holds the individual digits of all numbers. In the worst case, it will hold alln * d
digits from all numbers in the input list. - The temporary list
t
that stores the digits of a single number in reverse. Since it's reused for each number and extends theans
list immediately after, it doesn't increase the maximal memory footprint with respect to the number of total digits.
Given space is generally calculated in terms of the additional space required by the algorithm, not including the space for the input itself. The space complexity of the given algorithm is O(n * d)
as the ans
list may hold all digits of all numbers, though in practice, only the maximum number of digits in a single number is simultaneously held in the temporary list t
.
In conclusion, the time complexity is O(n * d)
and the space complexity is O(n * d)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.