So a coworker posed a problem to me yesterday that intrigued me. He claimed he heard it as an interview question at Google.
There exists a series such that f(n) = n. f(n) is the sum total of all occurrences of the digit 1 within all numbers in the range 0 to n.
The problem then goes on to list several elements in the sequence and your job was to find the next element in the sequence. I was unconcerned with the answer. I was much more interested in the function f(n), and how it could be approached mathematically instead of as a brute force search. A couple of the guys who had been working on the problem throughout the day showed me their work, and they all had some variation of the brute force algorithm. Mine was the following:
static void Main(string[] args)
{
int total = 0;
int test = 10000000;
foreach (var num in Enumerable.Range(0, test + 1))
{
total += num.ToString().ToCharArray().Count(x => x == '1');
}
Console.WriteLine("Answer = " + total);
Console.ReadKey();
}
With a slight modification, it could answer the question without breaking a sweat. If I wanted to wait all day.
So I decided to approach the problem from several angles. I tried a recursive algorithm that broke the number into chunks. I tried searching my brain for applicable probability or statistical formulas. Well, to tell the truth, because my day to day work centers on trying to keep management from shooting themselves in the foot rather than solving complex problems (*sigh*), my math is becoming a bit rusty. Instead, I approached the problem as a "visual" mathematical problem, and attacked it one digit at a time.
The results are as follows:
static int calcResult(int n)
{
int answer = 0;
// Iterate over each position in the number
for (int i = 0; i < (int)Math.Log10(n) + 1; i++)
{
answer += calcPosition(n, i);
}
return answer;
}
/// <summary>
/// Calculates the number of times a position within a number n has contained
/// the value '1' in the range of numbers from 0 to n.
/// </summary>
/// <param name="n">Number</param>
/// <param name="pivotOffset">Digit offset from beginning of number</param>
/// <returns>The total times the position equals 1 in the range from 0 to n</returns>
static int calcPosition(int n, int pivotOffset)
{
// The algorithm works by breaking the number into 3 components:
// 1) The integer value of the position under consideration (the pivot)
// 2) The integer value of the digits preceding the pivot
// 3) The integer value of the digits remaining beyond the pivot
int guess = 0;
// Helpers
int maxExponent = (int)Math.Log10(n);
int pivotPosition = maxExponent - pivotOffset;
int pivotExponentValue = (int)Math.Pow(10, pivotPosition);
int valueOfDigitsUpToPivot = n / pivotExponentValue;
// Calc #1
int valueOfPivot = valueOfDigitsUpToPivot % 10;
// Calc #2
int valueOfPreviousDigits = valueOfDigitsUpToPivot / 10;
// Calc #3
int valueOfRemainder = n - (valueOfDigitsUpToPivot * pivotExponentValue);
// The digits previous to the pivot tell us how many sets of numbers
// in which the pivot position has been equal to '1.' Each 'set' is equal
// to the base 10 exponent value of the position of the pivot.
guess += valueOfPreviousDigits * pivotExponentValue;
// If the pivot is greater than 1, an addition 'set' has elapsed.
if (valueOfPivot > 1)
guess += pivotExponentValue;
// If the pivot is '1,' it has not incremented through an entire 'set'
// so take the current tally of the times it has incremented from 0
// to the remainder.
if (valueOfPivot == 1)
guess += valueOfRemainder + 1;
return guess;
}
Yes, I know I could clean this up, cover the case of 0, and generalize it to any digit. Right now, it is the principle that matters.
Two things I like about this:
1) Complexity has been cut to Log10(n)
2) Each iteration is independent of the previous, so the iterations could be conducted in parallel instead, with a simple accumulation of the results.
Now, my challenge is this: I am sure that there is a better algorithm. I want to know what the best mathematical algorithm to solve this problem is. I would like opinions on my approach, and hopefully I will learn something.
