Given an array arr[] consisting of N positive integers, the task is to find the maximum absolute difference between the sum of the array elements placed at even indices and those at odd indices of the array by rotating their binary representations any number of times. Consider only 8-bit representation.
Examples:
Input: arr[] = {123, 86, 234, 189}
Output: 326
Explanation:
Following are the rotation of elements:
- For arr[0] (= 123): arr[0] = (123)10 = (1111011)2. Rotate the bits to the right twice to make arr[0] = (1111100)2 = (246)10.
- For arr[1] (= 86): arr[1] = (86)10 = (1010110)2. Rotate the bits to the right once to make arr[1] = (0101011)2 = (43)10.
- For element arr[3](=189): arr[3] = (189)10 = (10111101)2. Rotate the bits once to the left to make arr[3] = (011111011)2 = (111)10.
Therefore, the array arr[] modifies to {246, 43, 234, 111}. The maximum absolute difference = (246 + 234) – (43 + 111) = 326.
Input: arr[] = {211, 122, 212, 222}, N = 4
Output: 376
Approach: The given problem can be solved by minimizing elements either at even or odd indices and maximizing elements other indices by rotating the binary representation of each array elements and find the maximum difference. Follow the steps below to solve the problem:
- Define a function say Rotate(X, f) to find the maximum and minimum value of a number possible after rotating the bits in the binary representation of any number.
- Initialize two variables, say maxi = X and mini = X to store the maximum and minimum value of the number X possible.
- Iterate over the bits of the number X and then rotate the bits of X by performing the following:
- If X is odd, then update the value of X as X >> 1 and X = X | (1<<7).
- Otherwise, update the value of X as X >> 1.
- Update the value of maxi as the maximum of maxi and X.
- Update the value of mini as the minimum of mini and X.
- If the value of f is 1, return maxi. Otherwise, return mini.
- Now, find the difference obtained by maximizing the element placed at even indices and minimizing the elements placed at odd indices and store that difference in a variable, say caseOne.
- Now, find the difference obtained by minimizing the element placed at even indices and maximizing the elements placed at odd indices and store that difference in a variable, say caseTwo.
- After completing the above steps, print the maximum of caseOne and caseTwo 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 find maximum and// minimum value of a number that// can be obtained by rotating bitsint Rotate(int n, int f){ // Stores the value of N int temp = n; // Stores the maximum value int maxi = n; // Stores the minimum value int mini = n; for (int idx = 0; idx < 7; idx++) { // If temp is odd if (temp & 1) { temp >>= 1; temp += pow(2, 7); } else temp >>= 1; // Update the maximum // and the minimum value mini = min(mini, temp); maxi = max(maxi, temp); } // If flag is 1, then // return the maximum value if (f) return (maxi); // Otherwise, return // the maximum value else return (mini);}// Function to find the maximum difference// between the sum of odd and even-indexed// array elements possible by rotating bitsint calcMinDiff(int arr[], int n){ // Stores the maximum difference int caseOne = 0; // Stores the sum of elements // present at odd indices int sumOfodd = 0; // Stores the sum of elements // present at even indices int sumOfeven = 0; // Traverse the given array for (int i = 0; i < n; i++) { // If the index is even if (i % 2) sumOfodd += Rotate(arr[i], 0); else sumOfeven += Rotate(arr[i], 1); } // Update the caseOne caseOne = abs(sumOfodd - sumOfeven); // Stores the maximum difference int caseTwo = 0; // Stores the sum of elements // placed at odd positions sumOfodd = 0; // Stores the sum of elements // placed at even positions sumOfeven = 0; // Traverse the array for (int i = 0; i < n; i++) { // If the index is even if (i % 2) sumOfodd += Rotate(arr[i], 1); else sumOfeven += Rotate(arr[i], 0); } // Update the caseTwo caseTwo = abs(sumOfodd - sumOfeven); // Return the maximum of caseOne // and caseTwo return max(caseOne, caseTwo);}// Driver Codeint main(){ int arr[] = { 123, 86, 234, 189 }; int n = sizeof(arr) / sizeof(arr[0]); cout << (calcMinDiff(arr, n));}// This code is contributed by ukasp. |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find maximum and// minimum value of a number that// can be obtained by rotating bitsstatic int Rotate(int n, int f){ // Stores the value of N int temp = n; // Stores the maximum value int maxi = n; // Stores the minimum value int mini = n; for (int idx = 0; idx < 7; idx++) { // If temp is odd if (temp %2 == 1) { temp >>= 1; temp += Math.pow(2, 7); } else temp >>= 1; // Update the maximum // and the minimum value mini = Math.min(mini, temp); maxi = Math.max(maxi, temp); } // If flag is 1, then // return the maximum value if (f==1) return (maxi); // Otherwise, return // the maximum value else return (mini);}// Function to find the maximum difference// between the sum of odd and even-indexed// array elements possible by rotating bitsstatic int calcMinDiff(int arr[], int n){ // Stores the maximum difference int caseOne = 0; // Stores the sum of elements // present at odd indices int sumOfodd = 0; // Stores the sum of elements // present at even indices int sumOfeven = 0; // Traverse the given array for (int i = 0; i < n; i++) { // If the index is even if (i % 2==0) sumOfodd += Rotate(arr[i], 0); else sumOfeven += Rotate(arr[i], 1); } // Update the caseOne caseOne = Math.abs(sumOfodd - sumOfeven); // Stores the maximum difference int caseTwo = 0; // Stores the sum of elements // placed at odd positions sumOfodd = 0; // Stores the sum of elements // placed at even positions sumOfeven = 0; // Traverse the array for (int i = 0; i < n; i++) { // If the index is even if (i % 2==0) sumOfodd += Rotate(arr[i], 1); else sumOfeven += Rotate(arr[i], 0); } // Update the caseTwo caseTwo = Math.abs(sumOfodd - sumOfeven); // Return the maximum of caseOne // and caseTwo return Math.max(caseOne, caseTwo);}// Driver Codepublic static void main(String[] args){ int arr[] = { 123, 86, 234, 189 }; int n = arr.length; System.out.print((calcMinDiff(arr, n)));}}// This code contributed by umadevi9616. |
Python3
# Python program for the above approach# Function to find maximum and# minimum value of a number that# can be obtained by rotating bitsdef Rotate(n, f): # Stores the value of N temp = n # Stores the maximum value maxi = n # Stores the minimum value mini = n for idx in range(7): # If temp is odd if temp & 1: temp >>= 1 temp += 2**7 else: temp >>= 1 # Update the maximum # and the minimum value mini = min(mini, temp) maxi = max(maxi, temp) # If flag is 1, then # return the maximum value if(f): return (maxi) # Otherwise, return # the maximum value else: return (mini)# Function to find the maximum difference# between the sum of odd and even-indexed# array elements possible by rotating bitsdef calcMinDiff(arr): # Stores the maximum difference caseOne = 0 # Stores the sum of elements # present at odd indices sumOfodd = 0 # Stores the sum of elements # present at even indices sumOfeven = 0 # Traverse the given array for i in range(len(arr)): # If the index is even if i % 2: sumOfodd += Rotate(arr[i], 0) else: sumOfeven += Rotate(arr[i], 1) # Update the caseOne caseOne = abs(sumOfodd - sumOfeven) # Stores the maximum difference caseTwo = 0 # Stores the sum of elements # placed at odd positions sumOfodd = 0 # Stores the sum of elements # placed at even positions sumOfeven = 0 # Traverse the array for i in range(len(arr)): # If the index is even if i % 2: sumOfodd += Rotate(arr[i], 1) else: sumOfeven += Rotate(arr[i], 0) # Update the caseTwo caseTwo = abs(sumOfodd - sumOfeven) # Return the maximum of caseOne # and caseTwo return max(caseOne, caseTwo)# Driver Codearr = [123, 86, 234, 189]print(calcMinDiff(arr)) |
C#
// C# program for the above approachusing System;public class GFG {// Function to find maximum and// minimum value of a number that// can be obtained by rotating bitsstatic int Rotate(int n, int f){ // Stores the value of N int temp = n; // Stores the maximum value int maxi = n; // Stores the minimum value int mini = n; for (int idx = 0; idx < 7; idx++) { // If temp is odd if (temp %2 == 1) { temp >>= 1; temp += (int)Math.Pow(2, 7); } else temp >>= 1; // Update the maximum // and the minimum value mini = Math.Min(mini, temp); maxi = Math.Max(maxi, temp); } // If flag is 1, then // return the maximum value if (f==1) return (maxi); // Otherwise, return // the maximum value else return (mini);}// Function to find the maximum difference// between the sum of odd and even-indexed// array elements possible by rotating bitsstatic int calcMinDiff(int[] arr, int n){ // Stores the maximum difference int caseOne = 0; // Stores the sum of elements // present at odd indices int sumOfodd = 0; // Stores the sum of elements // present at even indices int sumOfeven = 0; // Traverse the given array for (int i = 0; i < n; i++) { // If the index is even if (i % 2==0) sumOfodd += Rotate(arr[i], 0); else sumOfeven += Rotate(arr[i], 1); } // Update the caseOne caseOne = Math.Abs(sumOfodd - sumOfeven); // Stores the maximum difference int caseTwo = 0; // Stores the sum of elements // placed at odd positions sumOfodd = 0; // Stores the sum of elements // placed at even positions sumOfeven = 0; // Traverse the array for (int i = 0; i < n; i++) { // If the index is even if (i % 2==0) sumOfodd += Rotate(arr[i], 1); else sumOfeven += Rotate(arr[i], 0); } // Update the caseTwo caseTwo = Math.Abs(sumOfodd - sumOfeven); // Return the maximum of caseOne // and caseTwo return Math.Max(caseOne, caseTwo);} // Driver Code public static void Main(string[] args) { int[] arr = { 123, 86, 234, 189 }; int n = arr.Length; Console.WriteLine((calcMinDiff(arr, n))); }}// This code is contributed by splevel62. |
Javascript
<script>// JavaScript program to implement// the above approach// Function to find maximum and// minimum value of a number that// can be obtained by rotating bitsfunction Rotate(n, f){ // Stores the value of N let temp = n; // Stores the maximum value let maxi = n; // Stores the minimum value let mini = n; for (let idx = 0; idx < 7; idx++) { // If temp is odd if (temp %2 == 1) { temp >>= 1; temp += Math.pow(2, 7); } else temp >>= 1; // Update the maximum // and the minimum value mini = Math.min(mini, temp); maxi = Math.max(maxi, temp); } // If flag is 1, then // return the maximum value if (f==1) return (maxi); // Otherwise, return // the maximum value else return (mini);} // Function to find the maximum difference// between the sum of odd and even-indexed// array elements possible by rotating bitsfunction calcMinDiff(arr, n){ // Stores the maximum difference let caseOne = 0; // Stores the sum of elements // present at odd indices let sumOfodd = 0; // Stores the sum of elements // present at even indices let sumOfeven = 0; // Traverse the given array for (let i = 0; i < n; i++) { // If the index is even if (i % 2==0) sumOfodd += Rotate(arr[i], 0); else sumOfeven += Rotate(arr[i], 1); } // Update the caseOne caseOne = Math.abs(sumOfodd - sumOfeven); // Stores the maximum difference let caseTwo = 0; // Stores the sum of elements // placed at odd positions sumOfodd = 0; // Stores the sum of elements // placed at even positions sumOfeven = 0; // Traverse the array for (let i = 0; i < n; i++) { // If the index is even if (i % 2==0) sumOfodd += Rotate(arr[i], 1); else sumOfeven += Rotate(arr[i], 0); } // Update the caseTwo caseTwo = Math.abs(sumOfodd - sumOfeven); // Return the maximum of caseOne // and caseTwo return Math.max(caseOne, caseTwo);}// Driver code let arr = [ 123, 86, 234, 189 ]; let n = arr.length; document.write((calcMinDiff(arr, n))); </script> |
Output:
326
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
