Sum of Decoded Numbers - Solution & Explanation

Medium8 min read

Problem Statement

You are given an integer array nums.

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

width_i = nums[i] % 10.
d_i = floor(nums[i] / 10).
x_i as the integer formed by the first width_i digits of the decimal representation of d_i.
y_i as the integer formed by all remaining digits of the decimal representation of d_i.

It is guaranteed that the decimal representation of d_i contains more than width_i digits. Therefore, both x_i and y_i contain at least one digit.

The decoded value of nums[i] is x_i^y_i.

Return the sum of the decoded values of all elements in nums, modulo 10⁹ + 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 2³ = 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 25² = 625.
For 2101, we have width = 1, d = 210, x = 2, and y = 10.
The decoded value of 2101 is 2¹⁰ = 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 2³⁰ = 1073741824.
Therefore, the answer is 1073741824 modulo (10⁹ + 7) = 73741817.

Constraints:

1 <= nums.length <= 10⁵
100 < nums[i] < 10¹⁵
1 <= width_i <= 9
1 <= x_i, y_i < 10⁹
The digit sequences used to form x_i and y_i do not have leading zeros.
It is guaranteed that every element in nums is a valid encoded integer.

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.