Last Updated: 13 Apr, 2021
Ninja's Lootcase
Easy
Asked in companies
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.
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
Approaches
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’.
The idea here is to traverse the array and try to make the elements of array ‘0’ so we can think of as we know there are 2 operations that are we can increase the elements by ‘1’ or we can double them so we can use this that if we see all the elements are presents are even we can divide the elements by ‘2’ and if any odd element is present we decrease it by ‘1’ to make an even number and then divide it and in every operation, we store the count so when all elements become ‘0’ it would be the minimum number of operations.
Algorithm
- First, we declare a variable ‘ans’ for storing the count of operations.
- Now we run a loop until all the elements of the array are ‘0’.
- Now in each iteration, we check if our elements are odd or not
- If we found any element as odd we decrease it by ‘1’ and increase the ans by ‘1’
- Else we count the number of elements that are even.
- Now we check if all the elements of the array are ‘0’ or not
- If all elements of the array become 0 we return ans.
- Else we remain in the loop.
- Now we check if all the elements are even or not if all are even we divide the elements by ‘2’ and increase it by ‘1’.