What are the substrings of 1111?

I am not sure if others used the same logic, but the idea is that for the current sum, we multiply the previous sum by 10 and then add "extra". This "extra" grows each iteration, specially by the 1-based index of the current digit times the current digit value. For example, if the current digit is 3 and the 1-based index of this digit is 4, then the "extra" would increase by 12. So at any given digit, the sum is: currentSum = previousSum*10 + (previousExtra + (index * currentDigit)).

Here's how to solve the problem:

Approach

1. Understanding Contributions:

   • Each digit in the number contributes to several substrings based on its position.
   • For example, in the number 123, digit 2 contributes to substrings 12, 23, and 2 itself.

2. Mathematical Insight:

   • Each digit contributes to multiple substrings. You can calculate the total contribution of each digit by considering its position in the number.

3. Efficient Calculation:

   • Use a mathematical formula to calculate the contribution of each digit in a single pass to ensure the solution is efficient.

Steps to Implement the Solution

1. Precompute Contributions:

   • Calculate the total contribution of each digit based on its position using a formula derived from the pattern of substring contributions.

2. Modulo Operation:

   • Since the result could be large, take modulo (10^9 + 7) to keep the numbers manageable and meet problem constraints.

Here’s how you can implement this in PHP:

<?php

function sumOfSubstrings($number) {
    $mod = 1000000007;
    $length = strlen($number);
    $totalSum = 0;
    $multiplier = 1;
    $sum = 0;

    // Iterate over each digit from the end to the start
    for ($i = $length - 1; $i >= 0; $i--) {
        $digit = intval($number[$i]);
        $sum = ($sum + $digit * $multiplier) % $mod;
        $totalSum = ($totalSum + $sum) % $mod;
        $multiplier = ($multiplier * 10 + 1) % $mod;
    }

    return $totalSum;
}

// Example usage:
echo sumOfSubstrings("16") . "\n"; // Output: 23
echo sumOfSubstrings("123") . "\n"; // Output: 164
?>

Explanation:

1. Initialization:

   • Initialize totalSum to accumulate the final result.
   • multiplier is used to track the multiplier for each digit based on its position.
   • sum keeps track of the cumulative sum of contributions for the current position.

2. Iteration:

   • Traverse the number from the end to the start. For each digit:
     • Compute its contribution using the current multiplier.
     • Update sum to include this digit's contribution.
     • Update totalSum to include the updated sum.
     • Update multiplier for the next digit.

3. Modulo Operation:

   • Use modulo (10^9 + 7) to ensure the result does not overflow.

This approach is efficient with a time complexity of (O(n)), where (n) is the length of the number, and handles large numbers gracefully by using modulo operations.

js

const mod = BigInt(10 ** 9 + 7);
const zero = BigInt(0);
const one = BigInt(1);
const ten = BigInt(10);
function substrings(n) {
    const len = BigInt(n.length);
    let sum = zero;
    let f1 = one;
    let f2 = ten;
    for (let i = len - one; i >= zero; i--) {
        [sum, f1, f2] = [
            (sum + BigInt(n[i]) * (i + one) * f1) % mod,
            (f1 + f2) % mod,
            (f2 * ten) % mod
        ];
    }

    return sum;
}