Header Ads Widget

Polo the Penguin and the Numbers | codechef solution

Rajnish Tripathi 12:05

Polo, the Penguin, likes numbers. He says that the goodness of a number is itself multiplied by the number of digits in it's decimal representation. For example, the goodness of the integer 474 is 474*3 = 1422.

Help him to count the sum of goodness of all integers from L to R, inclusive. Since the answer can be too large, output it modulo 1,000,000,007 (10^9+7).

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The only line of each test case contains the pair of integers L and R, separated by a single space.

Output

For each test case, output a single line containing the answer to the corresponding test case.

Constraints

  • 1 ≤ T ≤ 1,000
  • 1 ≤ L ≤ R ≤ 1,000,000,000 (10^9)

Sample 1:

Input
Output
1
9 12
75

Explanation:

Example case 1. The answer is 9*1 + 10*2 + 11*2 + 12*2 = 75.

 Code(C++):-

#include <bits/stdc++.h>
using namespace std;
#define ull long long int
#define m (ull)(1000000007)

int main()
{
int t;
cin >> t;
while (t--)
{
int l, r;
cin >> l >> r;
int dl = to_string(l).size(), dr = to_string(r).size();
ull S = 0;
while (dl <= dr)
{
ull a = max(l, (int)pow(10, (dl - 1))), an = min((int)((ull)pow(10, dl) - 1), r);
ull s1 = (an - a + 1), s2 = (a + an), s = 0;
s = (s1 % 2 == 0 ? ((s1 / 2) * s2 * dl) : ((s2 / 2) * s1 * dl));
S += (s % m);
S %= m;
dl++;
}
cout << S << "\n";
}
return 0;
}

Code(JAVA):-
import java.io.*;
import java.util.StringTokenizer;

/**
* Created by varun on 21/1/18.
*/
class PPNUM {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
String str = br.readLine();
StringTokenizer st = new StringTokenizer(str, " ");
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
long ans = 0;
int num1 = numDigits(l), num2 = numDigits(r);
long power = (int) Math.pow(10, num1);
while (num1 <= num2) {
int upper = power - 1 > r ? r: (int)power-1;
ans = (ans + (((long)(l + upper) * (upper - l + 1)) / 2) *(long) num1) % 1000000007;
l = upper + 1;
power *= 10;
num1++;
}
bw.write(ans + "\n");
bw.flush();
}
}

public static int numDigits(int ele) {
int count = 0;
while (ele != 0) {
count++;
ele /= 10;
}
return count;
}
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments