Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 6, 2017 23:14
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/4250328741e10319979a68594463b0cc to your computer and use it in GitHub Desktop.
Save jianminchen/4250328741e10319979a68594463b0cc to your computer and use it in GitHub Desktop.
Hackerrank - lucky 9 - code review - extract a function, public -> private, const int SIZE = 8, and add comment for the function
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
{
private static long Module = 1000000007;
static void Main(string[] args)
{
int n = Convert.ToInt32(Console.ReadLine());
String number = Console.ReadLine().ToString();
int[][] frequencyTable = new int[n][]; // subsequences
for (int i = 0; i < n; i++)
{
frequencyTable[i] = new int[8];
}
BuildFrequencyTableFromBottomUp(frequencyTable, number, n);
Console.WriteLine((frequencyTable[n - 1][0] - 1) % Module);
}
/*
* Build frequency table using bottom up method - dynamic programming
* Design of the algorithm:
* At any position of the sequence, you need to consider two cases:
Concatenate the digit at the position with your current subsequence and move to next position.
Leave the digit and move to next position.
The idea can be coded with states: Current position and Remainder of the subsequence modulo 8.
*
*/
public static void BuildFrequencyTableFromBottomUp(int[][] frequencyTable, string number, int n)
{
const int SIZE = 8;
frequencyTable[0][0] = 1; // ask why here? count 0 as the first digit
frequencyTable[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++)
{
frequencyTable[i][remainder] = frequencyTable[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 = frequencyTable[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;
frequencyTable[i][nextRemainder] = (Int32)((frequencyTable[i][nextRemainder] + current) % Module);
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment