Skip to main content
Talentd

Sum of Decoded Numbers - Solution & Explanation

MediumArrayMathSimulation10 min read
Practice this problem

Problem Statement

You are given an integer array nums.

Each nums[i] is an encoded integer representing two positive integers xi and yi. To decode nums[i], define:

  • widthi = nums[i] % 10.
  • di = floor(nums[i] / 10).
  • xi as the integer formed by the first widthi digits of the decimal representation of di.
  • yi as the integer formed by all remaining digits of the decimal representation of di.

It is guaranteed that the decimal representation of di contains more than widthi digits. Therefore, both xi and yi contain at least one digit.

The decoded value of nums[i] is xiyi.

Return the sum of the decoded values of all elements in nums, modulo 109 + 7.

The floor() function returns the integer part of the division.

 

Example 1:

Input: nums = [231]

Output: 8

Explanation:

  • For 231, we have width = 1, d = 23, x = 2, and y = 3.
  • The decoded value of 231 is 23 = 8.
  • Since there is only one element in nums, the sum of the decoded values is 8.

Example 2:

Input: nums = [2522,2101]

Output: 1649

Explanation:

  • For 2522, we have width = 2, d = 252, x = 25, and y = 2.
  • The decoded value of 2522 is 252 = 625.
  • For 2101, we have width = 1, d = 210, x = 2, and y = 10.
  • The decoded value of 2101 is 210 = 1024.
  • The sum of the decoded values is 625 + 1024 = 1649.

Example 3:

Input: nums = [2301]

Output: 73741817

Explanation:

  • For 2301, we have width = 1, d = 230, x = 2, and y = 30.
  • The decoded value is 230 = 1073741824.
  • Therefore, the answer is 1073741824 modulo (109 + 7) = 73741817.

 

Constraints:

  • 1 <= nums.length <= 105
  • 100 < nums[i] < 1015
  • 1 <= widthi <= 9
  • 1 <= xi, yi < 109
  • The digit sequences used to form xi and yi do not have leading zeros.
  • It is guaranteed that every element in nums is a valid encoded integer.

Approach Overview

Problem Overview: You are given a compressed numeric expression where numbers are encoded as k[digits]. This means the digit string digits is repeated k times to form a decimal integer, and multiple such terms are separated by +. Decode each term, add the resulting integers, and return the sum modulo 1_000_000_007. Because k can be huge, the decoded number may have millions of digits, so you cannot actually expand it.

Approach 1: Brute-Force Expansion (O(expanded length) time, O(expanded length) space)

Parse the string and, for each k[digits], append the digit block k times to a string buffer, then convert that string to an integer and add it to the running total. This mirrors the problem statement directly and is simple to verify on small inputs, but it fails when k is large because both time and memory scale with the decoded output size, not with the encoded input length. For repeated counts above a few thousand, this approach can blow up instantly.

Approach 2: Simulation + Fast Power (O(N log M) time, O(1) space)

Simulate the expression by scanning left to right, but avoid constructing the repeated digits. For a token k[digits] where digits is an L-digit string with numeric value s, the decoded integer equals s * (10^(L*k) - 1) / (10^L - 1). Compute 10^(L*k) modulo 1_000_000_007 using binary exponentiation and multiply by the modular inverse of 10^L - 1 via Fermat's little theorem. This makes each token O(log(L*k)), so the entire scan is O(N log M), where M is the maximum repetition count. If you see a plain number, treat it as a 1[digits] token. The whole solution uses only a few integer variables, so extra space is constant.

Recommended for interviews: Most engineers can write the brute-force expander, but joining all the digits takes you out of O(N) and is an automatic fail when k reaches 10^6 or more. Interviewers expect the fast-power solution because it shows you recognize the geometric-series shape inside the repetition. Walk through a small example such as 3[12] and derive the value as 12 * (10^6 - 1) / 99, then explain that you compute only the numerator with pow. Review modular arithmetic and string parsing to strengthen the two skills at the core of this problem. The final implementation is available in Python, Java, C++, Go, and TypeScript.

Solution

We decode each element exactly as the statement describes. For each element v in nums, its width is w = v bmod 10, and the number left after dropping the last digit is d = \lfloor v / 10 \rfloor. Converting d to its decimal string s, the value x is the integer formed by the first w characters of s, and y is the integer formed by the remaining characters.

Since y can be as large as 10^9, multiplying repeatedly would be too slow, so we use fast power to compute x^y bmod (10^9 + 7) in O(log y) time, then accumulate the decoded values modulo 10^9 + 7.

The time complexity is O(n times log M), and the space complexity is O(log M). Here, n is the length of the array nums, and M is the maximum value in the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute-Force ExpansionO(expanded length)O(expanded length)Only for tiny repetition counts or sample-style test cases
Simulation + Fast PowerO(N log M)O(1)General case; handles huge repetitions, expected in interviews

Video Solutions (5)

LeetCode Weekly Contest 517 | 4038 & 4039 | Count Integers in a Block + Sum of Decoded Numbers | C++

EdgeCaseOffByOne8:58135 views
Video 1 of 5

Frequently Asked Questions

Sum of Decoded Numbers Python solution
In Python, use the built-in pow(base, exp, MOD) to compute 10^(L*k) modulo 1_000_000_007, then multiply by pow(denom, MOD-2, MOD) to get the denominator inverse. Scan the string, treat plain numbers as 1[digits], and accumulate each term modulo MOD.
Is Sum of Decoded Numbers easy or hard?
It is a Medium-difficulty problem with a 44.8% acceptance rate. The brute-force expansion is simple to imagine, but the need to handle huge repetition counts is what makes the fast-power solution important and turns it into a more challenging interview question.
How to solve Sum of Decoded Numbers in O(n log m)?
Scan the encoded string left to right. For each k[digits] token, compute the value of one repeated block, then multiply by the geometric sum (10^(L*k)-1)/(10^L-1) using fast modular exponentiation and modular inverse. Add this value to the running sum modulo 1_000_000_007. You never need to build the decoded string.
What is the best approach for Sum of Decoded Numbers?
The best approach is Simulation + Fast Exponentiation. It computes each k[digits] block with the geometric-series formula value(s) * (10^(L*k)-1)/(10^L-1), using modular fast power and modular inverse. This runs in O(N log M) time and O(1) extra space.
Is Sum of Decoded Numbers asked at Google/Amazon/Meta?
There is no official company tag, but coding rounds that combine string parsing with modular arithmetic and fast exponentiation are common at Amazon, Google, and Microsoft. Practicing this problem helps you handle those mathematical twists in competitive interviews.
What data structure is used in Sum of Decoded Numbers?
No complex data structure is needed for the optimal solution. A linear scan over the encoded string with integer variables for the repeat count, digit length, and cumulative sum is enough. The only helper you need is a fast modular power function.
What is the time complexity of Sum of Decoded Numbers?
The optimal time complexity is O(N log M), where N is the length of the encoded expression and M is the maximum repetition count. Brute-force expansion runs in O(expanded length) time, which can become exponentially slower and consume too much memory.

Ready to solve this problem?

Practice Sum of Decoded Numbers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays