Dynamic Programming: Counting numbers in between

Viewed 924

Given two numbers X and Y, how many numbers exist between them inclusive that have at least half their digits the same? For example, 1122 and 4444 would work, while 11234 and 112233 would not work.

Obviously, the most straightforward way is to start at X and increment by 1 all the way to Y, and then check each number, but that is way too slow, as the boundaries for X and Y are between 100 and 10^18. I know that it is some form of dynamic programming, and that I should use strings to represent the numbers, but I can't get much further.

Any help would be accepted. Thanks!

4 Answers

Obviously, then, you won't do this by considering all numbers in the range. Instead, think in terms of generating the numbers you want. For instance, design a function that will generate all of the qualifying numbers, given no more than the length in digits.

For instance, for 5 digits, you want all the numbers with at least three 1's, or three 2's, or ... Can you do that in one pass, or do you need to separate those with exactly three 1's from those with more?

Now that you've thought about that, think about this: instead of generating all those numbers, just count them. For instance, for three 1's and two other digits, you have 9*9 pairs of other digits (make sure not to double-count things such as 11122). You can arrange the 1's in 10 ways, with a possible swap of the other two digits.

Note that the problem is a little different with an even quantity of digits: you have to avoid double-counting the half-and-half numbers, such as 111222.

Does that get you moving?


RESPONSE TO COMMENTS 03 Dec

@bobjoe628: this is not intended to be a complete algorithm; rather, it's a suggestion to get you started. Yes, you have several combinatoric problems to handle. As for 11122233, I'm not sure I understand your concern: as with any such permutation problem, you have to handle each digit being interchangeable with its siblings. There are 10C5 ways to distribute the 1's; in the remaining spots, there are 5C3 ways to distribute the 2's; the other two slots are 3'3. Readily available algorithms (i.e. browser search) will cover those machinations.

I trust that you can write an algorithm to generate numbers: note that you need only one combination of digits, so it's safe to simply generate digits in ascending order, as you've been giving your examples: 1111122233. Once you've generated that, your combinatoric code should cover all unique permutations of those digits.

Finally, note that most languages have support packages that will perform permutations and combinations for you.

Related