Ninja's Lootcase

Easy
0/40
Average time to solve is 15m
profile
Contributed by
0 upvote
Asked in companies
Expedia GroupUber

Problem statement

Ninja has accidentally discovered a suitcase while digging a well in his lawn. But the suitcase is locked and there is a paper along with that suitcase on which instructions for opening the suitcase are given.

So instructions are defined as follows. 
1. Select any element from the array and increase it by ‘1’.
2. Double all the value of all the elements in the array

So your task is to find the minimum number of steps of making the array element starting from ‘0’ you were be provided with the array ‘arr’ and if you double the all array element it would be counted as ‘1’ and for each element increment by ‘1’ considered as a separate count.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the ‘arr’ array.

The next line contains ‘N’ space-separated integers denoting the values of elements of the ‘arr’ array.
Output Format : 
For each test case, print a single line containing the minimum number of steps required to form the given array.

The output of each test case will be printed in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 5000
0 <= arr[i] < 10 ^ 6

Where ‘arr[i]’ represents the elements of the array.

Time Limit: 1 sec
Sample Input 1 :
2
3
2 4 8
3
6 3 7
Sample Output 1 :
6
9
Explanation For Sample Input 1 :
Test Case 1 :
For the first test case, the given array is { 2, 4, 8 } so we start from { 0, 0, 0 } and after the first ‘1’ operation i.e adding ‘1’ to ‘3rd’ index this will look like as { 0, 0, 1 } now in the 2nd operation we multiplied array ‘arr’  by ‘2’ and now it will look like { 0, 0, 2 } now we increase element at index ‘1’ by ‘1’  now it will look like as { 0, 1, 2 } now we multiply the whole array with ‘2’ and now it will look like as { 0, 2, 4 } now we increase the 0th index by ’1’ and now it will look like { 1, 2, 4 } now we multiply the array by ‘2’ and we got { 2, 4, 8 } so we return ‘6’ as the answer.

Test Case 2 :
For this test case, the given array is { 6, 3, 7 } so we start from { 0, 0, 0 } and after the first two operations this will look like as { 1, 0, 1 } now we multiplied it by ‘2’ and it will look like { 2, 0, 2 } now we increase the element all element by ‘1’ and now it will become { 3, 1, 3 } now we multiply it by ‘2’ making it as { 6, 3, 6 } now we increase the element at last index by ‘1’ and return ‘9’ as the final answer.
Sample Input 2 :
2
2
5 5
4
6 1 3 5
Sample Output 2 :
6
9
Hint

Can you think of a recursive approach for finding the count?

Approaches (2)
Recursive Approach

The idea here is that we can say that number of increment operations required are equal to the number of set bits present in the elements of a given array because in one operation you can double all elements of the array. To get an even number you need to get even / 2 i.e. half of the number. So we need Increment operations only when our current element is odd

 and in all other cases, we can divide the number by 2.

 

Algorithm

 

  • Firstly we declare a variable ‘ans’ to store our answer.
  • Now we define our two functions getIncrement which gives us operations used to increment the number and getMultiply which gives us operations used to double its value.
  • Now we start iterating the array and first, we call the getIncrement function which gives us count in a recursive way in every recursive call we check if the number is odd we increase the count by ‘1’ and again call recursively after dividing it by 2.
  • We recursively called this function until the element becomes ‘0’and when it becomes ‘0’ we return the count.
  • Now we call the function getMulitply we give us count in a recursive way we recursively called the function by dividing it by ‘2’ until it becomes less than equal to ‘1’
  • But as we know we can use multiply operations on all elements by using a single operation so after each getMultiply operation, we check the maximum count and store the maximum count in the ans.
  • After the whole traversal, we return the ‘ans’.

 

Description of ‘getIncrementOperations’ function

 

The function is created to count the number of minimum operations which can be performed of incrementation to make the desired array.

The function will take one parameter:

Int element for which we count the number of operations needed.

  • So we recursively call this function until our element becomes ‘0’.
  • In every step, we check if the number is odd we divide the element by ‘2’ and then recursively calls the function by increasing the count.

 

Description of ‘getMultiplyOperations’ function

 

The function is created to count the number of minimum operations which can be performed of double the elements to make the desired function.

The function will take one parameter:

Int element for which we count the number of operations required.

  • So we recursively call the function until our element is greater than or equal to ‘1’
  • In every step, we recursively call the function by the value element divided by ‘2’.
Time Complexity

O(N*log(MAX)), where ‘N’ represents the size of the given array and ‘MAX’ represents the maximum element present in the array.

 

As we are using a loop for iterating the array which takes O(N) time and in every iteration recursive function calls takes O(log(MAX) ) time as we are dividing the number by ‘2’ in every recursive call.

Space Complexity

O(N), Where n is the number of elements present in the array.

 

Recursive stack uses space of order of n.

Code Solution
(100% EXP penalty)
Ninja's Lootcase
Full screen
Console