Given an integer array arr[] of size N, the task is to find the minimum number of array elements required to be divided by 2, to make at least K elements in the array equal.
Example :
Input: arr[] = {1, 2, 2, 4, 5}, N = 5, K = 3
Output: 1
Explanation:
Dividing 4 by 2 modifies the array to {1, 2, 2, 2, 5} with 3 equal elements.
Input: arr[] = {1, 2, 3, 4, 5}, N = 5, K = 3
Output: 1
Explanation:
Dividing 2 and 3 by 2 modifies the array to {1, 1, 1, 4, 5} with 3 equal elements.
Approach:
Every integer X can be divided by 2 log2(X) times to get a non-zero value. Hence, we need to perform these log2(arr[i]) operations on every array element arr[i] and for every value obtained after a division, store the number of operations required to reach the respective value. Once, all operations are performed for all array elements, for every value that at least K array elements have been reduced to at some point, find the sum of smallest K operations required among all of them. Find the minimum number of operations required among all such instances.
Illustration:
arr[] = {1, 2, 2, 4, 5}, N = 5, K = 3
Only 1 element can have a value 5, so ignore.
Only 1 element can have a value 4, so ignore.
No element can have a value 3.
4 elements can have a value 2.
{1, 2, 2, (4/2), (5/2) } -> {1, 2, 2, 2, 2}
Since, the number of possibilities exceeds K, find the sum of the smallest K operations.
arr[1] -> 0 operations
arr[2] -> 0 operations
arr[3] -> 1 operation
arr[4] -> 1 operation
Hence, sum of smallest 3 operations = (0 + 0 + 1) = 1
All 5 elements can be reduced to 1.
{1, 2/2, 2/2, (4/2)/2, (5/2)/2} -> {1, 1, 1, 1, 1}
Hence, the sum of smallest 3 operations = (0 + 1 + 1) = 2
Hence, the minimum number of operations required to make at least K elements equal is 1.
Follow the steps below to solve the problem using the above approach:
- Create a matrix vals[][] such that vals [ X ][ j ] will store the number of operations needed to obtain value X from an array element.
- Traverse the array and for every array element:
- Initialize x = arr[i]. Initialize count of operations cur as 0.
- At every step, update x = x/2 and increment cur by 1. Insert cur into vals[x] as the number of divisions required to obtain the current value of x.
- Now, all possible values that can be obtained by repetitive division of every arr[i] by 2 with the number of such divisions required to get that value are stored in the vals[][] matrix.
- Now, traverse the matrix vals[][] and for every row, perform the following:
- Check if the current row vals[i] consists of at least K elements or not. If vals[i] < K, ignore as at least K array elements cannot be reduced to i.
- If vals[i].size() is ? K, calculate the sum of the row i. Update ans = min(ans, sum of vals[i]).
- The final value of ans gives us the desired answer.
Below is the implementation of the above approach :
C++
// C++ program to make atleast// K elements of the given array// equal by dividing by 2#include <bits/stdc++.h>using namespace std;// Function to return the// minimum number of divisions// requiredint get_min_opration(int arr[], int N, int K){ vector<vector<int> > vals(200001); for (int i = 0; i < N; ++i) { int x = arr[i]; int cur = 0; while (x > 0) { // cur: number of // times a[i] is // divided by 2 // to obtain x vals[x].push_back(cur); x /= 2; ++cur; } } int ans = INT_MAX; for (int i = 0; i <= 200000; ++i) { // To obtain minimum // number of operations sort(vals[i].begin(), vals[i].end()); } for (int i = 0; i <= 200000; ++i) { // If it is not possible // to make at least K // elements equal to vals[i] if (int(vals[i].size()) < K) continue; // Store the number // of operations int sum = 0; for (int j = 0; j < K; j++) { sum += vals[i][j]; } // Update the minimum // number of operations // required ans = min(ans, sum); } return ans;}// Driver Programint main(){ int N = 5, K = 3; int arr[] = { 1, 2, 2, 4, 5 }; cout << get_min_opration(arr, N, K); return 0;} |
Java
// Java program to make atleast// K elements of the given array// equal by dividing by 2import java.util.*;class GFG{// Function to return the// minimum number of divisions// requiredstatic int get_min_opration(int arr[], int N, int K){ Vector<Integer> []vals = new Vector[200001]; for (int i = 0; i < vals.length; i++) vals[i] = new Vector<Integer>(); for (int i = 0; i < N; ++i) { int x = arr[i]; int cur = 0; while (x > 0) { // cur: number of // times a[i] is // divided by 2 // to obtain x vals[x].add(cur); x /= 2; ++cur; } } int ans = Integer.MAX_VALUE; for (int i = 0; i <= 200000; ++i) { // To obtain minimum // number of operations Collections.sort(vals[i]); } for (int i = 0; i <= 200000; ++i) { // If it is not possible // to make at least K // elements equal to vals[i] if ((vals[i].size()) < K) continue; // Store the number // of operations int sum = 0; for (int j = 0; j < K; j++) { sum += vals[i].get(j); } // Update the minimum // number of operations // required ans = Math.min(ans, sum); } return ans;} // Driver codepublic static void main(String[] args){ int N = 5, K = 3; int arr[] = {1, 2, 2, 4, 5}; System.out.print(get_min_opration(arr, N, K));}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program to make atleast# K elements of the given array# equal by dividing by 2import sys# Function to return the# minimum number of divisions# requireddef get_min_opration(arr, N, K): vals = [[] for _ in range(200001)] for i in range(N): x = arr[i] cur = 0 while (x > 0): # cur: number of times a[i] # is divided by 2 to obtain x vals[x].append(cur) x //= 2 cur += 1 ans = sys.maxsize for i in range(200001): # To obtain minimum # number of operations vals[i] = sorted(vals[i]) for i in range(200001): # If it is not possible # to make at least K # elements equal to vals[i] if (int(len(vals[i])) < K): continue # Store the number # of operations sum = 0 for j in range(K): sum += vals[i][j] # Update the minimum # number of operations # required ans = min(ans, sum) return ans# Driver codeif __name__ == '__main__': N = 5 K = 3 arr = [ 1, 2, 2, 4, 5 ] print(get_min_opration(arr, N, K))# This code is contributed by mohit kumar 29 |
C#
// C# program to make atleast// K elements of the given array// equal by dividing by 2using System;using System.Collections.Generic;class GFG{// Function to return the// minimum number of divisions// requiredstatic int get_min_opration(int []arr, int N, int K){ List<int> []vals = new List<int>[200001]; for (int i = 0; i < vals.Length; i++) vals[i] = new List<int>(); for (int i = 0; i < N; ++i) { int x = arr[i]; int cur = 0; while (x > 0) { // cur: number of // times a[i] is // divided by 2 // to obtain x vals[x].Add(cur); x /= 2; ++cur; } } int ans = int.MaxValue; for (int i = 0; i <= 200000; ++i) { // If it is not possible // to make at least K // elements equal to vals[i] if ((vals[i].Count) < K) continue; // Store the number // of operations int sum = 0; for (int j = 0; j < K; j++) { sum += vals[i][j]; } // Update the minimum // number of operations // required ans = Math.Min(ans, sum); } return ans;} // Driver codepublic static void Main(String[] args){ int N = 5, K = 3; int []arr = {1, 2, 2, 4, 5}; Console.Write(get_min_opration(arr, N, K));}}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program to make atleast // K elements of the given array // equal by dividing by 2 // Function to return the // minimum number of divisions // required function get_min_opration(arr, N, K) { var vals = new Array(200001); for (var i = 0; i < vals.length; i++) vals[i] = []; for (var i = 0; i < N; ++i) { var x = arr[i]; var cur = 0; while (x > 0) { // cur: number of // times a[i] is // divided by 2 // to obtain x vals[x].push(cur); x = parseInt(x / 2); ++cur; } } //Max integer value var ans = 2147483648; for (var i = 0; i <= 200000; ++i) { // If it is not possible // to make at least K // elements equal to vals[i] if (vals[i].length < K) continue; // Store the number // of operations var sum = 0; for (var j = 0; j < K; j++) { sum += vals[i][j]; } // Update the minimum // number of operations // required ans = Math.min(ans, sum); } return ans; } // Driver code var N = 5, K = 3; var arr = [1, 2, 2, 4, 5]; document.write(get_min_opration(arr, N, K)); </script> |
1
Time Complexity: O (N * log N)
Auxiliary Space: O (N * log N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
