Given an array arr[] consisting of N positive integers, where N is even, the task is to form N/2 pairs such that the sum of the Least Significant Bit of Bitwise OR of all these pairs is maximum.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output: 8
Explanation:
On forming the pairs as (8, 4),(6, 2),(1, 3),(5, 7), the Bitwise OR of the pair is given by:
8 OR 4 = 12 and LSB = 4
6 OR 2 = 6 and LSB = 2
1 OR 3 = 3 and LSB = 1
5 OR 7 = 7 and LSB = 1
The sum of all the LSB is 4 + 2 + 1 + 1 = 8, which is maximum possible sum.Input: arr[] = {1, 2, 3, 4, 5}
Output: 3
Approach: The given problem can be solved by finding the LSB of each array element arr[i] and store them in another array, say lsb_arr[] and sort this array in descending order. Now, storing just the LSB of each array element is sufficient because in the answer, it is only requires to consider the LSB. So, only the LSB’s can be used for the Bitwise OR operation. Now, consider each pair (i, i + 1) and add the minimum of these two to the result. Follow the steps below to solve the given problem:
- Initialize a list lsb_arr[] to store the least significant bit of all array element arr[i].
- Traverse over the range [0, N) and store the LSB of each arr[i] in lsb_arr[].
- Sort the list lsb_arr[] in descending order.
- Initialize the variable ans as 0 to store the result sum of Least Significant Bits.
- Traverse over the range [0, N) using the variable i and add the value of element at (i + 1) position to the variable ans and increase the value of i by 2.
- After completing the above steps, print the value of ans as the resultant.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function top get LSB value of vint chk(int n){ // Binary conversion vector<int> v; while (n != 0) { v.push_back(n % 2); n = n / 2; } for (int i = 0; i < v.size(); i++) { if (v[i] == 1) { return pow(2, i); } } return 0;}// Function to find the sum of LSBs of// all possible pairs of the given arrayvoid sumOfLSB(int arr[], int N){ // Stores the LSB of array elements vector<int> lsb_arr; for (int i = 0; i < N; i++) { // Storing the LSB values lsb_arr.push_back(chk(arr[i])); } // Sort the array lab_arr[] sort(lsb_arr.begin(), lsb_arr.end(), greater<int>()); int ans = 0; for (int i = 0; i < N - 1; i += 2) { // Taking pairwise sum to get // the maximum sum of LSB ans += (lsb_arr[i + 1]); } // Print the result cout << (ans);}// Driver Codeint main(){ int N = 5; int arr[] = { 1, 2, 3, 4, 5 }; // Function Call sumOfLSB(arr, N);}// This code is contributed by Potta Lokesh |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function top get LSB value of vstatic int chk(int n){ // Binary conversion Vector<Integer> v = new Vector<Integer>(); while (n != 0) { v.add(n % 2); n = n / 2; } for (int i = 0; i < v.size(); i++) { if (v.get(i) == 1) { return (int) Math.pow(2, i); } } return 0;}// Function to find the sum of LSBs of// all possible pairs of the given arraystatic void sumOfLSB(int arr[], int N){ // Stores the LSB of array elements Vector<Integer> lsb_arr = new Vector<Integer>() ; for (int i = 0; i < N; i++) { // Storing the LSB values lsb_arr.add(chk(arr[i])); } // Sort the array lab_arr[] Collections.sort(lsb_arr); int ans = 0; for (int i = 0; i < N - 1; i += 2) { // Taking pairwise sum to get // the maximum sum of LSB ans += (lsb_arr.get(i + 1)); } // Print the result System.out.print(ans);}// Driver Codepublic static void main(String[] args){ int N = 5; int arr[] = { 1, 2, 3, 4, 5 }; // Function Call sumOfLSB(arr, N);}}// This code contributed by shikhasingrajput |
Python3
# Python program for the above approach# Function top get LSB value of vdef chk(v): # Binary conversion v = list(bin(v)[2:]) v.reverse() if('1' in v): v = v.index('1') return (2**v) else: return 0# Function to find the sum of LSBs of# all possible pairs of the given arraydef sumOfLSB(arr, N): # Stores the LSB of array elements lsb_arr = [] for i in range(N): # Storing the LSB values lsb_arr.append(chk(arr[i])) # Sort the array lab_arr[] lsb_arr.sort(reverse=True) ans = 0 for i in range(0, N-1, 2): # Taking pairwise sum to get # the maximum sum of LSB ans += (lsb_arr[i+1]) # Print the result print(ans)# Driver CodeN = 5arr = [1, 2, 3, 4, 5]# Function CallsumOfLSB(arr, N) |
Javascript
<script> // JavaScript program for the above approach // Function top get LSB value of v const chk = (n) => { // Binary conversion let v = []; while (n != 0) { v.push(n % 2); n = parseInt(n / 2); } for (let i = 0; i < v.length; i++) { if (v[i] == 1) { return Math.pow(2, i); } } return 0; } // Function to find the sum of LSBs of // all possible pairs of the given array const sumOfLSB = (arr, N) => { // Stores the LSB of array elements let lsb_arr = []; for (let i = 0; i < N; i++) { // Storing the LSB values lsb_arr.push(chk(arr[i])); } // Sort the array lab_arr[] lsb_arr.sort((a, b) => a - b) let ans = 0; for (let i = 0; i < N - 1; i += 2) { // Taking pairwise sum to get // the maximum sum of LSB ans += (lsb_arr[i + 1]); } // Print the result document.write(ans); } // Driver Code let N = 5; let arr = [1, 2, 3, 4, 5]; // Function Call sumOfLSB(arr, N); // This code is contributed by rakeshsahni</script> |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function top get LSB value of vstatic int chk(int n){ // Binary conversion List<int> v = new List<int>(); while (n != 0) { v.Add(n % 2); n = n / 2; } int j = 0; foreach(int i in v) { if (i == 1) { return (int) Math.Pow(2.0, (double)j); } j++; } return 0;}// Function to find the sum of LSBs of// all possible pairs of the given arraystatic void sumOfLSB(int[] arr, int N){ // Stores the LSB of array elements int[] lsb_arr = new int[N]; for (int i = 0; i < N; i++) { // Storing the LSB values lsb_arr[i] = chk(arr[i]); } // Sort the array lab_arr[] Array.Sort(lsb_arr); int ans = 0; for (int i = 0; i < N - 1; i += 2) { // Taking pairwise sum to get // the maximum sum of LSB ans += (lsb_arr[i + 1]); } // Print the result Console.WriteLine(ans);}// Driver Codestatic public void Main (){ int N = 5; int[] arr = { 1, 2, 3, 4, 5 }; // Function Call sumOfLSB(arr, N);}}// This code is contributed by Dharanendra L V. |
Output:
3
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
