Is there a universal formula for how you could work this out?
This is a part of a coding problem I'm attempting to solve and simple solutions like going through each integer and checking if it contains the number 9 is way too slow.
closest I've got so far (working in c#) is this:
using System;
using System.Numerics;
public static class Kata {
public static BigInteger Nines(BigInteger n)
{
BigInteger a = 0;
for (BigInteger i = 0; i < BigInteger.Parse((Math.Floor(Math.Log10((double)n))+1).ToString()); i++)
{
long c = (long)((Math.Floor((double)n /Math.Pow(10,(double)i)) % 10));
a = c < 9 ? (long)(((double)c*(Math.Pow(9,(double)i))) + (double)a) : (long)(c*(Math.Pow(9,(double)i)));
}
return n-a;
}
}
however I noticed that when n=3950 for example, I begin getting incorrect values (for this specific case the function returns 1034 instead of 1035 and I'm not sure where I've gone wrong. The error gets even bigger for larger values of n)
Let's say that your input, n, has k digits, and that the leading digit is d.
Then, we're considering all numbers with up to k-1 digits and some (possibly all) with exactly k.
For the numbers with up to k-1 digits, we can allow leading zeros and then think of numbers as having exactly k digits, some with leading zeros. Since there are 10 digits there are 10^(k-1) of these, and since there are 9 digits other than '9', there are 9^(k-1) of these which don't have a 9, therefore there are 10^(k-1) - 9^(k-1) which do have a 9.
Now we need to consider numbers with exactly k digits. Say the leading digit is d. Then the set of all k-digit numbers with a leading digit between 1 & d-1 also has 10^(k-1) - 9^(k-1) members with at least one 9.
If d is a 9 then the rest is easy, just count all k-digit numbers with a leading 9 that are at most n.
If d is smaller than 9 then recurse on n with the leading digit removed.
E.g. n = 234, so d = 2, k = 3
2-digit numbers: 10^2 - 9^2 = 100 - 81 = 19. These are: 9, 19, 29, 39, 49, 59, 69, 79, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99.
3-digit numbers with a leading digit between 1 & 1: There are 1 of these, which gets us another 19 (each elt of the above list, plus 100).
Recursion: repeat the above for n = 34 (we have removed the leading 2).
I don't know c#, so here's Ruby code, which you can read as pseudocode.
def f(n)
# n = input
# k = num digits
# d = leading digit
# confirm input >= 0 & answer basic 1-digit questions directly
return -1 if n < 0 # invalid input
return 0 if n < 9
return 1 if n == 9
# calculate k (num digits) and d (leading digit)
k = Math.log10(n).to_i + 1
d = n / 10 ** (k-1)
# Start with all k-1-digit numbers
ans = 10 ** (k-1) - 9 ** (k-1)
# Next, multiply this by d to account for leading digits 0 through d-1
ans *= d
# Next, handle the leading digit differently depending on whether or not it's a 9.
if d == 9
ans += n - (9 * 10 ** (k-1) - 1)
else
ans += f(n - d * (10 ** (k-1)))
end
return ans
end
...and here's output for n up to 100.
1.upto(99) do |n|
puts "#{n}, #{f(n)}"
end
1, 0
2, 0
3, 0
4, 0
5, 0
6, 0
7, 0
8, 0
9, 1
10, 1
11, 1
12, 1
13, 1
14, 1
15, 1
16, 1
17, 1
18, 1
19, 2
20, 2
21, 2
22, 2
23, 2
24, 2
25, 2
26, 2
27, 2
28, 2
29, 3
30, 3
31, 3
32, 3
33, 3
34, 3
35, 3
36, 3
37, 3
38, 3
39, 4
40, 4
41, 4
42, 4
43, 4
44, 4
45, 4
46, 4
47, 4
48, 4
49, 5
50, 5
51, 5
52, 5
53, 5
54, 5
55, 5
56, 5
57, 5
58, 5
59, 6
60, 6
61, 6
62, 6
63, 6
64, 6
65, 6
66, 6
67, 6
68, 6
69, 7
70, 7
71, 7
72, 7
73, 7
74, 7
75, 7
76, 7
77, 7
78, 7
79, 8
80, 8
81, 8
82, 8
83, 8
84, 8
85, 8
86, 8
87, 8
88, 8
89, 9
90, 10
91, 11
92, 12
93, 13
94, 14
95, 15
96, 16
97, 17
98, 18
99, 19
.. and finally, the OP's example:
> f(3950)
=> 1035