Help me Create its logic

help
1

There was a question where we have to find the count of number of interesting numbers in the range of a and b both inclusive [a,b]. A number is said to be interesting if the number of even digits are odd in number and number of odd digits are even in number…
Eg. 312 is an interesting number as 1,3 i.e., even no. of odd digits and 2 i.e., odd no. of even digits.
Constraints:-
1<=T<=10^5
1<=a<=b<=10^18
INPUT:
1
1 20

OUTPUT:
4

Expalanation:
In range of [1,20] there are only numbers i.e., 2,4,6,8.

Help me generate the proper mathematical formulae for this logic
as it is clear tha number will always be odd in length…

1 Like
2

let’s consider a function , f(), for any given input, answer would be ‘f(b) - f(a-1)’.
now, the function would take a integer as parameter,
def f(n):
#there will be 2 cases
let, len = number of digits in n
1. number of digits in n is odd
2. number of digits in n is even.
in 2nd case, there are no interesting number of even length , so the answer here should be same as the maximum number of length len-1. as len-1 will be odd. e.g.
if n=2456, then the number of interesting numbers for this n should be same as intersting numbers for 999 and for 24, same as 9, for 567423 , same as 99999.
now, for any odd length numbers the total number of interesting numbers is equal to (9*pow(10,len of n-1))/2, it’s an integer division, so for len=1, we have total interesting numbers 4, for 2we have 0 ,as 2 is even , for 3 we have 450 , for 4 we have 0 , for 5 we have 45000 and all, so for any even digit number , we just need to find sum of all odd length numbers which are interesting , i.e. for n=4, the answer would be f(1) + f(3), for n=8, the answer would be f(1)+f(3)+f(5)+f(7), now , f(1)=4 , f(3)=450, f(5)=45000, when you will add these term , yo will find a patter, i.e.
n f(n)
2 4
4 454
6 45454
8 4545454
so , i think you will now generalize this for any given n of even length.

now , for length of odd size, f(n) = f(n-1) + interseting numbers of length of n and value<=n.
now, as f(n-1) is even , so you can calculate that part, now for 2nd part, you should try this, suppose given bumber is 24594, so it;s length is 5 , so f(n-1) is 454, now maintain a sum=0 , and start a loop from the 2nd last digit to 1st digit of the number in reverese order, i.e. 9->5->4->2, and keep a multiplier equal to 5 in the starting i.e. mul =5, now
steps-

  1. if the number is not the first digit, then sum =sum+ muldigit, and update mul=mul10
    2.if number is the first digit , then sum =sum + mul*(digit-1) and break
    i.e here 95 + 550 + 4*500 + (2-1)*5000, and you will get a result, your current ans is sum + f(n-1) , now just need a loop from given number with last digit 0 to the given number and check how many of them are interesting number , add this number to the current sum and this is your result. lt me explain the loop part, in this case, you need a loop from 24590 to 24594, in case of 23546 a loop from 23540 to 23546, it will go upto 10 in worst case, which is efficient, now for every number in this loop check if the number is interseting or not, by the ru;e given in question , i 'm uploading the code for clarity , i know it’s a mess,but i’hve tried my best
1 Like
4 
def interesting(n):
odd=0
even=0
while n>0:
    x=n%10
    if x%2==0:
        even+=1
    else:
        odd+=1
    n=n//10
if even%2!=0 and odd%2==0:
    return True
return False

def f(n):
x=len(str(n))
if x%2==0:
e=x//2-1

    ans  = '45'*e+'4'
    return int(ans)
else:
    if x==1:
        ans=0
    else:
        
        e= (x-1)//2-1
        ans = '45'*e+'4'
    ans = int(ans)
    sum=0
    x=str(n)
    mul=5
    for i in range(len(x)-2,-1,-1):
        if i==0:
            sum = sum+mul*(int(x[i])-1)
        else:
            sum =sum+mul*(int(x[i]))
        mul=mul*10
    x=(n//10)*10
    for i in range(x,n+1):
        if interesting(i):
            sum+=1
    return sum+ans

t=int(input())
for _ in range(t):
a,b=map(int,input().split())
print(f(b)-f(a-1))

5

Thank You very much…