siddhantuniyal's blog

By siddhantuniyal, history, 4 weeks ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by siddhantuniyal (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by siddhantuniyal (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by siddhantuniyal (previous revision, new revision, compare).

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

I was asked this question in Online Assessment of JPMC. You can do it using precomputation too. Here is how —
Declare an array of size 1e6+1 (Assuming the max value of r can be 1e6).
For each number (say)j from 1 to 1e6, if it contains all distinct numbers, make arr[j]=1, else arr[j]=0.
Then calculate cumulative sum of the array, such that, arr[i]+=arr[i-1].
Now, for each query, [l,r], your answer will be arr[r]-arr[l-1].

Code
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

explore digit dp