Reduce Array

Easy

0/40

Contributed by

5 upvotes

Asked in company

Problem statement

You are given an array ‘Arr’ of ‘N’ integers. Your task is to reduce each of the elements to zero. You can perform the following two operations on the array. Select an index ‘i’. If ‘Arr[i]’ is odd then replace it with ‘(Arr[i]-1) / 2’ else replace it with ‘Arr[i] / 2’.

Return the total number of operations required to reduce each element of the array to zero.

Example:

‘N’=5, ‘Arr’ = [2 , 5 , 6 , 3 , 1].
2 -> 1 -> 0
5 -> 2 -> 1 -> 0
6 -> 3 -> 1 -> 0
3 -> 1 -> 0
1 -> 0

Hence total operations will be 11.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

First-line contains 'T', denoting the number of Test cases.
Each Test case contains 2 lines.
First-line contains an integer ‘N’.
Second-line contains ‘N’ integers, elements of ‘Arr’.

Output Format:-

Your task is to return the total number of operations required to reduce the array.

Note:-

You don’t need to print anything. Just implement the given function.

Constraints :

1<=‘T’<=10
1<=‘N’<=10^5
1<=‘Arr[i]’<=10^9

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

9
10

Explanation Of Sample Input 1 :

For testcase one:

‘N’=5, ‘Arr’ = [3 , 4 , 2 , 1 , 1].
3 -> 1 -> 0
4 -> 2 -> 1 -> 0
2 -> 1 -> 0
1 -> 0
1 -> 0

Hence total operations will be 9.
For test case two:

‘N’=3, ‘Arr’ = [6 , 8 , 4].
6 -> 3 -> 1 -> 0
8 -> 4 -> 2 -> 1 -> 0
4 -> 2 -> 1 -> 0

Hence total operations will be 10.

Sample Input 2 :

Sample Output 2 :

15
18

Approaches (1)

Approach 1

Greedy

Time Complexity

O( N * log(C)). Where ‘N’ is the length of the array and 'C' is the maximum element in the array.

Space Complexity

O(1).

We are using only variables. So, the Space Complexity is O(1).

(100% EXP penalty)

Reduce Array

Console