Given a range [L, R], the task is to find the sum i * countDigits(i)2 for all i ? [L, R] where countDigits(i) is the count of digits in i.
That is, find:
L * countDigits(L)2 + (L + 1) * countDigits(L + 1)2 + ….. + R * countDigits(R)2.
Examples:
Input: L = 8, R = 11
Output: 101
8 * 12 + 9 * 12 + 10 * 22 + 11 * 22 = 8 + 9 + 40 + 44 = 101
Input: L = 98, R = 102
Output: 2
98 * 22 + 99 * 22 + 100 * 32 + 101 * 32 + 102 * 32 = 3515
Approach: We break the segment [L, R] into several segments of the numbers with the same number of digits.
[1 – 9], [10 – 99], [100 – 999], [1000 – 9999], [10000 – 99999], [100000 – 999999], [10000000 – 99999999] and so on.
When L and R are of the same length then the required sum will be countDigits(L)2 * (L + R) * (R – L + 1) / 2
Proof:
Let [L, R] = [10, 14] where L and R are of the same length i.e. 2.
Therefore, the sum for the segment [L, R] will be 10 * 22 + 11 * 22 + 12 * 22 + 13 * 22 + 14 * 22.
Take 22 common, 22 * (10 + 11 + 12 + 13 + 14) = totalDigits2 * (Sum of AP)
Sum of AP = (no of terms / 2) * (first term + last term) i.e. (R – L + 1) * (L + R) / 2.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define MOD 1000000007// Function to return the required sumint rangeSum(int l, int r){ int a = 1, b = 9, res = 0; for (int i = 1; i <= 10; i++) { int L = max(l, a); int R = min(r, b); // If range is valid if (L <= R) { // Sum of AP int sum = (L + R) * (R - L + 1) / 2; res += (i * i) * (sum % MOD); res %= MOD; } a = a * 10; b = b * 10 + 9; } return res;}// Driver codeint main(){ int l = 98, r = 102; cout << rangeSum(l, r); return 0;} |
Java
// Java implementation of the approachclass GFG { static final int MOD = 1000000007; // Function to return the required sum static int rangeSum(int l, int r) { int a = 1, b = 9, res = 0; for (int i = 1; i <= 10; i++) { int L = Math.max(l, a); int R = Math.min(r, b); // If range is valid if (L <= R) { // Sum of AP int sum = (L + R) * (R - L + 1) / 2; res += (i * i) * (sum % MOD); res %= MOD; } a = a * 10; b = b * 10 + 9; } return res; } // Driver code public static void main(String args[]) { int l = 98, r = 102; System.out.print(rangeSum(l, r)); }} |
Python3
# Python3 implementation of the approach MOD = 1000000007;# Function to return the required sum def rangeSum(l, r) : a = 1; b = 9; res = 0; for i in range(1, 11) : L = max(l, a); R = min(r, b); # If range is valid if (L <= R) : # Sum of AP sum = (L + R) * (R - L + 1) // 2; res += (i * i) * (sum % MOD); res %= MOD; a *= 10; b = b * 10 + 9; return res; # Driver code if __name__ == "__main__" : l = 98 ; r = 102; print(rangeSum(l, r)); # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;class GFG { const int MOD = 1000000007; // Function to return the required sum static int rangeSum(int l, int r) { int a = 1, b = 9, res = 0; for (int i = 1; i <= 10; i++) { int L = Math.Max(l, a); int R = Math.Min(r, b); // If range is valid if (L <= R) { // Sum of AP int sum = (L + R) * (R - L + 1) / 2; res += (i * i) * (sum % MOD); res %= MOD; } a = a * 10; b = b * 10 + 9; } return res; } // Driver code public static void Main() { int l = 98, r = 102; Console.WriteLine(rangeSum(l, r)); }} |
PHP
<?php// PHP implementation of the approach$MOD = 1000000007;// Function to return the required sumfunction rangeSum($l, $r){ global $MOD; $a = 1; $b = 9; $res = 0; for ($i = 1; $i <= 10; $i++) { $L = max($l, $a); $R = min($r, $b); // If range is valid if ($L <= $R) { // Sum of AP $sum = ($L + $R) * ($R - $L + 1) / 2; $res += ($i * $i) * ($sum % $MOD); $res %= $MOD; } $a = $a * 10; $b = $b * 10 + 9; } return $res;}// Driver code$l = 98; $r = 102;echo rangeSum($l, $r);// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// Javascript implementation of the approachMOD=1000000007// Function to return the required sumfunction rangeSum(l, r){ var a = 1, b = 9, res = 0; for (var i = 1; i <= 10; i++) { var L = Math.max(l, a); var R = Math.min(r, b); // If range is valid if (L <= R) { // Sum of AP var sum = (L + R) * (R - L + 1) / 2; res += (i * i) * (sum % MOD); res %= MOD; } a = a * 10; b = b * 10 + 9; } return res;}// Driver codevar l = 98, r = 102;document.write(rangeSum(l, r));// This code is contributed by noob2000.</script> |
3515
Time Complexity: O(10), as we are using a loop to loop 10 times.
Auxiliary Space: O(1), as we are not using extra space.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
