CODEWITHSUNDEEP
algorithmnumberssubstring
Mounir
Mounir

Reputation: 21

Algorithm for counting substrings in a numerical range

I'm looking for a fast algorithm that can be used to solve this problem: Giving A and B integers (in the range [0,10^18]), and giving a list of N (N<=1000) numerical substrings; the goal is to count all the numbers in the range [A,B] containing any of the N substrings. We've always A<=B and the numerical substrings are also integers in the range [0,10^18].

Example1: if A=10, B=22, and giving N=2 substrings={1,10} ; the count would be = 11; counting the numbers: 10->19 and 21.

Example2: If A=175, B=201, and giving N=3 substrings={55,0,200} ; the count would be = 4; counting the numbers: 180, 190, 200 and 201.

The straight-forward way is to analyse each integer in the range [A,B], one after another, but it's not a solution since the range can be so big (until 10^18 integers).

One first thing I did to reduce the problem complexity is to delete some useless substrings from the original list of N substrings, such that "no substring is contained in another". For example: {1,10} becomes {1} and {55,0,200} becomes {55,0}. This won't change the final count.

Next, even assuming we can get the count for one substring in the range [A,B], we still cannot sum this count with those of other substrings from the list, as one number can contain many substrings and should not be counted more than once.

Any ideas to solve the problem et get the wanted count?

Upvotes: 2

Views: 356

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

I think it is more of a combinatorial problem.

  1. Calculate the possible number of digits of numbers between A and B. For example between 2 and 2000, the number of digits can be 1, 2, 3 or 4. With 1 digit, you need to calculate for numbers > 2 and for 4 digits, you have to calculate the numbers less than 2000, i.e, beginning with 1.

  2. If the number of digits is k, and you have to say find the numbers containing substring 234, then choose where you will place that substring (in k-2 ways) and then find the number of permutations for all the possible remaining digits (i think in 10 ^ (k-3) ways). Ofcourse you will have to discount for leading zeroes etc.

  3. Repeat this for all substrings.

  4. Now you will have to subtract the ones that contain more than one substrings. Repeat the above procedure for all combinations of substrings and subtract it from the calculated value.

Upvotes: 1

Related Questions