Round H 2020 Google Kick Start Boring Numbers Problem | Java

Problem

Ron read a book about boring numbers. According to the book, a positive number is called boring if all of the digits at even positions in the number are even and all of the digits at odd positions are odd. The digits are enumerated from left to right starting from 1. For example, the number 1478 is boring as the odd positions include the digits {1, 7} which are odd and even positions include the digits {4, 8} which are even.

Given two numbers L and R, Ron wants to count how many numbers in the range [L, R] (L and R inclusive) are boring. Ron is unable to solve the problem, hence he needs your help.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line with two numbers L and R.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the count of boring numbers.

Limits

Time limit: 20 seconds. Memory limit: 1 GB. 1 ≤ T ≤ 100.

Test Set 1

1 ≤ L ≤ R ≤ 103.

Test Set 2

1 ≤ L ≤ R ≤ 1018.

Sample

In Sample Case #1, the numbers in the range are {5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15} out of which {5, 7, 9, 10, 12, 14} are boring, hence the answer is 6.

In Sample Case #2, the numbers in the range are {120, 121, 122, 123, 124, 125} out of which {121, 123, 125} are boring, hence the answer is 3.

In Sample Case #3, the numbers in the range are {779, 780, 781, 782, 783} out of which {781, 783} are boring, hence the answer is 2.

Java Code

import java.util.*; public class Solution{ public static long five[] = new long[20]; public static long pre[] = new long[20]; public static class Solu{ int a[] = {0,0,1,1,2,2,3,3,4,4}; int b[] = {0,1,1,2,2,3,3,4,4,5}; public long count(long x) { String s = Long.toString(x); int n = s.length(); char s1[] = s.toCharArray(); long ans = pre[n-1]; for(int i=1; i<=n; ++i) { int c = s1[i-1] - '0'; if(c% 2 != i% 2) { ans += five[n-i] * b[c]; break; }else { ans += five[n-i] * a[c]; if(i==n) ans++; } } return ans; } public void solve(int case_num,long L,long R) { System.out.printf("Case #%d: %d\n",case_num, count(R)- count(L-1)); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t= sc.nextInt(); five[0] = (long) 1; for(int i=1; i<20; ++i) { five[i] = five[i-1]*5; } pre[0] = (long) 0; for(int i=1; i<20; ++i) { pre[i] = pre[i-1]+five[i]; } for(int i=1; i<=t; ++i) { Solu solution = new Solu(); long l = sc.nextLong(); long r = sc.nextLong(); solution.solve(i,l,r); } } }

Round H 2020 - Kick Start 2020 Editor. Here you can check whether your code satisfies Time and Space Complexity of the Problem.

Here is the link for Google KickStart Round F 2021 Trash Bins Problem.