3697. Compute Decimal Representation

Problem Statement

You are given a positive integer n.

A positive integer is a base-10 component if it is the product of a single digit from 1 to 9 and a non-negative power of 10. For example, 500, 30, and 7 are base-10 components, while 537, 102, and 11 are not.

Express n as a sum of only base-10 components, using the fewest base-10 components possible.

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

Solution

This is a straightforward implementation problem. The key insight is that any positive integer can be uniquely represented as a sum of its digits multiplied by powers of 10. For example, $123 = 1 \cdot 10^2 + 2 \cdot 10^1 + 3 \cdot 10^0$. Each term in this expansion is a base-10 component. This decomposition also uses the minimum number of components.

The algorithm iterates through the digits of the number n from right to left (least significant to most significant). In each step, we extract the last digit, multiply it by the corresponding power of 10, and if the result is non-zero, we add it to our list of components. We then remove the last digit from n by integer division and increase our power of 10.

Since we process the digits from right to left, the resulting components will be in ascending order. The problem requires the components to be in descending order, so we simply reverse the list before returning it.

class Solution {
public:
    vector<int> decimalRepresentation(int n) {
        vector<int> ans;
        long long pow = 1;
        while (n > 0) {
            int digit = n % 10;
            if (digit > 0) {
                ans.push_back(digit * pow);
            }
            n /= 10;
            pow *= 10;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Time Complexity

• Time: $O(\log_{10} n)$, as we process each digit of the number once.
• Space: $O(\log_{10} n)$, to store the resulting base-10 components.