4039. Sum of Decoded Numbers

Description

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.

Solutions

Solution 1: Simulation + Fast Power

Thinking

Each element decodes independently: the width is the last digit, the remaining digits split into \(x\) and \(y\), and we compute \(x^y\). Elements do not share state.

\(y\) can reach \(10^9\), so multiplying in a loop is impossible. Fast exponentiation yields \(x^y\bmod(10^9+7)\) in \(O(\log y)\), and we add the results modulo the same prime.

We decode each element exactly as the statement describes. For each element \(v\) in \(\textit{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 \(\textit{nums}\), and \(M\) is the maximum value in the array.

Python3JavaC++GoTypeScript

class Solution:
    def sumDecoded(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        ans = 0
        for v in nums:
            d, w = divmod(v, 10)
            s = str(d)
            x = int(s[:w])
            y = int(s[w:])
            ans = (ans + pow(x, y, mod)) % mod
        return ans

class Solution {
    public int sumDecoded(long[] nums) {
        final long mod = 1000000007L;
        long ans = 0;

        for (long v : nums) {
            long d = v / 10;
            int w = (int) (v % 10);

            String s = Long.toString(d);
            long x = Long.parseLong(s.substring(0, w));
            long y = Long.parseLong(s.substring(w));

            ans = (ans + pow(x, y, mod)) % mod;
        }

        return (int) ans;
    }

    private long pow(long x, long y, long mod) {
        long res = 1;
        while (y > 0) {
            if ((y & 1) != 0) {
                res = res * x % mod;
            }
            x = x * x % mod;
            y >>= 1;
        }
        return res;
    }
}

class Solution {
public:
    int sumDecoded(vector<long long>& nums) {
        const long long mod = 1000000007;
        long long ans = 0;

        for (long long v : nums) {
            long long d = v / 10;
            int w = v % 10;

            string s = to_string(d);
            long long x = stoll(s.substr(0, w));
            long long y = stoll(s.substr(w));

            ans = (ans + qpow(x, y, mod)) % mod;
        }

        return ans;
    }

private:
    long long qpow(long long x, long long y, long long mod) {
        long long res = 1;
        while (y) {
            if (y & 1) {
                res = res * x % mod;
            }
            x = x * x % mod;
            y >>= 1;
        }
        return res;
    }
};

func sumDecoded(nums []int64) int {
    const mod int64 = 1000000007
    var ans int64

    for _, v := range nums {
        d, w := v/10, int(v%10)
        s := strconv.FormatInt(d, 10)

        x, _ := strconv.ParseInt(s[:w], 10, 64)
        y, _ := strconv.ParseInt(s[w:], 10, 64)

        ans = (ans + pow(x, y, mod)) % mod
    }

    return int(ans)
}

func pow(x, y, mod int64) int64 {
    res := int64(1)
    for y > 0 {
        if y&1 != 0 {
            res = res * x % mod
        }
        x = x * x % mod
        y >>= 1
    }
    return res
}

function sumDecoded(nums: number[]): number {
    const mod = 1000000007n;
    let ans = 0n;

    for (const v of nums) {
        const d = Math.floor(v / 10);
        const w = v % 10;

        const s = String(d);
        const x = BigInt(s.slice(0, w));
        const y = BigInt(s.slice(w));

        ans = (ans + pow(x, y, mod)) % mod;
    }

    return Number(ans);
}

function pow(x: bigint, y: bigint, mod: bigint): bigint {
    let res = 1n;

    while (y > 0n) {
        if (y & 1n) {
            res = (res * x) % mod;
        }
        x = (x * x) % mod;
        y >>= 1n;
    }

    return res;
}

4039. Sum of Decoded Numbers

Description

Solutions

Solution 1: Simulation + Fast Power

Comments