Java – how far can I count from 1, up to N times when I can use any number
My questions are as follows; For the number n, I need to find the maximum value I can calculate. Each number can be used n times
For example, if n = 5, the maximum value is 12 because the number 1 has been used five times
My initial approach was to simply traverse all numbers and record how many times each number has been used so far When n is large, it is obviously very inefficient, so I am looking for suggestions on smarter (and more effective) ways to achieve this goal
public class Counter {
private static Hashtable<Integer,Integer> numbers;
public static void main(String[] args){
Counter c = new Counter();
c.run(9);
}
public Counter() {
numbers = new Hashtable<Integer,Integer>();
numbers.put(0,0);
numbers.put(1,0);
numbers.put(2,0);
numbers.put(3,0);
numbers.put(4,0);
numbers.put(5,0);
numbers.put(6,0);
numbers.put(7,0);
numbers.put(8,0);
numbers.put(9,0);
}
public static void run(int maxRepeat) {
int keeper = 0;
for(int maxFound = 0; maxFound <= maxRepeat; maxFound++) {
keeper++;
for (int i = 0; i < Integer.toString(keeper).length(); i++) {
int a = Integer.toString(keeper).charAt(i);
//here update the tally for appropriate digit and check if max repeats is reached
}
}
System.out.println(keeper);
}
}
Solution
For beginners, instead of using hashtable to support your counter, use int [] Arrays are perfect when you know exactly how many elements a map must have, especially when the key is a number
Having said that, I think the most effective acceleration may come from better mathematics, not better algorithms Through some experiments (or perhaps obviously), you will notice that 1 is always the first number to use a given number of times So given n, if you can find the first number to use the number 1 N 1 times, you know your answer is the previous number This allows you to solve problems without having to calculate them so high
Now let's see how many 1s are used to calculate various numbers In this article, I will use n to specify a number. When we try to calculate how many 1s are used to calculate a number, the capital letter N indicates how many 1s are used to calculate a number
One digit
Start with one digit:
1: 1 2: 1 ... 9: 1
Obviously, the number of 1s required to calculate one digit is... 1 Well, actually we forgot one:
0: 0
This will be very important in the future So we should say this: the number of 1 required to count to a single digit x is x > 1 0 1：0. Let's define a mathematical function f (n), which represents "the number of 1 required to count to n" then
f(X) = X > 0 ? 1 : 0
Two digits
For two digits, there are two types For numbers in the form of 1X,
10: 2 11: 4 12: 5 ... 19: 12
You can think of it this way: counting up to 1x requires a 1 equal to 1
>F (9) (counting from most to 9) plus > 1 (from 10) plus > x (from the first few digits of 11-1x, if x > 0) plus > however, many 1s are required to calculate X
Or mathematically,
f(1X) = f(9) + 1 + X + f(X)
Then there are two digits higher than 19:
21: 13 31: 14 ... 91: 20
Count the number of 1s required for two digit YX, where y > 1 is
>F (19) (from number to 19) plus > F (9) * (Y – 2) (included in 1 from number 20 to (Y-1) 9 – if y = 5, I mean 1 in 20-49, from 21,31,41) plus > however, a lot of 1 is required to calculate X
Or mathematically, for Y > 1,
f(YX) = f(19) + f(9) * (Y - 2) + f(X)
= f(9) + 1 + 9 + f(9) + f(9) * (Y - 2) + f(X)
= 10 + f(9) * Y + f(X)
Three digit number
Once you get a three digit number, you can extend the pattern For any three digit number in 1yx form (y can now be anything), the total number from counting to that number is 1
>F (99) (from the highest count to 99) plus > 1 (from 100) plus > 10 * y x (starting from the first number of 101-1yx) plus > however, multiple 1s are required to calculate the two digit YX
therefore
f(1YX) = f(99) + 1 + YX + f(YX)
Note that it is parallel to f (1x) Continue the logic to more numbers. For numbers starting with 1, the mode is
f(1[m-digits]) = f(10^m - 1) + 1 + [m-digits] + f([m-digits])
[m-digits] represents a sequence of numbers with length M
Now, for a three digit number ZYX that does not start with 1, that is, z > 1 1. The number of 1 required to calculate them is
>F (199) (counting to 199) plus > F (99) * (Z – 2) (starting from 1 in 200 - (Z-1) 99) plus > however, a lot of 1 is required to calculate YX
therefore
f(ZYX) = f(199) + f(99) * (Z - 2) + f(YX)
= f(99) + 1 + 99 + f(99) + f(99) * (Z - 2) + f(YX)
= 100 + f(99) * Z + f(YX)
Now, the number pattern starting with 1 seems clear:
f(Z[m-digits]) = 10^m + f(10^m - 1) * Z + f([m-digits])
General situation
We can combine the final result with the formula of numbers starting with 1 You should be able to verify that the following formula is equivalent to the appropriate case of all the numbers Z 1-9 given above, and that it does the right thing when z = = 0:
f(Z[m-digits]) = f(10^m - 1) * Z + f([m-digits])
+ (Z > 1) ? 10^m : Z * ([m-digits] + 1)
For numbers in the form of 10 ^ m – 1, such as 99999, you can directly evaluate the function:
f(10^m - 1) = m * 10^(m-1)
Because the number 1 will be used 10 ^ (m-1) times in each m numbers – for example, when counting to 999, 100 1 will be used in hundreds of places, 100 1 will be used here, dozens of places, and 100 1 'will be used in those places So that's it
f(Z[m-digits]) = Z * m * 10^(m-1) + f([m-digits])
+ (Z > 1) ? 10^m : Z * ([m-digits] + 1)
For this particular method, you can modify the exact expression, but I think it's very close to it You have a recursive relationship here that allows you to evaluate f (n) by removing a leading number at each step, that is, the number of 1s required to count to n Its time complexity is logarithmic in n
perform
In view of the last formula above, it is easy to realize this function Technically, you can use a basic case in recursion: an empty string, which defines f ("") as 0 But it will save you some calls to deal with individual numbers and table numbers 10 ^ m – 1 This is how I do it, omitting some parameter validation:
private static Pattern nines = Pattern.compile("9+");
/** Return 10^m for m=0,1,...,18 */
private long pow10(int m) {
// implement with either pow(10,m) or a switch statement
}
public long f(String n) {
int Z = Integer.parseInt(n.substring(0,1));
int nlen = n.length();
if (nlen == 1) {
return Z > 0 ? 1 : 0;
}
if (nines.matcher(n).matches()) {
return nlen * pow10(nlen - 1);
}
String m_digits = n.substring(1);
int m = nlen - 1;
return Z * m * pow10(m - 1) + f_impl(m_digits)
+ (Z > 1 ? pow10(m) : Z * (Long.parseLong(m_digits) + 1));
}
Reversed phase
This algorithm solves the inversion of your question: that is, it calculates the number of times a number is used to count N, and you want to know which n (i.e. 1 ') you can reach with a given number n So, as I mentioned at the beginning, you are looking for the first N. N
The easiest way is to count from n = 0 to see when you exceed n
public long howHigh(long N) {
long n = 0;
while (f(n+1) <= N) { n++; }
return n;
}
But of course, this is not better (and may actually be worse) than accumulating counts in an array The whole point of F is that you don't have to test every number; You can skip a long interval until you find an n so that f (n 1) > N, and then use jump to narrow the search scope A fairly simple method I recommend is exponential search, which places the results at the upper limit, and then performs a binary search to narrow the scope:
public long howHigh(long N) {
long upper = 1;
while (f(upper + 1) <= N) {
upper *= 2;
}
long lower = upper / 2,mid = -1;
while (lower < upper) {
mid = (lower + upper) / 2;
if (f(mid + 1) > N) {
upper = mid;
}
else {
lower = mid + 1;
}
}
return lower;
}
Since the implementation of F above is O (log (n)) and the exponential binary search is also o (log (n)), the final algorithm should be o (log ^ 2 (n)). I think the relationship between N and N is linear enough. You can also regard it as O (log ^ 2 (n)) If you search in the log space and cache the calculated value of the function wisely, you may reduce it to approximately o (log (n)) Variants that may provide significant acceleration persist in the round of interpolation search after determining the upper limit, but coding correctly is tricky Nevertheless, fully optimized search algorithms may be another problem