3697. Compute Decimal Representation

EasyArrayMath

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a positive integer n.

A positive integer is called a base-10 component if it can be written as a single digit from 1 to 9 multiplied by a non-negative power of 10. In other words, it is a number that has exactly one non-zero digit.

For example:

500 is a base-10 component because 500 = 5 × 10^2
30 is a base-10 component because 30 = 3 × 10^1
7 is a base-10 component because 7 = 7 × 10^0

On the other hand, 537, 102, and 11 are not base-10 components, since each of them contains more than one non-zero digit.

Your task is to express n as a sum of only base-10 components, using the fewest number of components possible.

Return an array containing these base-10 components sorted in descending order.

For example, if n = 537, the answer is [500, 30, 7], because 537 = 500 + 30 + 7, and each of these three numbers is a base-10 component. No representation with fewer components exists, since every non-zero digit of n must come from at least one component.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Extracting digits and their place values is a straightforward simulation of decimal decomposition with no search or optimization needed.

Open in Flowchart

Intuition

The key observation is that every number is naturally a sum of its digits multiplied by their place values. For instance, 537 = 5 × 100 + 3 × 10 + 7 × 1. Each term in this expansion has exactly one non-zero digit, which means each term is itself a base-10 component.

Why is this the fewest possible? Think about how addition works: when we add base-10 components together without any carries, each component contributes exactly one non-zero digit to the result. So a number with k non-zero digits needs at least k components. Trying to use fewer would force carries, but carries only complicate things — they never reduce the count below the number of non-zero digits.

Since the digit-by-digit decomposition achieves exactly k components (one per non-zero digit), it is optimal.

This leads directly to a simple simulation: extract each digit of n from the lowest position to the highest using modulo and division by 10, track the current place value p, and whenever a digit v is non-zero, record the component v × p. Because we process digits from least significant to most significant, the collected components are in ascending order, so we reverse the list at the end to get the required descending order.

Pattern Learn more about Math patterns.

Solution Approach

Simulation

We process the digits of n one at a time, from the least significant to the most significant, while keeping track of the place value of the current digit.

Step-by-step breakdown:

