Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 6, 2017 22:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/c4c26f06ea7daab2e10ceb222dea7d0e to your computer and use it in GitHub Desktop.
Save jianminchen/c4c26f06ea7daab2e10ceb222dea7d0e to your computer and use it in GitHub Desktop.
Hackerrank - lucky 8 - code review
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