Amazon Interview Question

Round 1

Questions: Given an array of integers arr[] consisting of N integers, the task is to minimize the sum of the given array by performing at most K operations, where each operation involves reducing an array element arr[i] to floor(arr[i]/2).

• Constraints: k <= 1e9, n <= 1e5
• Time limit: 2 sec
• Can anyone think of an optimized approach better than mlogn? under 2 sec