Created
March 6, 2017 22:56
-
-
Save jianminchen/c4c26f06ea7daab2e10ceb222dea7d0e to your computer and use it in GitHub Desktop.
Hackerrank - lucky 8 - code review
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace Hackerrank_LuckyNumber8_DP_Studycode | |
{ | |
/* | |
* Problem statement: | |
* | |
* https://www.hackerrank.com/contests/w28/challenges/lucky-number-eight | |
* | |
* Study dynamic programming solution | |
* | |
* questions on two things: | |
* first value is 1, count[0][0] = 1, why? count 0 as the first digit. see the frequency table. | |
* second, count[n - 1][0] + Module - 1, why? Remove number 0 as the answer. | |
*/ | |
class Program | |
{ | |
public static long Module = 1000000007; | |
static void Main(string[] args) | |
{ | |
int n = Convert.ToInt32(Console.ReadLine()); | |
String number = Console.ReadLine().ToString(); | |
int[][] count = new int[n][]; // subsequences | |
for (int i = 0; i < n; i++) | |
{ | |
count[i] = new int[8]; | |
} | |
int SIZE = 8; | |
count[0][0] = 1; // ask why here? count 0 as the first digit | |
count[0][(number[0] - '0') % SIZE]++; | |
// build a frequency table - | |
for (int i = 1; i < n; i++) | |
{ | |
// subseqences - just ignore the current elment | |
for (int remainder = 0; remainder < SIZE; remainder++) | |
{ | |
count[i][remainder] = count[i - 1][remainder]; | |
} | |
// iterate each element in the array - go over all possible remainders in ascending order | |
for (int remainder = 0; remainder < SIZE; remainder++) | |
{ | |
long current = count[i - 1][remainder]; | |
// if the remainder's related count is 0, then no possible subsequences to the nextRemainder | |
// skip the remainder. | |
if (current == 0) | |
{ | |
continue; | |
} | |
int nextRemainder = (10 * remainder + (number[i] - '0')) % SIZE; | |
count[i][nextRemainder] = (Int32)((count[i][nextRemainder] + current) % Module); | |
} | |
} | |
Console.WriteLine((count[n - 1][0] - 1) % Module); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment