### siddhantuniyal's blog

By siddhantuniyal, history, 2 months ago,

I tried this problem with L = 1 , R = 9999

The answer is 4275 (9 + 9*8 + 9*9*8 + 9*9*8*7) , but with the below approach I am getting 5617. I am trying this approach, because it is generalized for any L and R.Please help me in finding out what I am doing wrong.

Observation 1 : The numbers following this conditions are always >= 1

Observation 2 : let x = 456 , y = 467. We are only able to tell that y > x because we started from the first digit , iterated towards the last digit and compared digits. At the first point of inequality , we were able to conclude that 456 < 457

Hence , I am iterating over all possible points of inequality between digits. here 1 is represented as 0001

if inequality is at 1st digit , that means 1st digit has to be 1,2,3..9 -> hence 9C1. And for the rest 3 digits , choose any 3 digits from the remaining 9 digits (10 digits originally and removing one because we placed it at 1st digit) and rearrange them -> 9C3 * 3!

if inequality is at 2nd digit , that means 1st digit = 0 and 2nd digit = 1,2..9 -> hence 9C1. And for the rest 2 digits , choose any 2 digits from the remaining 8 (10 originally , one (0) already at 1st digit , one chosen for 2nd digit) and rearrange -> 8C2 * 2!

if inequality is at 3rd digit , that means 1st and 2nd digit -> 0 and 3rd digit = 1,2,3..9 -> 9C1. and for the remaining digit , 8C1 (0 already used at 1st and 2nd digit , and one already chosen for 3rd digit).

for 4th digit -> 8C1

and we also have to add 1 to the answer , because , we are only considering some number between 1 and 9999 which has atleast one digit unequal to its corresponding digit in 1. but , 1 itself can be part of answer and here it is.

so this gives 9C1 * 9C3 * 3! + 9C1 * 8C2 * 2! + 9C1 * 8C1 + 8C1 + 1 , which is 5617 and wrong.

• 0

By siddhantuniyal, history, 3 months ago,

My Approach

The Editorial

I don't understand why inclusion-exclusion is required , shouldn't my approach work?

Please help me in understanding why my approach is wrong.

Thank You

• -1

By siddhantuniyal, history, 4 months ago,

The problem : MATMOD

My solution (with complete explanation in comments) : My Solution

I have taken a random accepted submission , and compared my code's output with every possible edge case I could think of, and my output matches it every single time.

The accepted submission : Other Solution

Still, I am getting wrong answer.