Forgot Password ?
New password will be sent to following email id
Game of Powers of 2
Problem Code : POW2
2 2 2 0 3 1 0 2
Time Limit :
C , C++ , Java , Python 2
Login to submit your response.
<p>Chotu and Motu are playing a game related to <b>the power of 2s</b>. </p> <p> Interesting isn't it? </p> <p>So Chotu provides Motu with an array <b>Arr [ ] of size N</b> where each index <b>i</b> ( 0 <= i <= N - 1) represents a power of 2 i.e <b>index i corresponds to 2<sup>i</sup> </b></p>. <p> <b>Arr [ i ] </b>corresponds to the <b>frequency of 2<sup>i</sup>.</b> </p> . <p> For example, if we have array <b>Arr[ ]</b> as [ 1, 0, 2 ] , it means that the frequency of 2<sup>0</sup> is 1, of 2<sup>1</sup> is 0 and that of 2<sup>2</sup> is 2. </p> <p> Now, we can play the <b>conversion game</b> here, by carrying out conversion to higher powers from lower powers of 2 . </p> In other words, as 2<sup>2</sup> occurs twice, we can convert it into one occurrence of 2<sup>3</sup> because <b>(2)</b>*2<sup>2</sup> = <b>(1)</b>*2<sup>3</sup> </p> <p>The converted array Arr [ ] will be [ 1, 0, 0, 1 ]. </p> <p>Chotu challenges Motu to <b>minimise the sum of the array elements</b>. In the example array, earlier it was <b>1+0+2 = 3, and now it will be 1+0+0+1 = 2.</b> </p> <p><b>If it is required to increase the array size (make indices > (N - 1) ) to minimise the sum</b>, Motu can do that as well, just like in the above example.</p> <p><b>Source: Hike </b></p>
<p>First line comprises <b>T</b> - the number of test cases.</p> <p>For each test case, first line comprises <b>N</b> - the number of elements in the array. </p> <p>Second line of each test case comprises N space separated integers denoting Arr [ i ] </p>.
<p>For each test case, print the minimum array sum possible in a separate line. </p>
<p><b>1 <= T <= 5</b></p> <p><b>1< = N < = 10<sup>5</sup></b></p> <p><b>1 <= Arr [ i ] <= 2*10<sup>9</sup> </b></p>
<p>In 1st case, we have frequency of 2<sup>0</sup> as 2, so we can convert it into 1 frequency of 2<sup>1</sup>, and the answer can't be reduced further. </p>.