Dynamic Programming: Counting numbers in between

Question

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!

Answer 1

I will explain you in some steps:

First step:

For solving this kind of range problems between X and Y always make it simple by counting between 0 to X and 0 to Y-1, then subtract the result. i.e. if you have a function like f(N) that calculates the numbers that have at least half their digits the same between 0 and N, then your final result is:

f(X) - f(Y-1)

Second step:

Next we have to compute f(N). We split this function into 2 sub functions, one for calculating the result for numbers having the same number of digits with N (lets call it f_equal), and the other for counting the qualified numbers having digits less the N (let's call it f_less). E.g. if N is 19354, we count the qualified numbers between 0 to 9999, then in another method count the favorite numbers between 10000 to 19354, after that we sum up the result. Next, I'll explain you how to implement these two methods.

Third step:

Here, we want to compute f_less method. you can do it by some math, but I always prefer to write a simple DP for solving these tasks. I will write the recursive function whether you can use memoization or you can make it bottom-up with some loops (I'll leave it as a practice for you).

long long f_less(int curDigit, int favNum, int favNumCountSoFar, int nonFavNum, int nonFavNumCountSoFar, int maxDigit){
    if(curDigit == maxDigit ){
        //for numbers with even maxDigit there may be a case when we have 2 favorite numbers
        //and we should count them only once. like 522552
        if(favNumCountSoFar*2 == maxDigit && favNumCountSoFar == nonFavNumCountSoFar) return 1;
        if(2*favNumCountSoFar >= maxDigit) return 2;
        return 0;
    }
    long long res = 0;
    for(int i=(curDigit==0?1:0);i<=9;++i) //skip the leading zero
        if(i==favNum)
            res += f_less(curDigit+1, favNum, favNumCountSoFar + 1, nonFavNum, nonFavNumCountSoFar,maxDigit);
        else
            res += f_less(curDigit+1, favNum, favNumCountSoFar, i, (i==nonFavNum?nonFavNumCountSoFar+1:1),maxDigit);
    return res;
}

And call it for all numbers through 0 to 9:

long long res = 0;
for(int maxDigit = 1; maxDigit < NUMBER_OF_DIGITS(N); ++maxDigit)
    for(int favNumber = 0; favNumber < 10; ++favNumber)
        res += f_less(0, favNumber, 0, -1, 0, maxDigit);

Fourth Step:

Finally we have to compute f_equal. Here we have to keep the number in a string to always check whether we are still in the range below N or not in the recursive function. Here is the implementation of f_equal (again use memoization or make it bottom-up):

string s = NUM_TO_STRING(N);
int maxDigit = s.size();
long long f_equal(int curDigit, int favNum, int favNumCountSoFar,int nonFavNum, int nonFavNumCountSoFar, bool isEqual){ //isEqual checks that whether our number is equal to N or it's lesser than it 
    if(curDigit == maxDigit ){
        //for numbers with even maxDigit there may be a case when we have 2 favorite numbers
        //and we should count them only once. like 522552
        if(favNumCountSoFar*2 == maxDigit && favNumCountSoFar == nonFavNumCountSoFar) return 1;
        if(2*favNumCountSoFar >= maxDigit) return 2;
        return 0;
    }
    long long res = 0;
    for(int i=(curDigit==0?1:0);i<=9;++i){ //skip the leading zero
        if(isEqual && i>(s[curDigit]-'0')) break;
        if(i==favNum)
            res += f_equal(curDigit+1, favNum, favNumCountSoFar + 1, nonFavNum, nonFavNumCountSoFar, isEqual && (i==(s[curDigit]-'0')));
        else
            res += f_equal(curDigit+1, favNum, favNumCountSoFar, i, (i==nonFavNum?nonFavNumCountSoFar+1:1), isEqual && (i==(s[curDigit]-'0')));
    } 
    return res;
}

And call it:

long long res = 0;
for(int favNumber = 0; favNumber < 10; ++favNumber)
    res += f_equal(0, favNumber,0, -1, 0, true);

The final result is res/2. The code is tested and works well.

Answer 2

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.

Answer 3

Here is a partial combinatoric answer. I leave out how to use the function to construct a full answer.

(Please see here for the same code with more elaborate comments: https://repl.it/@gl_dbrqn/AllSteelblueJuliabutterfly)

Fixing the leftmost digit(s), L, in a number with R digits to the right of L, we can calculate how many ways we can distribute (N / 2) or more of digit d by:

Python Code

import math, operator, collections   

# Assumes L has at least one digit set
# f({'string':'12', 'digit_frequencies':[0,1,1,0,0,0,0,0,0,0], 'num_digit_frequencies': 2}, 6)
def f(L, N):
  R = N - len(L['string'])

  count = 0
  counted = False

  for digit_frequency in L['digit_frequencies']:       
    start = int(math.ceil(N / 2.0)) - digit_frequency
    if start > R:
      continue

    for i in xrange(start, R + 1):
      if not (N & 1) and not counted:
        if L['num_digit_frequencies'] == 1 and not digit_frequency and i == N / 2:
          count = count - choose(R, i)

        if L['num_digit_frequencies'] == 2 and digit_frequency and not any([x > N / 2 for x in L['digit_frequencies']]) and i + digit_frequency == N / 2:
          count = count - choose(R, i)
          counted = True

      m = 9**(R - i)
      n = R - i + 1
      k = i

      count = count + m * choose(n + k - 1, k)

  return count


# A brute-force function to confirm results 
# check('12', 6)
def check(prefix, length):
  result = [x for x in xrange(10**(length - 1), 10**length) if len(str(x)) == length and str(x).startswith(prefix) and isValid(str(x))]

  print result
  return len(result)

def isValid(str):
  letters = collections.Counter(str)
  return any([x >= math.ceil(len(str) / 2.0) for x in letters.values()])


# https://stackoverflow.com/questions/4941753/is-there-a-math-ncr-function-in-python
def choose(n, r):
  r = min(r, n-r)
  if r == 0: return 1
  numer = reduce(operator.mul, xrange(n, n-r, -1))
  denom = reduce(operator.mul, xrange(1, r+1))
  return numer//denom

Answer 4

The number 0 is just shorthand. In reality there are an infinite number of leading zeros and an infinite number of trailing zeros (after the decimal point), like ...000000.000000....

For all integers it's obvious that there are at least as many 0s after the decimal point as there are non-zero digits before the decimal point; so all integers can be counted.

There are an infinite number of numbers between 0 and 1; and all of these have at least as many 0s to the left of the decimal point as they have non-zero digits after the decimal point. The same applies to numbers between 0 and -1.

For almost all floating point numbers that a computer can store, there simply isn't enough bits to cancel out all the leading and trailing zeros.

The only numbers that can't be counted are positive and negative infinity, and some but not all irrational numbers that are <= 1 or >= -1.

Code:

float getCount(int x, int y) {
    if(x == y) return 0.0; // Special case (no numbers are between x and y)
    return INFINITY;       // The closest value to the correct answer that a computer can use
}