Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la máxima diferencia absoluta entre la suma de los elementos de la array colocados en índices pares y aquellos en índices impares de la array rotando sus representaciones binarias cualquier número de veces. Considere solo la representación de 8 bits .
Ejemplos:
Entrada: arr[] = {123, 86, 234, 189}
Salida: 326
Explicación:
La siguiente es la rotación de elementos:
- Para arr[0] (= 123): arr[0] = (123) 10 = (1111011) 2 . Gira los bits a la derecha dos veces para hacer arr[0] = (1111100) 2 = (246) 10 .
- Para arr[1] (= 86): arr[1] = (86) 10 = (1010110) 2 . Gire los bits a la derecha una vez para hacer arr[1] = (0101011) 2 = (43) 10 .
- Para el elemento arr[3](=189): arr[3] = (189) 10 = (10111101) 2 . Gire los bits una vez hacia la izquierda para formar arr[3] = (011111011) 2 = (111) 10 .
Por lo tanto, la array arr[] se modifica a {246, 43, 234, 111}. La máxima diferencia absoluta = (246 + 234) – (43 + 111) = 326.
Entrada: arr[] = {211, 122, 212, 222}, N = 4
Salida: 376
Enfoque: el problema dado se puede resolver minimizando elementos en índices pares o impares y maximizando elementos en otros índices al rotar la representación binaria de cada elemento del arreglo y encontrar la diferencia máxima. Siga los pasos a continuación para resolver el problema:
- Defina una función, digamos Rotar (X, f) para encontrar el valor máximo y mínimo de un número posible después de rotar los bits en la representación binaria de cualquier número.
- Inicialice dos variables, digamos maxi = X y mini = X para almacenar el valor máximo y mínimo del número X posible.
- Iterar sobre los bits del número X y luego rotar los bits de X realizando lo siguiente:
- Si X es impar , actualice el valor de X como X >> 1 y X = X | (1<<7) .
- De lo contrario, actualice el valor de X como X >> 1 .
- Actualice el valor de maxi como el máximo de maxi y X .
- Actualice el valor de mini como el mínimo de mini y X .
- Si el valor de f es 1 , devuelve maxi . De lo contrario, devuelve mini.
- Ahora, encuentre la diferencia obtenida al maximizar el elemento colocado en índices pares y minimizando los elementos colocados en índices impares y almacene esa diferencia en una variable, digamos caseOne .
- Ahora, encuentre la diferencia obtenida al minimizar el elemento colocado en índices pares y maximizando los elementos colocados en índices impares y almacene esa diferencia en una variable, digamos caseTwo .
- Después de completar los pasos anteriores, imprima el máximo de caseOne y caseTwo como resultado.
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;
// Function to find maximum and
// minimum value of a number that
// can be obtained by rotating bits
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 & 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 bits
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)
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 Code
int 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 approach
import java.util.*;
class GFG
{
// Function to find maximum and
// minimum value of a number that
// can be obtained by rotating bits
static 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 bits
static 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;
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 bits def 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 bits def 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 Code arr = [123, 86, 234, 189] print(calcMinDiff(arr))
C#
// C# program for the above approach
using System;
public class GFG {
// Function to find maximum and
// minimum value of a number that
// can be obtained by rotating bits
static 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 bits
static 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 bits
function 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 bits
function 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>
Producción:
326
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA