Given an array arr[] and an integer L which represents the number of bits to be considered in bit representation of an array element. The task is to find a positive integer X, such that the sum of the bit difference of all the elements in arr[] with X is minimum.
Examples:
Input: N = 3, L = 5, arr[] = {18, 9, 21}
Output: 17
Explanation: arr[1] = (18)10 = (10010)2, arr[2] = (9)10 = (01001)2, arr[3] = (21)10 = (10101)2
Suppose X = (17)10 = (10001)2.
Difference between arr[1] and X : 2 (Different bits at index 3 and 4)
Difference between arr[2] and X : 2 (Different bits at index 0 and 1)
Difference between arr[3] and X : 1 (Different bits at index 2)
Therefore if X = 17, the sum of bit differences will be 2 + 2 +1 = 5, which is the minimum possible.Input: N = 3, L = 5 and arr[] = {8, 8, 8}
Output: 8
Approach: This problem can be solved using below idea:
- At bit position i, the bit in the resultant X should be the same as the majority bit at the ith position of all Array elements.
- This can be achieved using Hashing.
Illustration:
Suppose array is {5, 6, 4}
Bit representation of array:
5 = 101
6 = 110
4 = 100Now lets find the X using positionwise majority bit of Array:
At position 1: majority(1, 1, 1) = 1
At position 2: majority(0, 1, 0) = 0
At position 3: majority(1, 0, 0) = 0Therefore X formed = 100 = 4
Now lets find the bit difference of X with Array elements:
BitDifference(X, 5) = BitDifference(100, 101) = 1
BitDifference(X, 6) = BitDifference(100, 110) = 1
BitDifference(X, 4) = BitDifference(100, 100) = 0Sum of bit differences = 2, which will be the least possible.
Follow the steps below to solve the given problem.
- Initialize an array freq of length L which keeps the track of the number of bits set at every position in every given array element.
- Iterate freq and if the frequency of ith index is greater than N/2 then keep to bit set in the required number.
- If the frequency of the ith index is less than N/2 then keep the bit off in the required number.
- Convert the formed binary number into decimal number and return the value.
- Print the final result
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <iostream>using namespace std;// Function to find number// having smallest difference// with N numbersint smallestDifference(int N, int L, int arr[]){ // Initializing freq array // which keeps tracks of // number of set bits at every index int freq[L] = { 0 }; // Making freq map of set bits for (int i = 0; i < L; i++) { // Traversing every element for (int j = 0; j < N; j++) { // If bit is on then // updating freq array if ((arr[j] & 1) > 0) { freq[i]++; } arr[j] >>= 1; } } // Converting binary form of needed // number into decimal form int number = 0; int p = 1; // Traversing freq array for (int i = 0; i < L; i++) { // If frequency of set bit // is greater than N/2 // then we have to keep it set // in our answer if (freq[i] > N / 2) { number += p; } p *= 2; } // Returning numbers // having smallest difference // among N given numbers return number;}// Driver Codeint main(){ int N = 3; int L = 5; int arr[] = { 18, 9, 21 }; // Function call int number = smallestDifference(N, L, arr); cout << number << endl; return 0;} |
Java
// Java program for above approachimport java.util.*;class GFG { // Function to find number // having smallest difference // with N numbers public static int smallestDifference(int N, int L, int[] arr) { // Initializing freq array // which keeps tracks of // number of set bits at every index int[] freq = new int[L]; // Making freq map of set bits for (int i = 0; i < L; i++) { // Traversing every element for (int j = 0; j < N; j++) { // If bit is on then // updating freq array if ((arr[j] & 1) > 0) { freq[i]++; } arr[j] >>= 1; } } // Converting binary form of needed // number into decimal form int number = 0; int p = 1; // Traversing freq array for (int i = 0; i < L; i++) { // If frequency of set bit // is greater than N/2 // then we have to keep it set // in our answer if (freq[i] > N / 2) { number += p; } p *= 2; } // Returning numbers // having smallest difference // among N given numbers return number; } // Driver Code public static void main(String[] args) { int N = 3; int L = 5; int[] arr = { 18, 9, 21 }; // Function call int number = smallestDifference(N, L, arr); System.out.println(number); }} |
Python
# Python program for above approach# Function to find number# having smallest difference# with N numbersdef smallestDifference(N, L, arr): # Initializing freq array # which keeps tracks of # number of set bits at every index freq = [] for i in range(0, L): freq.append(0) # Making freq map of set bits for i in range(0, L): # Traversing every element for j in range(0, N): # If bit is on then # updating freq array if ((arr[j] & 1) > 0): freq[i] += 1 arr[j] >>= 1 # Converting binary form of needed # number into decimal form number = 0 p = 1 # Traversing freq array for i in range(0, L): # If frequency of set bit # is greater than N/2 # then we have to keep it set # in our answer if (freq[i] > N // 2): number += p p *= 2 # Returning numbers # having smallest difference # among N given numbers return number# Driver CodeN = 3L = 5arr = [18, 9, 21]# Function callnumber = smallestDifference(N, L, arr)print(number)# This code is contributed by Samim Hossain Mondal. |
C#
using System;public class GFG{ // Function to find number // having smallest difference // with N numbers public static int smallestDifference(int N, int L, int[] arr) { // Initializing freq array // which keeps tracks of // number of set bits at every index int[] freq = new int[L]; // Making freq map of set bits for (int i = 0; i < L; i++) { // Traversing every element for (int j = 0; j < N; j++) { // If bit is on then // updating freq array if ((arr[j] & 1) > 0) { freq[i]++; } arr[j] >>= 1; } } // Converting binary form of needed // number into decimal form int number = 0; int p = 1; // Traversing freq array for (int i = 0; i < L; i++) { // If frequency of set bit // is greater than N/2 // then we have to keep it set // in our answer if (freq[i] > N / 2) { number += p; } p *= 2; } // Returning numbers // having smallest difference // among N given numbers return number; } // Driver Code static public void Main () { int N = 3; int L = 5; int[] arr = { 18, 9, 21 }; // Function call int number = smallestDifference(N, L, arr); Console.Write(number); }}// This code is contributed by hrithikgarg03188. |
Javascript
<script>// Javascript program for above approach// Function to find number// having smallest difference// with N numbersfunction smallestDifference(N, L, arr){ // Initializing freq array // which keeps tracks of // number of set bits at every index let freq = []; for(let i = 0; i < L; i++) { freq[i] = 0; } // Making freq map of set bits for (let i = 0; i < L; i++) { // Traversing every element for (let j = 0; j < N; j++) { // If bit is on then // updating freq array if ((arr[j] & 1) > 0) { freq[i]++; } arr[j] >>= 1; } } // Converting binary form of needed // number into decimal form let number = 0; let p = 1; // Traversing freq array for (let i = 0; i < L; i++) { // If frequency of set bit // is greater than N/2 // then we have to keep it set // in our answer if (freq[i] > N / 2) { number += p; } p *= 2; } // Returning numbers // having smallest difference // among N given numbers return number;}// Driver Codelet N = 3;let L = 5;let arr = [ 18, 9, 21 ];// Function calllet number = smallestDifference(N, L, arr);document.write(number);// This code is contributed by Samim Hossain Mondal.</script> |
17
Time Complexity: O(N*L)
Auxiliary Space: O(L)
