Dada una array arr[] que consta de N enteros, la tarea es encontrar la suma máxima posible de los cuadrados de los elementos de la array a partir de la array dada mediante la realización de las siguientes operaciones:
- Seleccione cualquier par de elementos de array (arr[i], arr[j])
- Reemplace arr[i] por arr[i] Y arr[j]
- Reemplace arr[j] por arr[i] O arr[j] .
Ejemplos:
Entrada: arr[] = {1, 3, 5}
Salida: 51
Explicación:
Para el par (arr[1], arr[2]), realice las siguientes operaciones:
Reemplace 3 con 3 Y 5, que es igual a 1 Reemplace
5 con 2 O 5, que es igual a 7.
La array modificada obtenida después de los pasos anteriores es {1, 1, 7}.
Por lo tanto, la suma maximizada de los cuadrados se puede calcular como 1 * 1 + 1 * 1 + 7 * 7 = 51.Entrada: arr[] = {8, 9, 9, 1}
Salida: 243
Enfoque: La idea es observar que si x e y son los 2 elementos seleccionados, entonces sea z = x Y y , w = x O y donde x + y = z + w .
- Si x ≤ y , sin pérdida de generalidad, claramente, z ≤ w . Entonces, reescribe la expresión como x + y = (x – d) + (y + d)
Antigua suma de cuadrados = M = x 2 + y 2
Nueva suma de cuadrados = N = (x – d) 2 + (y – d) 2 , d > 0
Diferencia = N – M = 2d(y + d – x) , re > 0
- Si d > 0 , la diferencia es positiva. Por lo tanto, aumentamos con éxito la suma total de cuadrados. La observación anterior se debe al hecho de que el cuadrado de un número mayor es mayor que la suma del cuadrado de un número menor.
- Después de convertir los enteros dados en forma binaria , observamos lo siguiente:
x = 3 = 0 1 1
y = 5 = 1 0 1
z = 1 = 0 0 1
w = 7 = 1 1 1
- Bits establecidos totales en x + y = 2 + 2 = 4, y bits establecidos totales en z + w = 1 + 3 = 4. Por lo tanto, los bits establecidos totales se conservan después de realizar esta operación. Ahora la idea es averiguar z y w .
Por ejemplo: arr[] = {5, 2, 3, 4, 5, 6, 7}
1 0 1 = 5
0 1 0 = 2
0 1 1 = 3
1 0 0 = 4
1 0 1 = 5
1 1 0 = 6
1 1 1 = 7
———-
5 4 4 (suma de bits establecidos)
Ahora, suma los cuadrados de estos números.
- Por lo tanto, itere para cada posición de bit de 1 a 20, almacene el número total de bits en ese índice.
- Luego, mientras construye un número, tome 1 bit a la vez de cada uno de los índices.
- Después de obtener el número, suma el cuadrado del número a la respuesta.
- Imprime el valor de la respuesta después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the maximum value
int ans = 0;
int binary[31];
// Function to find the maximum sum
// of squares for each element of the
// array after updates
void findMaximumSum(
const vector<int>& arr, int n)
{
// Update the binary bit count at
// corresponding indices for
// each element
for (auto x : arr) {
int idx = 0;
// Iterate all set bits
while (x) {
// If current bit is set
if (x & 1)
binary[idx]++;
x >>= 1;
idx++;
}
}
// Construct number according
// to the above defined rule
for (int i = 0; i < n; ++i) {
int total = 0;
// Traverse each binary bit
for (int j = 0; j < 21; ++j) {
// If current bit is set
if (binary[j] > 0) {
total += pow(2, j);
binary[j]--;
}
}
// Square the constructed number
ans += total * total;
}
// Return the answer
cout << ans << endl;
}
// Driver Code
int main()
{
// Given array arr[]
vector<int> arr = { 8, 9, 9, 1 };
int N = arr.size();
// Function call
findMaximumSum(arr, N);
return 0;
}
C
// C program for the above approach
#include <math.h>
#include <stdio.h>
// Stores the maximum value
int ans = 0;
int binary[31];
// Function to find the maximum sum
// of squares for each element of the
// array after updates
void findMaximumSum(const int* arr, int n)
{
// Update the binary bit count at
// corresponding indices for
// each element
for (int i = 0; i < n; i++) {
int x = arr[i];
int idx = 0;
// Iterate all set bits
while (x) {
// If current bit is set
if (x & 1)
binary[idx]++;
x >>= 1;
idx++;
}
}
// Construct number according
// to the above defined rule
for (int i = 0; i < n; ++i) {
int total = 0;
// Traverse each binary bit
for (int j = 0; j < 21; ++j) {
// If current bit is set
if (binary[j] > 0) {
total += pow(2, j);
binary[j]--;
}
}
// Square the constructed number
ans += total * total;
}
// Return the answer
printf("%d\n", ans);
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 8, 9, 9, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
findMaximumSum(arr, N);
return 0;
}
// This code is contributed by phalashi.
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Stores the maximum value
static int ans = 0;
static int []binary = new int[31];
// Function to find the maximum sum
// of squares for each element of the
// array after updates
static void findMaximumSum(int []arr, int n)
{
// Update the binary bit count at
// corresponding indices for
// each element
for(int x : arr)
{
int idx = 0;
// Iterate all set bits
while (x > 0)
{
// If current bit is set
if ((x & 1) > 0)
binary[idx]++;
x >>= 1;
idx++;
}
}
// Connumber according
// to the above defined rule
for(int i = 0; i < n; ++i)
{
int total = 0;
// Traverse each binary bit
for(int j = 0; j < 21; ++j)
{
// If current bit is set
if (binary[j] > 0)
{
total += Math.pow(2, j);
binary[j]--;
}
}
// Square the constructed number
ans += total * total;
}
// Return the answer
System.out.print(ans + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 8, 9, 9, 1 };
int N = arr.length;
// Function call
findMaximumSum(arr, N);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach import math binary = [0] * 31 # Function to find the maximum sum # of squares for each element of the # array after updates def findMaximumSum(arr, n): # Stores the maximum value ans = 0 # Update the binary bit count at # corresponding indices for # each element for x in arr: idx = 0 # Iterate all set bits while (x): # If current bit is set if (x & 1): binary[idx] += 1 x >>= 1 idx += 1 # Construct number according # to the above defined rule for i in range(n): total = 0 # Traverse each binary bit for j in range(21): # If current bit is set if (binary[j] > 0): total += int(math.pow(2, j)) binary[j] -= 1 # Square the constructed number ans += total * total # Return the answer print(ans) # Driver Code # Given array arr[] arr = [ 8, 9, 9, 1 ] N = len(arr) # Function call findMaximumSum(arr, N) # This code is contributed by code_hunt
C#
// C# program for the
// above approach
using System;
class GFG{
// Stores the maximum
// value
static int ans = 0;
static int []binary =
new int[31];
// Function to find the maximum
// sum of squares for each element
// of the array after updates
static void findMaximumSum(int []arr,
int n)
{
// Update the binary bit
// count at corresponding
// indices for each element
for(int i = 0; i < arr.Length; i++)
{
int idx = 0;
// Iterate all set bits
while (arr[i] > 0)
{
// If current bit is set
if ((arr[i] & 1) > 0)
binary[idx]++;
arr[i] >>= 1;
idx++;
}
}
// Connumber according
// to the above defined rule
for(int i = 0; i < n; ++i)
{
int total = 0;
// Traverse each binary bit
for(int j = 0; j < 21; ++j)
{
// If current bit is set
if (binary[j] > 0)
{
total += (int)Math.Pow(2, j);
binary[j]--;
}
}
// Square the constructed
// number
ans += total * total;
}
// Return the answer
Console.Write(ans + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = {8, 9, 9, 1};
int N = arr.Length;
// Function call
findMaximumSum(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Stores the maximum value
var ans = 0;
var binary = Array(31).fill(0);
// Function to find the maximum sum
// of squares for each element of the
// array after updates
function findMaximumSum(arr, n)
{
// Update the binary bit count at
// corresponding indices for
// each element
var i,j;
for (i= 0;i<arr.length;i++) {
var x = arr[i];
var idx = 0;
// Iterate all set bits
while (x) {
// If current bit is set
if (x & 1)
binary[idx]++;
x >>= 1;
idx++;
}
}
// Construct number according
// to the above defined rule
for (i = 0; i < n; ++i) {
var total = 0;
// Traverse each binary bit
for (j = 0; j < 21; ++j) {
// If current bit is set
if (binary[j] > 0) {
total += Math.pow(2, j);
binary[j]--;
}
}
// Square the constructed number
ans += total * total;
}
// Return the answer
document.write(ans);
}
// Driver Code
// Given array arr[]
var arr = [8, 9, 9, 1];
var N = arr.length;
// Function call
findMaximumSum(arr, N);
</script>
Producción
243
Complejidad temporal: O(N log 2 A), donde A es el elemento máximo del arreglo.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por greenindia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA