chill21's blog

Distinct digits in a range using BIT
By chill21, history, 8 years ago, In English

You are given an array of size n find number of distinct digits in the numbers in a given range ? I know how to do it with segment tree , please help me to do it with Binary indexed tree .

thanks in advance :)

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use one BIT per digit so you can easily found the frequency of any given digit in a range. You can solve every query in O(D * log(N)) where D = 10.

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

You know how to do it with segment tree then you must be familiar with the logic. Then I guess problem is in the implementation part.
Here is my solution.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

By the way if you have multiple queries which can be processed offline, this can also be done using square root decomposition (also referred to as Mo's algorithm).

→ Reply