Even Or Odd
LEVEL:Expert
Description
Count of integers in a range which have even number of odd digits and odd number of even digits
Given a range [L, R], the task is to count the numbers which have even number of odd digits and odd number of even digits.
For example,
1. 8 has 1 even digit and 0 odd digit, Satisfies the condition since 1 is odd and 0 is even.
2. 545 has 1 even digit and 2 odd digits, Satisfies the condition since 1 is odd and 2 is even.
3. 4834 has 3 even digits and 1 odd digit, Does not satisfy the condition since there are odd numbers(i.e 1) of odd digits.
Input Format
First line contains two integers sperated by space.
Output Format
Print total numbers count
1 9
4
1 19
4
123 984
432
Login to see Discussion
Approach
Approach:
Case 1
There is a pattern in which these numbers occur between 1 and 10^{k} (where 1<=k<=18).
Number of occurrences from
1 to 10 and 1 to 100 are 4
1 to 1000 and 1 to 10000 are 454
1 to 10000 and 1 to 100000 are 45454
Case 2
If the number of digits in a number is even then it cannot satisfy the given condition because we need an odd number(of digits) and an even number(of digits) to satisfy our condition and odd number + even number is always odd So if the number of digits for a given number(say n) is even then its number of occurrences from 1 is equal to the number of occurrences from 1 to largest 10^{k} (1<=k<=18) which is less than n
Example:
Let n = 19, number of digits in 19 are 2
Therefore number of occurrences from 1 to 19 = number of occurrences from 1 to 10 (since 10 the largest 10^{k} less than 19)
Case 3
If number of digits for a given number(say n) are odd then number of occurrences between 10^{k}+1 and n is equal to
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution