Given an array arr of positive integers of size N, the task is to split the array into 3 partitions, such that the sum of bitwise XOR of each element of the array with its partition number is maximum.
Examples:
Input: arr[] = { 2, 4, 7, 1, 8, 7, 2 }
Output: First partition: 2 4 7 1 8
Second partition: 7
Third partition: 2
Sum: 244Input: arr[] = {95, 2, 86, 12, 9, 14, 45, 11}
Output: First partition: 95 2 86 12 9 14
Second partition: 45
Third partition: 11
Sum: 1994
Approach: The idea is to use nested loops for three partitions.
- Compute the XOR sum of each element of each partition with its partition number.
- Find the global maximum sum of all three partitions’ XOR sum.
- Return and print the three partitions and their maximum XOR sum.
Below is the implementation of the above approach:
C++
// C++ program for maximize the sum of// bitwise XOR of each element of the array// with it's partition number#include <bits/stdc++.h>using namespace std;// Utility function to print the partitionsvoid ShowPartition(vector<int> sum, vector<int> arr){ cout << "First partition: "; for (int i = 0; i <= sum[0]; i++) cout << arr[i] << " "; cout << "\nSecond partition: "; for (int i = sum[0] + 1; i <= sum[1]; i++) cout << arr[i] << " "; cout << "\nThird partition: "; for (int i = sum[1] + 1; i <= sum[2]; i++) cout << arr[i] << " "; cout << "\nSum: "; cout << sum[3];}// Function to maximise the partitions sumvector<int> MaximumSumPartition(vector<int> arr){ int i, j, k; int n = arr.size(); vector<int> sum(4, 0); // initialise the dummy sum values. int s1 = 0, s2 = 0, s3 = 0, s = INT_MIN; int x, y, z; // nested for loop for (i = 0; i <= n - 3; i++) { // XOR sum of first partition. s1 += 1 ^ arr[i]; x = i; for (j = i + 1; j <= n - 2; j++) { // XOR sum of second partition. s2 += 2 ^ arr[j]; y = j; for (k = j + 1; k <= n - 1; k++) { // XOR sum of third partition. s3 += 3 ^ arr[k]; z = k; // XOR sum of all three partition. if (s1 + s2 + s3 > s) { s = s1 + s2 + s3; sum[0] = x; sum[1] = y; sum[2] = z; sum[3] = s; } } } } // return the vector. return sum;}// Driver codeint main(){ vector<int> sum, arr{ 2, 4, 7, 1, 8, 7, 2 }; sum = MaximumSumPartition(arr); ShowPartition(sum, arr); return 0;} |
Java
// Java program for maximize the sum of// bitwise XOR of each element of the array// with it's partition numberimport java.io.*;class GFG { // Utility function to print the partitions static void ShowPartition(int []sum, int []arr) { System.out.print("First partition: "); for (int i = 0; i <= sum[0]; i++) System.out.print(arr[i] + " "); System.out.print("\nSecond partition: "); for (int i = sum[0] + 1; i <= sum[1]; i++) System.out.print(arr[i] + " "); System.out.print("\nThird partition: "); for (int i = sum[1] + 1; i <= sum[2]; i++) System.out.print(arr[i] + " "); System.out.print("\nSum: "); System.out.print(sum[3]); } // Function to maximise the partitions sum static int[] MaximumSumPartition(int []arr) { int i = 0, j = 0, k = 0; int n = arr.length; int []sum = new int[4]; for(i = 0; i < 4; i++) { sum[i] = 0; } // initialise the dummy sum values. int s1 = 0, s2 = 0, s3 = 0, s = Integer.MIN_VALUE; int x = 0, y = 0, z = 0; // nested for loop for (i = 0; i <= n - 3; i++) { // XOR sum of first partition. s1 += 1 ^ arr[i]; x = i; for (j = i + 1; j <= n - 2; j++) { // XOR sum of second partition. s2 += 2 ^ arr[j]; y = j; for (k = j + 1; k <= n - 1; k++) { // XOR sum of third partition. s3 += 3 ^ arr[k]; z = k; // XOR sum of all three partition. if (s1 + s2 + s3 > s) { s = s1 + s2 + s3; sum[0] = x; sum[1] = y; sum[2] = z; sum[3] = s; } } } } // return the vector. return sum; } // Driver code public static void main (String[] args) { int []arr = { 2, 4, 7, 1, 8, 7, 2 }; int []sum = MaximumSumPartition(arr); ShowPartition(sum, arr); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python code to implement the approachimport sys# Utility function to print the partitionsdef ShowPartition(sum, arr) : print("First partition: ", end = '') for i in range(sum[0]+1) : print(arr[i] , end = " ") print("\nSecond partition: ", end = '') for i in range(sum[0]+1, sum[1]+1) : print(arr[i] , end = " ") print("\nThird partition: ", end = '') for i in range(sum[1]+1, sum[2]+1) : print(arr[i] , end = " ") print("\nSum: ", end = '') print(sum[3]) # Function to maximise the partitions sumdef MaximumSumPartition(arr) : i = 0 j = 0 k = 0 n = len(arr) sum = [0] * 4 for i in range(0, 4): sum[i] = 0 # initialise the dummy sum values. s1 = 0 s2 = 0 s3 = 0 s = -sys.maxsize -1 x = 0 y = 0 z = 0 # nested for loop for i in range(0, n-2, 1): # XOR sum of first partition. s1 += 1 ^ arr[i] x = i for j in range(i + 1, n - 1, 1) : # XOR sum of second partition. s2 += 2 ^ arr[j] y = j for k in range(j + 1, n, 1) : # XOR sum of third partition. s3 += 3 ^ arr[k] z = k # XOR sum of all three partition. if (s1 + s2 + s3 > s) : s = s1 + s2 + s3 sum[0] = x sum[1] = y sum[2] = z sum[3] = s # return the vector. return sum # Driver codearr = [ 2, 4, 7, 1, 8, 7, 2 ] sum = MaximumSumPartition(arr);ShowPartition(sum, arr);# This code is contributed by code_hunt. |
C#
// C# program for maximize the sum of// bitwise XOR of each element of the array// with it's partition numberusing System;class GFG{ // Utility function to print the partitions static void ShowPartition(int []sum, int []arr) { Console.Write("First partition: "); for (int i = 0; i <= sum[0]; i++) Console.Write(arr[i] + " "); Console.Write("\nSecond partition: "); for (int i = sum[0] + 1; i <= sum[1]; i++) Console.Write(arr[i] + " "); Console.Write("\nThird partition: "); for (int i = sum[1] + 1; i <= sum[2]; i++) Console.Write(arr[i] + " "); Console.Write("\nSum: "); Console.Write(sum[3]); } // Function to maximise the partitions sum static int[] MaximumSumPartition(int []arr) { int i = 0, j = 0, k = 0; int n = arr.Length; int []sum = new int[4]; for(i = 0; i < 4; i++) { sum[i] = 0; } // initialise the dummy sum values. int s1 = 0, s2 = 0, s3 = 0, s = Int32.MinValue; int x = 0, y = 0, z = 0; // nested for loop for (i = 0; i <= n - 3; i++) { // XOR sum of first partition. s1 += 1 ^ arr[i]; x = i; for (j = i + 1; j <= n - 2; j++) { // XOR sum of second partition. s2 += 2 ^ arr[j]; y = j; for (k = j + 1; k <= n - 1; k++) { // XOR sum of third partition. s3 += 3 ^ arr[k]; z = k; // XOR sum of all three partition. if (s1 + s2 + s3 > s) { s = s1 + s2 + s3; sum[0] = x; sum[1] = y; sum[2] = z; sum[3] = s; } } } } // return the vector. return sum; } // Driver code public static void Main() { int []arr = { 2, 4, 7, 1, 8, 7, 2 }; int []sum = MaximumSumPartition(arr); ShowPartition(sum, arr); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for maximize the sum of // bitwise XOR of each element of the array // with it's partition number const INT_MIN = -2147483647 - 1; // Utility function to print the partitions const ShowPartition = (sum, arr) => { document.write("First partition: "); for (let i = 0; i <= sum[0]; i++) document.write(`${arr[i]} `); document.write("<br/>Second partition: "); for (let i = sum[0] + 1; i <= sum[1]; i++) document.write(`${arr[i]} `); document.write("<br/>Third partition: "); for (let i = sum[1] + 1; i <= sum[2]; i++) document.write(`${arr[i]} `); document.write("<br/>Sum: "); document.write(sum[3]); } // Function to maximise the partitions sum const MaximumSumPartition = (arr) => { let i, j, k; let n = arr.length; let sum = new Array(4).fill(0); // initialise the dummy sum values. let s1 = 0, s2 = 0, s3 = 0, s = INT_MIN; let x, y, z; // nested for loop for (i = 0; i <= n - 3; i++) { // XOR sum of first partition. s1 += 1 ^ arr[i]; x = i; for (j = i + 1; j <= n - 2; j++) { // XOR sum of second partition. s2 += 2 ^ arr[j]; y = j; for (k = j + 1; k <= n - 1; k++) { // XOR sum of third partition. s3 += 3 ^ arr[k]; z = k; // XOR sum of all three partition. if (s1 + s2 + s3 > s) { s = s1 + s2 + s3; sum[0] = x; sum[1] = y; sum[2] = z; sum[3] = s; } } } } // return the vector. return sum; } // Driver code let arr = [2, 4, 7, 1, 8, 7, 2]; let sum = MaximumSumPartition(arr); ShowPartition(sum, arr); // This code is contributed by rakeshsahni</script> |
Output
First partition: 2 4 7 1 8 Second partition: 7 Third partition: 2 Sum: 244
Time Complexity: O(N3)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
