PROBLEM STATEMENT
A new memory system is being tested by your company. The revolutionary
technology used allows 0's to be stored for no cost at all, but 1's still have
a cost. Unfortunately, the system places a maximum per-value-cost limit on
storing values. The cost of any single value is the total number of 1's in its
binary representation. For example,
79 (decimal) = 1001111 (binary) has 5 ones so its cost is 5.
63 (decimal) = 111111 (binary) has 6 ones so its cost is 6.
If a number costs more than the maximum per-value-cost limit it cannot be
stored. If the maximum per-value-cost limit was 5, a number such as 79 would
be allowed, but a number like 63 would not. You are going to test this memory
system with all values from 0 to some specified upper limit inclusive. Given
the inclusive upper limit, and the maximum per-value-cost, your method will
return the number of numbers that couldn't be successfully stored (they costed
too much).
Create a class CostlyOnes that contains the method howMany, which takes an int
upperLimit, an int maxPVCost, and returns an int representing the number of
numbers between 0 and upperLimit inclusive that could not be stored.
DEFINITION
Class: CostlyOnes
Method: howMany
Parameters: int, int
Returns: int
Method signature (be sure your method is public): int howMany(int upperLimit,
int maxPVCost);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- upperLimit is between 0 and 1000000000 (10^9) inclusive
- maxPVCost is between 0 and 30 inclusive
EXAMPLES
1) upperLimit = 15
maxPVCost = 2
The numbers in the range are (formatted as number:cost) :
0:0 1:1 10:1 11:2 100:1 101:2 110:2 111:3 1000:1
1001:2 1010:2 1011:3 1100:2 1101:3 1110:3 1111:4
As can be seen above there are four numbers with cost 3, and one number with
cost 4 that cannot be used.
Method returns 5.
2) upperLimit = 15
maxPVCost = 0
Only the number 0 can be stored since it is the only number of cost 0. This
means there are fifteen numbers that cannot be used.
Method returns 15.
3) upperLimit = 15
maxPVCost = 4
As seen in example 1, all of the numbers in the given range cost between 0 and
4 inclusive so all of the numbers can be used. This means there are zero
numbers that cannot be used.
Method returns 0.
4) upperLimit = 1000000000
maxPVCost = 15
Method returns 405307904.
5) upperLimit = 999988899
maxPVCost = 10
Method returns 947297086.
6) upperLimit = 0
maxPVCost = 0
Method returns 0.