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:

  1. 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 .
  2. 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 .
  3. 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>
Saída: 
326

 

Complexidade de tempo: O (N)
Espaço auxiliar: O (1)