Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created September 7, 2018 06:35
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/175e5173ea0c0336872beb5abf6d3d99 to your computer and use it in GitHub Desktop.
Save jianminchen/175e5173ea0c0336872beb5abf6d3d99 to your computer and use it in GitHub Desktop.
Leetcode 400 Nth Digit - FirstSubmission - a few issues - failed test case: input: 10, output: 0, expected: 1
public class Solution {
public int FindNthDigit(int n) // 8, return 8
{
var preprocessed = getPreprocessNumbers();
var length = preprocessed.Count;
/// there are 28 entries in the list
for (int i = 0; i < length; i++ )
{
var current = preprocessed[i];
if (n <= current[3]) // 8 < 9
{
var start = i == 0 ? 1 : getStartByDigits(current[0]); // 0
var digits = current[0]; // 1
var sequence = (n - start) / digits; // 8
var nth = (n - start) % digits; // 0
return getDigitInInteger(sequence, nth, digits);
}
}
return 0;
}
// 8 - start 1 sequence 7, nth 0, digits 1
// 12 - start 10 sequence 1, nth 0, digits 2
// 13 - start 10 sequence 1, nth 1, digits 2
private static int getDigitInInteger(int sequence, int nth, int digits)
{
int start = getStartByDigits(digits);
start += sequence;
int index = 0;
int nthValue = 1;
int current = start;
int loops = digits - nthValue;
int lastDigit = current % 10;
while (index < loops)
{
lastDigit = current % 10;
current = current / 10;
index++;
}
return lastDigit;
}
private static int getStartByDigits(int digits)
{
return digits == 1 ? 1 : (int)Math.Pow(10, digits - 1);
}
/// <summary>
/// 1 - 9, 1 digit number, 9 numbers, 9 * 1 digits in total
/// 10 - 99, 2 digit numbers, 90 numbers, 90 * 2 digits in total
/// 100 - 999, 3 digit numbers, 900 numbers, 900 * 3 digits in total
/// 1000 - 9999, ...
/// int 2^31
/// </summary>
/// <returns></returns>
private static IList<int[]> getPreprocessNumbers()
{
var numbers = new List<int[]>();
int start = 1;
int max = int.MaxValue;
int digits = 1;
int digitsUsed = 9;
int numberCounts = 9;
int totalDigitsUsed = 0;
while (start <= max && ((long)totalDigitsUsed + (long)digitsUsed) < max)
{
totalDigitsUsed += digitsUsed;
numbers.Add(new int[] { digits, numberCounts, digitsUsed, totalDigitsUsed });
// ....
start += numberCounts;
// increment the variables
digits++; // 1, 2, 3
numberCounts *= 10; // 9, 90, 900, ...
digitsUsed = numberCounts * digits; // 9, 90, 900, ...
}
return numbers;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment