Problem : Given a number k, find a k-digit string where the product of its digits is greater than or equal to the sum of its digits. If there are multiple such strings, return the one with the minimum product. If there are still ties, return the lexicographically smallest string.
Testcases:
Input : 1 Output : 1
Input : 2 Output : 22
Input : 3 Output : 123
Input : 4 Output : 1124
Input : 5 Output : 11222
Input : 6 Output : 111126
Constraints:
1 <= K <= 100000
How to solve this? Please help!
I think that when you see a k, you can try to make all numbers with k digits and then calculate the product of each one and the sum of each one. If the product is greater than or equal to the sum, store it in a dictionary, where the dictionary key is the product and the dictionary value is the list of the numbers (maybe in string form to save some space). Then find the minimum key in the dictionary, sort that corresponding list, and return the first element in the list.
Edit: oh wait, the answer is just "0" * k
"You can try to make all numbers with k digits and then calculate the product of each one and the sum of each one". k can be 100000 , how can i create and check a number with such a large number of digits? I did not get that.
backtracking
EDIT: Sorry! I missed the first tie-breaker is to minimize the product. This solution is only correct for considering only the second tie-breaker. Counter example: take the case K=2^16-16, the suffix of the optimal answer is 16 2's, which cannot be constructed using the last 6 digits. __________________________________________________________________________________________ (Original comment) Notice that for large k, the answer will contain 1s for the first K-6 digits (at least) because 11111111111...999999 = 9^6>10^5. So we can just brute force over every suffix between 111111 and 9^6. The first one that yields a valid result is the answer. There exist better solutions but this will pass. __________________________________________________________________________________________
EDIT: Here is a correct solution, and one that does not use recursive backtracking.
To begin, we can use the same argument noting that the optimal solution will never have more than 16 2s (2^15*3>10^5). (1)
Instead, we can iterate from K...2*K and find the first number such that it is not divisible by any prime greater than 7. This can be found in O(K log K) time with a modified Sieve of Eratosthenes. (if the number is within 160 of K (a better bound probably exists), you need to check if it is valid first by factoring the number to see whether the minimal sum to construct the number is less than it. Notice that to minimize the sum it is always optimal to use prime numbers))
Proof of (1): Suppose we 17 digits, a better result always exists where we only use 16 as we replace one two with a three. The sum is the same, but the product is greater than the maximum possible value 3*2^15> 10^5+31
Proof that we only need to check between K and 2*K: You can always construct a product at most 2*K by constructing a number with only 2's. Keep adding 2's until the product is greater than K+ number of 2's added. Hence our upper-bound is good.
How can we assure that the first valid result is indeed the minimum product and lexicographically smallest?
For k > 6 , we have a fixed count of ones initially, so we just need to adjust the last six digits using brute force and backtracking.
For k = 10 :
1111 _ _ _ _ _ _
We have a sum of 4 and a product of 1 initially. Adjust the last six digits by creating all possible numbers using backtracking, and you will get the least product with the least value easily.
Thanks to both of you 123gjweq2 , nathanballman.
Got it, you start from the minimum possible values so that the first result is the miminum product and sum
Edit: What is the criteria for the backtracking? How do we build it? I dont mean how to code it but how the pattern should look like
a simple backtracking for input 6 for a valid answer would look like (111229 if you start from big to small) or (111922 if you start from small to big) at some point you get those 2 valid answer before the real one which is (111223)
Yeah this one should work .
Why the answer can't have more than 6 digits greater than 1? For example, assume that the product of digits in the answer is 5^7, which can be achieved only with 7 digits being equal to 5. Are there any proofs that the product of digits in the answer can always be represented as a product of 6 digits?
For the largest k=10000:
If we place 1 in all the digits except for the last 6 digits, which can be filled with 9, the sum is calculated as follows:
Sum=6×9+(100000−6)×1=100048 The product of the digits ( 9^6 ) is greater than 500000. Since we need at most 6 digits to be checked to ensure the product is greater than or equal to the sum for the largest k, this indicates that it will be true for lower values of k as well. Thus, we can conclude that for all 1≤k≤10000, it is always possible to obtain a number whose product of digits is greater than or equal to the sum of its digits.
To ensure we can get the minimized product within six digits: For any k in the range [1,10000], we can use up to 18 digits of 2 (since 2 ^ 18 ≥ 200000 ) . Grouping 18 digits of 2 into six digits, we can use six digits of 8 instead (since 2 ^18 = (2 ^ 3 ) ^ 6 = 8 ^ 6). This approach ensures that we can effectively group the largest count of 18 digits into six digits, ensuring that a number of length [1,10000] can always achieve a similar product using six digits or fewer.
Edit:I am also unable to provide a rigorous proof, but from observation, it appears that all numbers can be reduced to a product of six digits that satisfies the condition. I believe this problem might require a proof by contradiction. If anyone has suggestions on how to approach or prove this, please share .
Sorry about that, I didn't read the original problem carefully enough. I edited my original post with a counter-example.
I gave 2^16-16 there, but 2^7-7 also works as a counter example and I'll explain why my algorithm fails here.
The correct solution for 2^7-7 is 111111...2222222.(2^7-14 1's and 7 2's) The product of this number is 2^7 and the sum is also 2^7. We know my original algorithm will fail because a list of only 1's and 2's is the most efficient way to reach any product (in terms of the sum of the digits)
Proof: Here's a constructive argument. First create a string of length K filled will all ones. Its sum will be K.
Now let us observe what happens to the product when you change a 1 to a 2. The product doubles and the sum increases by one. Now let us observe what happens when we increment any other number. Going from 2 -> 3 multiplies the product by 1.5. In general going from N -> N+1 multiplies the product by (N+1)/N.
This shows diminishing returns and because every transition between a number x -> y can be represented as a sequence of increments, only incrementing 1->2 is the single most efficient way to make a product.
Naturally, it follows that using only 6 digits instead of 7 will force one to be at least 3 which is less efficient therefore the sum will be greater than 2^7 and thus the product must be as well.
Again, sorry for my mistake. I gave a non-backtracking solution in my edit to my original comment.
I'm sure a simple brute force will work.
First, it's clearly obvious that the digits are in ascending order from 1 to 9. So, we just have to think about how many times each digit appears in the string.
The maximum sum of the digits is bounded by $$$9K \leq 900000$$$. In particular, this implies that the number of digit 2 is bounded by $$$\lceil\log_2(9K)\rceil$$$ (since more number of digits would clearly make the product exceed the sum). Similarly, the number of digit 3 is bounded by $$$\lceil\log_3(9K)\rceil$$$, and in general, the number of digit $$$d$$$ is bounded by $$$\lceil\log_d(9K)\rceil$$$.
So, the total number of ways of choosing the digits from 2 to 9 is bounded by $$$\prod_{d = 2}^{9} (\lceil \log_d(9K) \rceil + 1)$$$. If you actually compute this quantity with $$$K = 100000$$$, you'll find out that this is less than $$$2 * 10^8$$$. Of course, this is actually a pretty loose upper bound, and you can likely prune away many, since many of the products would far exceed the sum upper bound $$$9K$$$.
So basically, for all digits from 1 to 9, we can store/calculate the maximum count we can take for each digit and then brute force through it using backtracking. Thanks for the help.
The sum of digits is bounded by 9*k. To make product of digits at least 9*k we need at most ceil(log2(9*k)) digits greater than 1. If we had more than ceil(log2(9*k)) digits greater than 1, then we could turn the least digit greater than 1 into 1, reducing product of digits and making string lexicographically smaller. Therefore having at most ceil(log2(9*k)) digits greater than 1 is optimal. Let's denote ceil(log2(9*k)) as l. Sum of last l digits is bounded by 9*l. Let's maintain dp[i][j], sum of last l digits is i, product of them is at least j, dp[i][j] gives information about whether this state can be achieved and if so, which digit was the last used one. Dimension of dp will be [l*9][k+l*8]. Time complexity is O(klog^2(k)), space complexity is O(klog(k)) .
First, answer for N=6 is 111126
You can't assume 6 non-one digits. For example 8179, lowest product is 8192=2^13, and "1" * 8166 + "2" * 13 has sum 8192, so its tight.
I think easiest way to proceed is for each product P = K, K+1, ... check if its achievable. Brute force is enough, we should expect to hit an answer fairly fast, you can code this then check it finds an answer for every K.
Auto comment: topic has been updated by Summer_Wind (previous revision, new revision, compare).