Given an array arr[] of size N and an integer K, the task to find the maximum number of array elements that can be reduced to 1 by repeatedly dividing any element by 2 at most K times.
Note: For odd array elements, take its ceil value of division.
Examples:
Input: arr[] = {5, 8, 4, 7}, K = 5
Output: 2
Explanation:
5 needs 3 operations(5?3?2?1).
8 needs 3 operations(8?4?2?1).
4 needs 2 operations(4?2?1).
7 needs 3 operations(7?4?2?1)
Therefore, in 5 operations, the maximum number of array elements that can be reduced to 1 are 2, either (4, 5), (4, 8) or (4, 7).Input: arr[] = {5, 8, 5, 7}, K = 5
Output: 1
Approach: To maximize the number of elements, the idea is to sort the array in ascending order and start reducing the elements from the first index and decrement K by the number of operations required to reduce the ith element. Follow the steps below to solve the problem:
- Initialize a variable, say cnt, to store the required number of elements.
- Sort the array arr[] in increasing order.
- Traverse the array, arr[] using the variable i, and perform the following steps:
- Store the number of operations required to reduce arr[i] to 1 is opr = ceil(log2(arr[i])).
- Decrement K by opr.
- If the value of K becomes less than 0, break out of the loop. Otherwise, increment cnt by 1.
- After completing the above steps, print the value of cnt as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the maximum number of// array elements that can be reduced to 1// by repeatedly dividing array elements by 2void findMaxNumbers(int arr[], int n, int k){ // Sort the array in ascending order sort(arr, arr + n); // Store the count of array elements int cnt = 0; // Traverse the array for (int i = 0; i < n; i++) { // Store the number of operations // required to reduce arr[i] to 1 int opr = ceil(log2(arr[i])); // Decrement k by opr k -= opr; // If k becomes less than 0, // then break out of the loop if (k < 0) { break; } // Increment cnt by 1 cnt++; } // Print the answer cout << cnt;}// Driver Codeint main(){ int arr[] = { 5, 8, 4, 7 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 5; findMaxNumbers(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG {// Function to count the maximum number of// array elements that can be reduced to 1// by repeatedly dividing array elements by 2static void findMaxNumbers(int arr[], int n, int k){ // Sort the array in ascending order Arrays.sort(arr); // Store the count of array elements int cnt = 0; // Traverse the array for (int i = 0; i < n; i++) { // Store the number of operations // required to reduce arr[i] to 1 int opr = (int)Math.ceil((Math.log(arr[i]) / Math.log(2))); // Decrement k by opr k -= opr; // If k becomes less than 0, // then break out of the loop if (k < 0) { break; } // Increment cnt by 1 cnt++; } // Print the answer System.out.println(cnt);}// Driver Codepublic static void main(String args[]){ int arr[] = { 5, 8, 4, 7 }; int N = arr.length; int K = 5; findMaxNumbers(arr, N, K);}}// This code is contributed by jana_sayantan. |
Python3
# Python3 program to implement# the above approachimport math# Function to count the maximum number of# array elements that can be reduced to 1# by repeatedly dividing array elements by 2def findMaxNumbers(arr, n, k) : # Sort the array in ascending order arr.sort() # Store the count of array elements cnt = 0 # Traverse the array for i in range(n): # Store the number of operations # required to reduce arr[i] to 1 opr = math.ceil(math.log2(arr[i])) # Decrement k by opr k -= opr # If k becomes less than 0, # then break out of the loop if (k < 0) : break # Increment cnt by 1 cnt += 1 # Print the answer print(cnt)# Driver Codearr = [ 5, 8, 4, 7 ]N = len(arr)K = 5findMaxNumbers(arr, N, K)# This code is contributed by splevel62. |
C#
// C# program for the above approachusing System;public class GFG{ // Function to count the maximum number of// array elements that can be reduced to 1// by repeatedly dividing array elements by 2static void findMaxNumbers(int[] arr, int n, int k){ // Sort the array in ascending order Array.Sort(arr); // Store the count of array elements int cnt = 0; // Traverse the array for (int i = 0; i < n; i++) { // Store the number of operations // required to reduce arr[i] to 1 int opr = (int)Math.Ceiling((Math.Log(arr[i]) / Math.Log(2))); // Decrement k by opr k -= opr; // If k becomes less than 0, // then break out of the loop if (k < 0) { break; } // Increment cnt by 1 cnt++; } // Print the answer Console.Write(cnt);}// Driver Codepublic static void Main(String[] args){ int[] arr = { 5, 8, 4, 7 }; int N = arr.Length; int K = 5; findMaxNumbers(arr, N, K);}}// This code is contributed by susmitakundugoaldanga. |
Javascript
<script>// Javascript program for the above approach// Function to count the maximum number of// array elements that can be reduced to 1// by repeatedly dividing array elements by 2function findMaxNumbers( arr, n, k){ // Sort the array in ascending order arr.sort(); // Store the count of array elements let cnt = 0; // Traverse the array for (let i = 0; i < n; i++) { // Store the number of operations // required to reduce arr[i] to 1 let opr = Math.ceil(Math.log2(arr[i])); // Decrement k by opr k -= opr; // If k becomes less than 0, // then break out of the loop if (k < 0) { break; } // Increment cnt by 1 cnt++; } // Print the answer document.write(cnt);}// Driver Codelet arr = [ 5, 8, 4, 7 ];let N = arr.length;let K = 5;findMaxNumbers(arr, N, K);</script> |
Output:
2
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
