sum-of-k-digit-numbers-in-a-range

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given three integers <code>l</code>, <code>r</code>, and <code>k</code>.

Consider all possible integers consisting of exactly <code>k</code> digits, where each digit is chosen independently from the integer range <code>[l, r]</code> (inclusive). If 0 is included in the range, leading zeros are allowed.

Return an integer representing the sum of all such numbers.​​​​​​​ Since the answer may be very large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: l = 1, r = 2, k = 2

Output: 66

Explanation:

<ul>
	<li>All numbers formed using <code>k = 2</code> digits in the range <code>[1, 2]</code> are <code>11, 12, 21, 22</code>.</li>
	<li>The total sum is <code>11 + 12 + 21 + 22 = 66</code>.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: l = 0, r = 1, k = 3

Output: 444

Explanation:

<ul>
	<li>All numbers formed using <code>k = 3</code> digits in the range <code>[0, 1]</code> are <code>000, 001, 010, 011, 100, 101, 110, 111</code>​​​​​​​.</li>
	<li>These numbers without leading zeros are <code>0, 1, 10, 11, 100, 101, 110, 111</code>.</li>
	<li>The total sum is 444.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: l = 5, r = 5, k = 10

Output: 555555520

Explanation:​​​​​​​

<ul>
	<li>5555555555 is the only valid number consisting of <code>k = 10</code> digits in the range <code>[5, 5]</code>.</li>
	<li>The total sum is <code>5555555555 % (109 + 7) = 555555520</code>.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= l &lt;= r &lt;= 9</code></li>
	<li><code>1 &lt;= k &lt;= 109</code></li>
</ul>