Hackerrank: Lucky Number Eight (Dynamic Programming)

Problem statement

Given an n-digit positive integer, count and print the number of subsequences formed by concatenating the given number's digits that are divisible by 8. As the result can be large, print the result modulo 109 + 7.

Input Format

The first line contains an integer denoting n.

The second line contains a string describing an n-digit integer.

Constraints

· 1 ≤ n ≤ 2 x 105

Output Format

Print a single integer denoting the count of subsequences of the given number that are divisible by 8, modulo 109 + 7.

Sample Input 0

3

968

Sample Output 0

3

Explanation 0

The numbers obtained from subsequences of 968 are 9,6,8,96,68,98 and 968. Three of these numbers (i.e., 968,96, and 8) are divisible by 8, so we print the value of 3 mod (109 + 7) = 3 as our answer.

My introduction of the algorithm

The algorithm is a medium level one in the hackerrank contest of week of code 28 from January 9 to 15, 2017. I wrote an algorithm in the contest, and the code has over 300 lines of code, with timeout issue, not efficient.

So I learned to use dynamic programming method to solve the algorithm today. I read the editorial notes on hackerrank first, and studied one of submissions, and then built a frequency table for the sample test case 968 to clear my questions from code reading. And then I wrote the algorithm following the ideas showing in the frequency table, using dynamic programming bottom-up method.

Hackerrank Editorial Notes

In this problem, you are given a sequence of digits of length N. You have to find the number of non-contiguous subsequences, such that the number formed by their concatenation is divisible by 8.

Observe a bit,

The number is formed by concatenating the non-contiguous subsequences, which implies that the number itself is a subsequence and vice-versa.

So the problem boils down to counting the ways you can make a subsequence divisible by 8. This can be done by Dynamic Programming.

At any pos

I find it kind of silly that you receive n as the first input and the second input in a n-digit number. I'd think things could be simpler if you just received some input number where you can quickly determine its length to compute n. But I'm guessing that the rules of the contest.

One area of a small bit of inefficiency - as well as naming confusion - is regarding to number[i] - '0'. The truth is number is not a number. It's a string composed of digits, which you trust is valid input since you don't validate it. That's fine as long as the rules are they absolutely will be passing you an integer as as string.

You can perhaps improve readability and performance somewhat by converting the string of digits to an integer array once, and pass that to BuildFrequencyTableFromBottomUp. This can be something simple like:

private static int[] ToIntegerArray(string stringOfDigits) => stringOfDigits.Select(digit => digit - '0').ToArray();

Don't know how many total inner loops you are going through. Usually if it's a few hundred thousand, it would not be a factor on performance. Now if it were several billion, converting to an integer array first would have measurable improvement.

You would then need to change the relevant code in your method.

StackExchange Code Review Q#157119, answer score: 3