Author: Ankit Rao
DIFFICULTY
Easy - Medium
PREREQUISITES
Bit Manipulation
PROBLEM
Given an array of n integers where each index i represents a value a_i - cost of buying 2^i items, and a value L representing the minimum threshold of items to buy.
Print the minimum cost for this.
###EXPLANATION
Here
Let m=1+max\begin{Bmatrix}
n+1 ,\left \lfloor 1+Log_2L \right \rfloor
\end{Bmatrix}
Here in the given problem, let’s say is cost_i represents the minimum cost to purchase 2^i items, then the following relation holds -
cost_i = \begin{Bmatrix} a_0 & if \,\, i=0 \\ min(2*cost_{i-1},a_i)& otherwise \end{Bmatrix}
prev = +INFINITY ;
for ( int i = 0 ; i < m ; i ++){
if ( i < n )
c o s t [ i ] = min ( prev , c o s t [ i ] ) ;
else
c o s t [ i ] = prev ;
prev = 2· c o s t [ i ] ;
}
Note that if 2 *a^i ≤ a^{i + 1}, then it doesn’t make sense to buy any it of type i + 1 — it won’t ever be worse to buy two items of type i instead.
Now for all i it’s true that 2 *a^i ≥ a^{i + 1}. Note that now it doesn’t make sense to buy more than one item of type i if i-1 \le n .
for ( int i = 0 ; i < m ; i ++){
if (L & ( 1LL << i ) )
answer += c o s t [ i ] ;
else
answer = min ( answer , c o s t [ i ] ) ;
}
If i^{th} bit is set in L, then no cost[j] or any form of their sum for 1 \le j \le i-1 can satisfy the requirement because 2^0 + 2^1 + ....... 2^{i-1} = 2^i - 1 .
But as you go further, if the cost[i] corresponding to higher bits is lower, it can certainly lead to minimum cost solution.
With this approach you may end up getting more than L items, but it will lead you to the minimum cost.
Also, in the given problem run the loop only till m instead of 64 as it can easily lead to overflow.