BALNUM - Balanced Numbers
Balanced numbers have been used by mathematicians for centuries. A positive integer is considered a balanced number if:
1) Every even digit appears an odd number of times in its decimal representation
2) Every odd digit appears an even number of times in its decimal representation
For example, 77, 211, 6222 and 112334445555677 are balanced numbers while 351, 21, and 662 are not.
Given an interval [A, B], your task is to find the amount of balanced numbers in [A, B] where both A and B are included.
The first line contains an integer T representing the number of test cases.
A test case consists of two numbers A and B separated by a single space representing the interval. You may assume that 1 <= A <= B <= 1019
For each test case, you need to write a number in a single line: the amount of balanced numbers in the corresponding interval
Input: 2 1 1000 1 9
Output: 147 4
time limit is strict ! A small factor in complexity gave me tleLast edit: 2019-08-17 10:33:55
Last edit: 2017-08-30 16:48:46
The number of test cases is relatively "small", i.e. there won't be 1000 test cases with 19 digits number.
awesome problem :) !!
@Buda IM: I completely agree with you ,test cases should be mentioned in the problem description.
Buda IM (retired):
I think number of test cases should be in problem description. Because you should know whether to do overkill by precalculating all results, or calc solution for each test alone. But usually authors leave out that number ..
You may assume a thousand.
How many test cases are there?