Maximize a diferença entre os elementos da array com índice ímpar e par girando suas representações binárias
Dado um array arr [] consistindo em N inteiros positivos, a tarefa é encontrar a diferença absoluta máxima entre a soma dos elementos do array colocados em índices pares e aqueles em índices ímpares do array girando suas representações binárias qualquer número de vezes. Considere apenas a representação de 8 bits .
Exemplos:
Entrada: arr [] = {123, 86, 234, 189}
Saída: 326
Explicação: A
seguir estão a rotação dos elementos:
- Para arr [0] (= 123): arr [0] = (123) 10 = (1111011) 2 . Gire os bits para a direita duas vezes para fazer arr [0] = (1111100) 2 = (246) 10 .
- Para arr [1] (= 86): arr [1] = (86) 10 = (1010110) 2 . Gire os bits para a direita uma vez para fazer arr [1] = (0101011) 2 = (43) 10 .
- Para o elemento arr [3] (= 189): arr [3] = (189) 10 = (10111101) 2 . Gire os bits uma vez para a esquerda para fazer arr [3] = (011111011) 2 = (111) 10 .
Portanto, a array arr [] é modificada para {246, 43, 234, 111}. A diferença absoluta máxima = (246 + 234) - (43 + 111) = 326.
Entrada: arr [] = {211, 122, 212, 222}, N = 4
Saída: 376
Abordagem: O problema dado pode ser resolvido minimizando elementos em índices pares ou ímpares e maximizando elementos em outros índices girando a representação binária de cada elemento da array e encontrando a diferença máxima. Siga as etapas abaixo para resolver o problema:
- Definir uma função digamos Rodar (X, f) para encontrar o máximo e o valor mínimo de um número possível depois de rodar os bits na representação binária de qualquer número.
- Inicialize duas variáveis, digamos maxi = X e mini = X para armazenar o valor máximo e mínimo do número X possível.
- Repita os bits do número X e gire os bits de X executando o seguinte:
- Se X for ímpar , atualize o valor de X como X >> 1 e X = X | (1 << 7) .
- Caso contrário, atualize o valor de X como X >> 1 .
- Atualize o valor da maxi como o máximo de maxi e X .
- Atualize o valor da mini- como o mínimo de mini- e X .
- Se o valor de f for 1 , retorne maxi . Caso contrário, devolva mini.
- Agora, encontre a diferença obtida maximizando o elemento colocado em índices pares e minimizando os elementos colocados em índices ímpares e armazene essa diferença em uma variável, digamos caseOne .
- Agora, encontre a diferença obtida minimizando o elemento colocado em índices pares e maximizando os elementos colocados em índices ímpares e armazene essa diferença em uma variável, digamos caseTwo .
- Depois de concluir as etapas acima, imprima o máximo de caseOne e caseTwo como resultado.
Abaixo está a implementação da abordagem acima:
// 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 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.
# 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# 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.
<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>
326
Complexidade de tempo: O (N)
Espaço auxiliar: O (1)
Aprendendo inglês e usando o Anki? Use o Faluchu e esqueça os cartões. É gratis!
Usar o Faluchu