Dada una array arr de enteros positivos de tamaño N , la tarea es dividir la array en 3 particiones, de modo que la suma de XOR bit a bit de cada elemento de la array con su número de partición sea máxima.
Ejemplos :
Entrada: arr[] ={ 2, 4, 7, 1, 8, 7, 2 }
Salida: Primera partición: 2 4 7 1 8
Segunda partición: 7
Tercera partición: 2
Suma: 244Entrada: arr[] = {95, 2, 86, 12, 9, 14, 45, 11}
Salida: Primera partición: 95 2 86 12 9 14
Segunda partición: 45
Tercera partición: 11
Suma: 1994
Enfoque : la idea es utilizar bucles anidados para tres particiones.
- Calcule la suma XOR de cada elemento de cada partición con su número de partición.
- Encuentre la suma máxima global de la suma XOR de las tres particiones.
- Devuelva e imprima las tres particiones y su suma XOR máxima.
A continuación se muestra la implementación del enfoque anterior:
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 partitions
void 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 sum
vector<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 code
int 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 number
import 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 approach
import sys
# Utility function to print the partitions
def 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 sum
def 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 code
arr = [ 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 number
using 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>
Producción
First partition: 2 4 7 1 8 Second partition: 7 Third partition: 2 Sum: 244
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA