Chef is multi-talented. He has developed a cure for corona virus called CO-VAC-19. Now that everyone in the world is infected, it is time to distribute it throughout the world efficiently to wipe out corona virus from the Earth. Chef just cooks the cure, you are his distribution manager.
In the world, there are N countries (numbered 1 through N) with populations a1,a2,…,aN. Each cure can be used to cure one infected person once. Due to lock down rules, you may only deliver cures to one country per day, but you may choose that country arbitrarily and independently on each day. Days are numbered by positive integers. On day 1, Chef has x cures ready. On each subsequent day, Chef can supply twice the number of cures that were delivered (i.e. people that were cured) on the previous day. Chef cannot supply leftovers from the previous or any earlier day, as the cures expire in a day. The number of cures delivered to some country on some day cannot
exceed the number of infected people it currently has, either.
However, corona virus is not giving up so easily. It can infect a cured person that comes in contact with an infected person again ― formally, it means that the number of infected people in a country doubles at the end of each day, i.e. after the cures for this day are used (obviously up to the population of that country).
Find the minimum number of days needed to make the world corona-free.
What I have tried:
We have been given with a sorted (in non-decreasing order) list of N positive integers (A1, A2 , ..... , An) and another positive integer X . We have to make all the list integers zero using the Integer X. But there are some conditions to do so:
Condition 1 : At one time we can only subtract X to one Integer in List (Ai).
Condition 2 : After Every Operation (of condition 1) All the Integers of list gets Doubled as well as X gets doubled.
Condition 3 : If X is larger than Ai then the Value of X changes to Ai and then Subtraction takes place.
What to find : We need to find the minimum operations to make all integers in list zero.
A sample to Understand Better :
List : 1 2 3 4 5
X : 4
Here to find most optimal solution we will first make 4 into zero using X.
Operation cost = 1
Now every integer will be doubled hence new list will be
2 4 6 0 10, X = 8
2 4 6 0 2, X = 8 (subtracting 10 - 8) Operation cost = 2
Again every thing gets doubled so new list is
4 8 12 0 4 , X = 16
4 8 0 0 4, X = 12` (as 12 < 16, X becomes 12) Operation cost = 3
Again every thing gets doubled so new list is
8 16 0 0 8, X = 24
8 0 0 0 8, X = 16 (as 16 < 24, X becomes 16) Operation cost = 4
Again every thing gets doubled so new list is
16 0 0 0 16, X = 32
16 0 0 0 0, X = 16 (as 16 < 32, X becomes 16) Operation cost = 5
Again every thing gets doubled so new list is
32 0 0 0 0, X = 32
0 0 0 0 0, X = 32 (as 32 <= 32, X becomes 32) Operation cost = 6
So, Finally in 6 operations we made the list zero.
Some More cases with Answers :
List : 10 20 30 40 50
X : 1
Answer : 9
List : 1 20 110
X : 10
Answer : 6
Constraints : (1 <= Ai<= 1000000000) , (1 <= X <= 1000000000)
My approach
- Let
a
be an integer in list and x is given to make `a` into zero.
- Now, there will a series formed after every operation as given below
(a-x) , (2(a-x) - 2x) , (2(2(a-x) - 2x) - 4x) , ..........
(a-x) , (2a - 4x) , (4a - 12x), (8a - 32x) , .....
(a-x) , 2(a-2x) , 4(a-3x) , 8(a-4x) , .......
an = (2^(n-1))(a-nx) | where an is nth term
So to make
An == 0 , A-nx = 0, A = n/x
I have figured out how to make any single integer zero with x but i cant figure out how to make the list zero with minimum operations, As I have to make a code for that also so what i need is a basic algorithm which can be used to solve this problem.
Can anyone help me with this ??
Submit an article or tip