Editorialist:Swetanjal Dutta
PREREQUISITES:
- Basic Arithmetic
PROBLEM LINK:
PROBLEM IN SHORT:
Each digit(0-9) has a cost.
What is the maximum number you can write such that the total cost incurred is less than equal to B?
The cost for each digit will be given to you.
EXPLANATION:
Observation #1:
While writing the largest number, the first thing we have to keep in mind is to maximize the number of digits(no matter what the digits are!)
3 digit number 100 is obviously greater than 2 digit number 99.
The above observation seems trivial but we will build our solution on this crucial observation only.
Incorporating Observation #1 in our problem to get the maximum number of digits we can write incurring cost no more than B
What is the maximum number of digits I can write incurring cost no more than B?
We said that we don’t bother what the digits are. So it makes sense to use the digit which has the least cost.
Let’s take the example of Case (b):
| Digit | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Cost | 9 | 12 | 8 | 9 | 10 | 13 | 17 | 23 | 80 | 75 |
Given B=62, what is the maximum number of digits we can write?
The maximum number of digits we can write = [62/Least Cost of a digit]
= [62/8]
= [7.75]
= 7
**[x] represents the box function, also known as the Greatest Integer Function. It is equivalent to floor(x).
In other words, it returns the greatest integer less than equal to x.
When we get the final answer we will see that it will have 7 digits.
So for any value X, the maximum number of digits we can write incurring a cost no more than X
= [X/Least Cost of a digit]
Observation #2:
Now that we know the number of digits our answer will have, let us turn our attention to the digits that we will place, to maximize our answer.
89 and 98 will incur the same cost. But 98 is greater than 89. Similarly, 898 and 988 will require the same cost but 988 is the greater number.
So, whenever we place a digit we will try to put the largest digit possible.
Another example to convince us is:
Say 88 and 90 both are numbers that we can write by incurring a cost no more than B. Which do we prefer?
At the first place we could put 8 or 9. But we chose the largest digit possible i.e 9 and it turned out that it gave us the correct answer.
How do we know which is the largest digit “possible” to put at any instant?
Let us work out the Case (b) to understand all this.
Combining Observation #1 and #2 to get the final solution:
Here is the table once more for ease of seeing data while solving:
| Digit | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Cost | 9 | 12 | 8 | 9 | 10 | 13 | 17 | 23 | 80 | 75 |
Given B=62.
Observation #1 gave us the first and the most important part of the solution i.e our answer will have 7 digits.
Keeping this in mind let’s incorporate Observation #2.
Observation #2 told us that whenever we are placing a digit we should place the largest digit possible.
Deciding the first digit of our answer:
What is the maximum digit possible to be placed?
9? 8? May be 7 or 6?
Or is it 2 because that has the smallest cost?
Why not put and check?
Let’s put 9 first in the first place:
9 __ __ __ __ __ __
Now how do we know whether it is indeed valid to put 9 here?
Putting 9 would incur a cost of 75.
See, we have already incurred a cost greater than B(=62) by placing 9.
So, 9 is definitely not the largest digit that can be placed at the first place. 
Let us move to 8.
Try putting 8 in the first place:
It turns out that again we will incur a cost greater than B by placing 8.
So, 8 is not the largest digit that can be placed at the first place.
Let’s try something smaller.
Try putting 7 in the first place:
7 __ __ __ __ __ __
Putting a 7 will incur a cost of 23.
That is definitely not greater than B.
So, is 7 the largest number that can be placed?
Yes? No?
How do we know?
Hint: We told in the beginning that our answer must have 7 digits.
What will be the remaining cost after placing 7?
62-23 = 39
Can we place the remaining 6 digits by incurring a cost no more than 39?
The maximum number of digits we can place by incurring a cost no more than 39 is
= [39/Least cost of a digit]
= [39/8] = [4.875] = 4 ……………………[Refer Observation #1 in case you are not convinced]
Therefore, we can see that it is indeed not possible to place remaining 6 digits by incurring a cost no more than 39.
So, 7 is not a good choice. [Had we put 7 our answer would have 5 digits in total.]
Let’s try 6.
6 _ _ _ _ _ _
Putting a 6 would incur a cost of 17. Remaining cost = 62-17 = 45.
We can place at most [45/8] = [5.625] = 5 digits after 6 and our answer will have 6 digits.
Still not good enough!
Try 5
5 __ __ __ __ __ __
Putting a 5 would incur a cost of 13.
Remaining cost = 62-13 = 49.
Can we place remaining 6 digits by incurring a cost no more than 49?
Maximum number of digits that can be placed by incurring a cost no more than 49
= [49/8]
= [6.125]
= 6
Yes! We can place a 5 at the first place and after that we can put 6 digits so that our answer will have 7 digits.
Great!
We have fixed our first digit of our answer.
Deciding the second digit of our answer:
What is the remaining cost B, now?
We have already put the first digit 5, incurring a cost of 13, so:
B = 62-13 = 49
Again what is the maximum digit possible to be placed at the second position?
Let us again try putting 9,8,…, until we get our valid digit.
But, wait!
What did we say in Observation #2?
Which was better 89 or 98?
So, does it make sense to try and put digits greater than the first digit at the second place?
Obviously, not!
[If you are not convinced read Observation #2 once again]
It is sufficient to check from 5 onwards.
Again let’s run through the process of trial and error.
5 5 __ __ __ __ __
Remaining cost = 49-13 = 36
Can we place the remaining 5 digits by incurring a cost no more than 36?
No, we can place at most 4 remaining digits.
5 4 __ __ __ __ __
Remaining cost = 49-10=39
Can we place the remaining 5 digits by incurring a cost no more than 39?
No, we can place at most 4 remaining digits.
5 3 __ __ __ __ __
Remaining cost = 49-9=40
Can we place the remaining 5 digits by incurring a cost no more than 40?
Yes, we can place at most 5 remaining digits.
So our second digit is fixed. 
Deciding the third digit of our answer:
What is the remaining cost?
We have placed the first two digits already.
B = 62-13-9 = 40
Now from which digit onwards do we try to get our maximum possible digit?
3 onwards.
5 3 3 __ __ __ __
Remaining cost = 40-9 = 31
Can we place the remaining 4 digits by incurring a cost no more than 31?
No, we can place at most 3 remaining digits.
5 3 2 __ __ __ __
Remaining cost = 40-8 = 32
Can we place the remaining 4 digits by incurring a cost no more than 32?
Yes, we can.
Now our third digit is decided.
Deciding the fourth digit of our answer:
Now that we placed our first, second and third digits of our answer, what is the remaining cost?
B = 62-13-9-8=32
Now from which digit onwards do we try to get our maximum possible digit.
2 onwards.
5 3 2 2 __ __ __
Remaining cost = 32-8 = 24
Can we place remaining 3 digits by incurring a cost no more than 24?
Yes, we can.
Deciding the fifth digit of our answer:
Now that we placed our first, second, third and fourth digits of our answer, what is the remaining cost?
B = 62-13-9-8-8=24
Now from which digit onwards do we try to get our maximum possible digit.
2 onwards.
5 3 2 2 2 __ __
Remaining cost = 24-8 = 16
Can we place remaining 2 digits by incurring a cost no more than 16?
Yes, we can.
Deciding the sixth digit of our answer:
Now that we placed our first, second,third, fourth and fifth digits of our answer, what is the remaining cost?
B = 62-13-9-8-8-8=16
Now from which digit onwards do we try to get our maximum possible digit.
2 onwards.
5 3 2 2 2 2 __
Remaining cost = 16-8 = 8
Can we place remaining 1 digit by incurring a cost no more than 8?
Yes, we can.
Deciding the seventh digit of our answer:
Now that we placed our first, second,third, fourth, fifth and sixth digits of our answer, what is the remaining cost?
B = 62-13-9-8-8-8-8=8
Now from which digit onwards do we try to get our maximum possible digit.
2 onwards.
5 3 2 2 2 2 2
Remaining cost = 8-8 = 0
Can we place remaining 0 digits by incurring a cost no more than 0?
Yes, we can always place 0 digits!
So, we have our correct solution: 5 3 2 2 2 2 2
Exercise:
You should try out Case [c] using the above strategy:
Edge Case:
Let us take the example of case (a):
| Digit | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Cost | 3 | 10 | 12 | 4 | 9 | 9 | 13 | 5 | 15 | 8 |
What is the maximum number of digits that can be placed by incurring a cost no more than B=33?
According to our Observation #1, this would be equal to
= [B/Least cost of a digit]
= [33/3]
= [11] =11
But notice that the digit with the least cost is 0. Can we place a 0 in the first place?
No.
So, we take the digit which has the second least cost. Place it in the first place.
After this whatever cost we have remaining, we can place the 0s and check what is the number of digits our answer must have.
So the maximum number of digits our answer will have
= 1+ [(B-Second Least cost of a digit)/Least cost of a digit]
= 1+ [(33-4)/3]
= 1+ [29/3]
= 1+ [9.667]
= 1+ 9 = 10.
Now while placing the digits we use the above described strategy.
Important Note:
In case the digit 0 has the least cost, then:
The maximum number of digits that can be placed such that we incur a cost no more than X, given that no digit is placed = 1+ [(X-Second Least cost of a digit)/Least cost of a digit]
The maximum number of digits that can be placed such that we incur a cost no more than X, given that a non zero digit is already placed = [X/Least cost of a digit]
This is based on the fact that at the first position we cannot place a 0 but in the other positions we can place 0s.
Deciding the first digit:
9 __ __ __ __ __ __ __ __ __ __
Remaining cost = 33-8 = 25
Can we place remaining 9 digits by not incurring a cost more than 25?
Maximum number of digits that can be placed after 9 by incurring a cost no more than 25
= [25/Least cost of a digit(=3)]
= [8.3333]
= 8
[We can consider the digit 0 here because we have already placed a non 0 digit in the first place]
Try 8.
It is obvious 8 won’t work because the remaining cost would be = 33 - 15 = 18
We could not place 9 digits with cost 25, forget about 18?
Try 7:
7 __ __ __ __ __ __ __ __ __ __
Remaining cost = 33-5 = 28
Can we place remaining 9 digits by not incurring a cost more than 28?
Maximum number of digits that can be placed after 9 by incurring a cost no more than 28
= [28/Least cost of a digit(=3)]
= [9.3333]
= 9
Yes, we can place the remaining 9 digits.
Can you fix the other digits exactly the way we did for the previous cases to get the answer?
You can see clearly that when the 0 has the least cost among all the digits, it is only the time when we decide the number of digits in our solution, our formula is different.
Rest everything remains the same.