# Maximize count of 1s in an array by repeated division of array elements by 2 at most K times

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {5, 8, 4, 7}, K = 5Output:2Explanation: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 = 51Output:

**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 **i ^{th}** 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**.

- Store the number of operations required to reduce
- 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 2` `void` `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 Code` `int` `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 approach` `import` `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 2` `static` `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 Code` `public` `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 approach` `import` `math` `# Function to count the maximum number of` `# array elements that can be reduced to 1` `# by repeatedly dividing array elements by 2` `def` `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 Code` `arr ` `=` `[ ` `5` `, ` `8` `, ` `4` `, ` `7` `]` `N ` `=` `len` `(arr)` `K ` `=` `5` `findMaxNumbers(arr, N, K)` `# This code is contributed by splevel62.` |

## C#

`// C# program for the above approach` `using` `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 2` `static` `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 Code` `public` `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 2` `function` `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 Code` `let 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)