Initialize an empty list ans to store the components, and a variable p = 1 representing the place value of the current digit (1, 10, 100, ...).
Loop while n is non-zero. In each iteration:
- Use divmod(n, 10) to split n into:
  - v — the current lowest digit (n % 10)
  - n — the remaining higher digits (n // 10)
- If v is non-zero, then p * v is a base-10 component of the original number, so append it to ans.
- Multiply p by 10 to move to the next higher place value.
Reverse the list. Since digits were processed from lowest to highest place value, ans is in ascending order. Reversing it gives the required descending order.

Walkthrough with n = 537:

Iteration	`v` (digit)	`p` (place value)	Component added	Remaining `n`
1	`7`	`1`	`7`	`53`
2	`3`	`10`	`30`	`5`
3	`5`	`100`	`500`	`0`

After reversing: [500, 30, 7].

Implementation:

class Solution:
    def decimalRepresentation(self, n: int) -> List[int]:
        ans = []
        p = 1
        while n:
            n, v = divmod(n, 10)
            if v:
                ans.append(p * v)
            p *= 10
        ans.reverse()
        return ans

Complexity Analysis

Time complexity: O(log n) — the loop runs once per digit of n, and a number n has ⌊log₁₀ n⌋ + 1 digits.
Space complexity: O(1) if we ignore the space used by the answer list; otherwise O(log n), since the answer holds at most one component per digit.

Example Walkthrough

Let's trace the algorithm with n = 4062. This example is interesting because it contains a zero digit, which lets us see how the algorithm skips digits that contribute no component.

We start with ans = [] and place value p = 1.

Iteration 1: divmod(4062, 10) gives n = 406, v = 2. Since v = 2 is non-zero, we append p * v = 1 × 2 = 2 to ans. Then p becomes 10.

ans = [2]

Iteration 2: divmod(406, 10) gives n = 40, v = 6. Since v = 6 is non-zero, we append 10 × 6 = 60. Then p becomes 100.

ans = [2, 60]

Iteration 3: divmod(40, 10) gives n = 4, v = 0. Since v = 0, nothing is appended — a zero digit needs no component. We still multiply p by 10, so p becomes 1000.

ans = [2, 60] (unchanged)

Iteration 4: divmod(4, 10) gives n = 0, v = 4. Since v = 4 is non-zero, we append 1000 × 4 = 4000. Then p becomes 10000.

ans = [2, 60, 4000]

Now n = 0, so the loop terminates.

Summary table:

Iteration	`v` (digit)	`p` (place value)	Component added	Remaining `n`
1	`2`	`1`	`2`	`406`
2	`6`	`10`	`60`	`40`
3	`0`	`100`	— (skipped)	`4`
4	`4`	`1000`	`4000`	`0`

Finally, we reverse ans from ascending order [2, 60, 4000] to descending order:

[4000, 60, 2]

Verification: 4000 + 60 + 2 = 4062 ✓, each value has exactly one non-zero digit ✓, and since 4062 has three non-zero digits, no representation with fewer than three components exists — so this answer is optimal.

Solution Implementation

1class Solution:
2    def decimalRepresentation(self, n: int) -> List[int]:
3        # Store each non-zero component of the number
4        ans = []
5        # Current place value (1, 10, 100, ...)
6        place = 1
7        # Process digits from least significant to most significant
8        while n:
9            # Extract the last digit and remove it from n
10            n, digit = divmod(n, 10)
11            # Only keep non-zero digits, scaled by their place value
12            if digit:
13                ans.append(place * digit)
14            # Move to the next higher place value
15            place *= 10
16        # Reverse to output components from largest to smallest
17        ans.reverse()
18        return ans
19

1class Solution {
2    public int[] decimalRepresentation(int n) {
3        // Stores each non-zero decimal component (e.g., 537 -> [7, 30, 500])
4        List<Integer> components = new ArrayList<>();
5
6        // Current place value: 1, 10, 100, ...
7        int placeValue = 1;
8
9        // Extract digits from the least significant to the most significant
10        while (n > 0) {
11            int digit = n % 10; // Current digit
12            n /= 10;            // Remove the processed digit
13
14            // Only keep non-zero components
15            if (digit != 0) {
16                components.add(digit * placeValue);
17            }
18
19            // Move to the next higher place value
20            placeValue *= 10;
21        }
22
23        // Reverse so the components are ordered from the highest place value to the lowest
24        Collections.reverse(components);
25
26        // Convert the list into an int array as the final answer
27        int[] result = new int[components.size()];
28        for (int i = 0; i < components.size(); ++i) {
29            result[i] = components.get(i);
30        }
31        return result;
32    }
33}
34

1class Solution {
2public:
3    vector<int> decimalRepresentation(int n) {
4        vector<int> result;
5        long long placeValue = 1; // Current place value (1, 10, 100, ...)
6
7        // Extract digits from the least significant to the most significant
8        while (n > 0) {
9            int digit = n % 10; // Current digit
10            n /= 10;            // Remove the processed digit
11
12            // Only non-zero digits contribute a base-10 component
13            if (digit != 0) {
14                result.push_back(placeValue * digit);
15            }
16
17            placeValue *= 10; // Move to the next higher place value
18        }
19
20        // Components were collected from smallest to largest,
21        // so reverse to get descending order
22        reverse(result.begin(), result.end());
23        return result;
24    }
25};
26

1/**
2 * Decomposes a positive integer into its base-10 place-value components.
3 * For example, 537 -> [500, 30, 7].
4 *
5 * @param n - The positive integer to decompose.
6 * @returns An array of place-value components in descending order of magnitude.
7 */
8function decimalRepresentation(n: number): number[] {
9    // Stores the non-zero place-value components (collected from lowest to highest digit).
10    const result: number[] = [];
11
12    // Current place value (1 for ones, 10 for tens, 100 for hundreds, ...).
13    let placeValue: number = 1;
14
15    // Process digits from the least significant to the most significant.
16    while (n > 0) {
17        // Extract the current lowest digit.
18        const digit: number = n % 10;
19
20        // Remove the lowest digit from n (integer division by 10).
21        n = Math.floor(n / 10);
22
23        // Only keep non-zero digits, scaled by their place value.
24        if (digit !== 0) {
25            result.push(digit * placeValue);
26        }
27
28        // Move to the next higher place value.
29        placeValue *= 10;
30    }
31
32    // Reverse so the components appear from the highest place value to the lowest.
33    result.reverse();
34
35    return result;
36}
37

Time and Space Complexity

Time Complexity: O(log n), where n is the given positive integer. The while loop executes once per decimal digit of n, and the number of digits is ⌊log₁₀ n⌋ + 1, which is O(log n). Each iteration performs constant-time operations (divmod, comparison, append, multiplication). The final ans.reverse() also takes O(log n) time since the list holds at most one element per digit.
Space Complexity: O(log n), used by the answer list ans, which stores at most one value for each non-zero digit of n — bounded by the total digit count O(log n). Apart from the output list, only a constant number of extra variables (p, v) are used.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Skip Zero Digits

The most frequent mistake is appending a component for every digit, including zeros. A zero digit contributes 0 to the sum, and 0 is not a base-10 component (it cannot be written as a digit 1–9 times a power of 10), so it must never appear in the output.

Incorrect:

while n:
    n, digit = divmod(n, 10)
    ans.append(place * digit)   # appends 0 for zero digits!
    place *= 10

For n = 102, this produces [100, 0, 2] instead of [100, 2].

Fix: Guard the append with a check:

if digit:
    ans.append(place * digit)

2. Returning Components in Ascending Order

Because digits are extracted from least significant to most significant, the list is naturally built in ascending order. Forgetting the final ans.reverse() (or ans[::-1]) returns [7, 30, 500] for n = 537, which fails the requirement that components be sorted in descending order.

Fix: Always reverse before returning, or build the list from the most significant digit instead (e.g., by iterating over str(n) left to right).

3. Off-by-One in Place Value When Using Strings

A string-based approach is a clean alternative, but it's easy to miscompute the power of 10 for each character:

Incorrect:

s = str(n)
ans = []
for i, ch in enumerate(s):
    if ch != '0':
        ans.append(int(ch) * 10 ** i)   # wrong exponent!

Here index i counts from the left, but the place value depends on the distance from the right. For n = 537, this yields [5, 30, 700].

Fix: Use the distance from the end of the string:

ans.append(int(ch) * 10 ** (len(s) - 1 - i))

This version also has the side benefit of already producing the list in descending order, so no reversal is needed.

4. Updating the Place Value Inside the `if` Block

Another subtle bug is multiplying place by 10 only when the digit is non-zero:

Incorrect:

while n:
    n, digit = divmod(n, 10)
    if digit:
        ans.append(place * digit)
        place *= 10   # skipped when digit == 0!

For n = 102, the 0 in the tens position doesn't advance the place value, so the 1 gets scaled by 10 instead of 100, producing [10, 2].

Fix: The place *= 10 update must execute on every loop iteration, regardless of whether the digit is zero, because the place value advances with each digit position, not with each component.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

3697. Compute Decimal Representation

Problem Description

How We Pick the Algorithm

Why Simulation / Basic DSA?

Intuition

Solution Approach

Simulation

Complexity Analysis

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Forgetting to Skip Zero Digits

2. Returning Components in Ascending Order

3. Off-by-One in Place Value When Using Strings

4. Updating the Place Value Inside the if Block

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings

4. Updating the Place Value Inside the `if` Block