Count numbers deleted by removing consecutive digit pairs that don't sum to 17

user_12519110 0
Viewed 3174

Below is the problem statement that I have:

You get number written in base 10, you have to delete it completely by choosing two consecutive digits and deleting them. But the sum of those 2 digits should not be 17. We call the numbers which are fully deleted by repeating the above operation as "Good".

Example:

  1. 9889 => Delete 88 to get 99
  2. 99 => Delete 99 to fully delete number. Conclusion: 9889 is good. NOTE: We cannot remove 98 or 89 as the sum of these 2 digits is 17.

Given a number N(even) you want to find the number of good N-digit number modulo 10^9 + 7. Include in the count the N digit numbers containing leading zeros, too.

Test Cases:

Case 1:

Input: 2
Output: 98

Case 2:

Input: 4
Output: 9926

Case 3:

Input: 442
Output: 417551213

I have tried solving this using various codes but not able to get the result.

dynamic-programming algorithm java
3 Answers

For each sequence of the last possible bad state, there must have been a forced sequence that generated it. Look at the locations of possible wild-cards (the digits that offer choice are the ones of interest, of course), and try to find a pattern.

In the following examples, for symmetry, switch 9s with 8s; xs are wildcards:

Input length 4, bad result 9898:

9898

Input length 4, bad result 98:

989x
98x8
9x98
x898

We can clearly see from the two above why we get the output, 9926 good 4-digit numbers.

Input length 6, bad result 9898:

98989x
9898x8
989x98
98x898
9x9898
x89898

Input length 6, bad result 9898 OR 98:

9898xx
989xx8
98xx98
9xx898
xx9898

Input length 6, bad result 98:

989x9x
98x8x8
...
9x989x
...

etc.

Python code:

# https://gist.github.com/rougier/ebe734dcc6f4ff450abf
def binom(n,k):
  if not 0<=k<=n: return 0
  b=1
  for t in range(min(k,n-k)):
    b*=n; b//=t+1; n-=1
  return b

def f(n):
  bads = 0
  
  for k in range((n - 2) // 2 + 1):
    bads += 9**k * binom(n, k)
  
  return (10**n - 2 * bads) % (10**9 + 7) 
  
print(f(442)) # 417551213
user_20347870

Try with using a tree to try every possible solution. The real problem is that, you have to predict what digit will stay and if you can delete them without having a sum of 17. For exemple, if you have 9823 you can delete 23 but you'll be blocked with 98 at the end.

You can try building a tree with every branch being a possibility of deletion. If all of the branches are blocked you get back to the previous node

user_144142600

Not wanting to spoil the coding, but whether a number is good, could be done with backtracking.

    solve(9889);

public static void solve(int num) {
    try {
        solve(num, new LinkedList<>());
        System.out.println("Not found");
    } catch (FoundException fe) {
        System.out.printf("%d%n", num);
        fe.result.forEach(pair -> System.out.printf("-> %d, having deleted %d%n",
            pair.getKey(), pair.getValue()));
    }
}

private static class FoundException extends RuntimeException {
    public final List<Pair<Integer, Integer>> result;

    public FoundException(List<Pair<Integer, Integer>> result) {
        this.result = result;
    }
}

private static void solve(int num, LinkedList<Pair<Integer, Integer>> partialResult) {
    if (num == 0) {
        throw new FoundException(partialResult);
    }
    int tenPower = 1;
    while (num >= tenPower) {
        int n = num / tenPower;
        int del = n % 100;
        if (del % 10 + del / 10 != 17) {
            int n2 = (n / 100) * tenPower + (num % tenPower);
            partialResult.addLast(new Pair<>(n2, del));
            solve(n2, partialResult);
            partialResult.removeLast();
        }
        tenPower *= 10;
    }
}

The problem seems to be formulated such that an int (31 bits unsigned int) suffices. Hence I tried working with int instead of a list of digits.

An other feature: using an exception to return from deep inside recursion to the top level with a positive result. The traditional way would be to check the result of a recursive call.

Note: the actual problem is a more mathematical one.

user_9848230
Related