Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la diferencia absoluta máxima entre la suma de los elementos de la array colocados en los índices pares e impares de la array intercambiando bits adyacentes desiguales en la representación binaria de cualquier array elemento cualquier número de veces.
Ejemplos:
Entrada: arr[]={5, 7, 3, 1, 8}
Salida: 9
Explicación:
arr[0] = (5) 10 = (101) 2 . Bits de desplazamiento a la izquierda para hacer arr[0] = (110) 2 = (6) 10 .
Por lo tanto, la array arr[] se modifica a {5, 7, 3, 1, 8}.
Por lo tanto, la máxima diferencia absoluta = (6 + 3 + 8) – (7 + 1) = 9.Entrada: arr[] = {54, 32, 11, 23}
Salida: 58
Explicación:
Modifique arr[0] a 60 desplazando a la izquierda los dos últimos bits establecidos de arr[0] (= 54). Por lo tanto, la array arr[] se modifica a {60, 32, 11, 23}.
Modifique arr[1] a 1 desplazando a la derecha todos los bits establecidos de arr[1] (= 32). Por lo tanto, la array arr[] se modifica a {60, 1, 11, 23}
Modifique arr[2] a 14 desplazando a la izquierda los últimos tres bits establecidos de arr[2] (= 11). Por lo tanto, la array arr[] se modifica a {60, 1, 14, 23}.
Modifique arr[3] a 15 desplazando a la derecha todos los bits establecidos de arr[3] (= 23). Por lo tanto, la array arr[] se modifica a {60, 1, 14, 15}.
Por lo tanto, la máxima diferencia absoluta = (60 + 14) – (15 + 1) = 58.
Enfoque: la idea es usar la observación de que cualquier bit establecido se puede mover a cualquier otra posición. Siga los pasos a continuación para resolver el problema:
- Defina una función, digamos maximizar() , para maximizar un número desplazando dos bits adyacentes desiguales.
- Defina una función, digamos minimizar() , para minimizar un número desplazando dos bits adyacentes desiguales.
- Realice las siguientes operaciones:
- Inicialice una variable, digamos ans , para almacenar el valor minimizado.
- Para minimizar un número, cambie todos los bits establecidos a la posición derecha y todos los bits no establecidos a la posición izquierda.
- Recorra el rango [0, conteo del bit establecido – 1] y actualice ans como ans | 1 . Si i no es igual al conteo de bits establecidos , entonces se desplaza a la izquierda en 1 .
- Devuelve el valor de ans .
- Primero, encuentre la diferencia obtenida al maximizar el elemento colocado en índices pares y minimizando los elementos colocados en índices impares. Guárdelo 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. Almacénelo en una variable, digamos caseTwo .
- Después de completar los pasos anteriores, imprima el máximo de caseOne y CaseTwo .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to count total number
// of bits present in a number
int countBit(int n){
return int(log2(n))+1;
}
// Function to count total
// set bits in a number
int countSetBit(int n){
// Stores the count
// of set bits
int ans = 0;
while(n > 0){
ans += (n & 1);
// Right shift by 1
n >>= 1;
}
// Return the final count
return ans;
}
// Function to find maximum number
// by shifting two unequal bits
int maximize(int n){
// Count set bits in number n
int bits = countBit(n);
int setBits = countSetBit(n);
int ans = 0;
// Iterate the string bits
for(int i = 0; i < bits; i++){
if (i < setBits)
ans |= 1;
if(i != setBits - 1)
ans <<= 1;
}
return ans;
}
// Function to find minimum number
// by shifting two unequal bits
int minimize(int n){
int setBits = countSetBit(n);
int ans = 0;
// Iterate the set bit
for (int i = 0; i < setBits; i++){
ans |= 1;
if (i != setBits - 1)
ans <<= 1;
}
return ans;
}
// Function to find the maximum difference
int maxDiff(vector<int> arr){
// Stores the maximum difference
int caseOne = 0;
// Stores the sum of elements
// placed at odd positions
int SumOfOdd = 0;
// Stores the sum of elements
// placed at even positions
int SumOfeven = 0;
// Traverse the array
for(int i = 0; i < arr.size(); i++){
if (i % 2)
SumOfOdd += minimize(arr[i]);
else
SumOfeven += maximize(arr[i]);
}
// Update CaseOne
caseOne = abs(SumOfOdd - SumOfeven);
// Stores the maximum difference
int caseTwo = 0;
// Assign value O
SumOfOdd = 0;
SumOfeven = 0;
// Traverse the array
for(int i = 0; i < arr.size(); i++)
{
if (i % 2)
SumOfOdd += maximize(arr[i]);
else
SumOfeven += minimize(arr[i]);
}
// Update caseTwo
caseTwo = abs(SumOfOdd - SumOfeven);
// Return maximum of caseOne and CaseTwo
return max(caseOne, caseTwo);
}
// Drivers Code
int main()
{
vector<int> arr{54, 32, 11, 23};
// Function Call
cout<<maxDiff(arr);
}
// This code is contributed by ipg2016107.
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count total number
// of bits present in a number
static int countBit(int n){
return (int)((Math.log(n) / Math.log(2))+1);
}
// Function to count total
// set bits in a number
static int countSetBit(int n){
// Stores the count
// of set bits
int ans = 0;
while(n > 0){
ans += (n & 1);
// Right shift by 1
n >>= 1;
}
// Return the final count
return ans;
}
// Function to find maximum number
// by shifting two unequal bits
static int maximize(int n){
// Count set bits in number n
int bits = countBit(n);
int setBits = countSetBit(n);
int ans = 0;
// Iterate the string bits
for(int i = 0; i < bits; i++){
if (i < setBits)
ans |= 1;
if(i != setBits - 1)
ans <<= 1;
}
return ans;
}
// Function to find minimum number
// by shifting two unequal bits
static int minimize(int n){
int setBits = countSetBit(n);
int ans = 0;
// Iterate the set bit
for (int i = 0; i < setBits; i++){
ans |= 1;
if (i != setBits - 1)
ans <<= 1;
}
return ans;
}
// Function to find the maximum difference
static int maxDiff(int[] arr){
// Stores the maximum difference
int caseOne = 0;
// Stores the sum of elements
// placed at odd positions
int SumOfOdd = 0;
// Stores the sum of elements
// placed at even positions
int SumOfeven = 0;
// Traverse the array
for(int i = 0; i < arr.length; i++){
if ((i % 2) != 0)
SumOfOdd += minimize(arr[i]);
else
SumOfeven += maximize(arr[i]);
}
// Update CaseOne
caseOne = Math.abs(SumOfOdd - SumOfeven);
// Stores the maximum difference
int caseTwo = 0;
// Assign value O
SumOfOdd = 0;
SumOfeven = 0;
// Traverse the array
for(int i = 0; i < arr.length; i++)
{
if ((i % 2) != 0)
SumOfOdd += maximize(arr[i]);
else
SumOfeven += minimize(arr[i]);
}
// Update caseTwo
caseTwo = Math.abs(SumOfOdd - SumOfeven);
// Return maximum of caseOne and CaseTwo
return Math.max(caseOne, caseTwo);
}
// Driver code
public static void main(String[] args)
{
int[] arr = {54, 32, 11, 23};
// Function Call
System.out.println(maxDiff(arr));
}
}
// This code is contributed by souravghosh0416.
Python3
# Python program for the above approach import math # Function to count total number # of bits present in a number def countBit(n): return int(math.log(n, 2))+1 # Function to count total # set bits in a number def countSetBit(n): # Stores the count # of set bits ans = 0 while n: ans += n & 1 # Right shift by 1 n >>= 1 # Return the final count return ans # Function to find maximum number # by shifting two unequal bits def maximize(n): # Count set bits in number n bits = countBit(n) setBits = countSetBit(n) ans = 0 # Iterate the string bits for i in range(bits): if i < setBits: ans |= 1 if i != setBits - 1: ans <<= 1 return ans # Function to find minimum number # by shifting two unequal bits def minimize(n): setBits = countSetBit(n) ans = 0 # Iterate the set bit for i in range(setBits): ans |= 1 if i != setBits-1: ans <<= 1 return ans # Function to find the maximum difference def maxDiff(arr): # Stores the maximum difference caseOne = 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 i % 2: SumOfOdd += minimize(arr[i]) else: SumOfeven += maximize(arr[i]) # Update CaseOne caseOne = abs(SumOfOdd - SumOfeven) # Stores the maximum difference caseTwo = 0 # Assign value O SumOfOdd = 0 SumOfeven = 0 # Traverse the array for i in range(len(arr)): if i % 2: SumOfOdd += maximize(arr[i]) else: SumOfeven += minimize(arr[i]) # Update caseTwo caseTwo = abs(SumOfOdd - SumOfeven) # Return maximum of caseOne and CaseTwo return max(caseOne, caseTwo) # Drivers Code arr = [54, 32, 11, 23] # Function Call print(maxDiff(arr))
C#
// C# program for the above approach
using System;
class GFG{
// Function to count total number
// of bits present in a number
static int countBit(int n){
return (int)((Math.Log(n) / Math.Log(2))+1);
}
// Function to count total
// set bits in a number
static int countSetBit(int n){
// Stores the count
// of set bits
int ans = 0;
while(n > 0){
ans += (n & 1);
// Right shift by 1
n >>= 1;
}
// Return the final count
return ans;
}
// Function to find maximum number
// by shifting two unequal bits
static int maximize(int n){
// Count set bits in number n
int bits = countBit(n);
int setBits = countSetBit(n);
int ans = 0;
// Iterate the string bits
for(int i = 0; i < bits; i++){
if (i < setBits)
ans |= 1;
if(i != setBits - 1)
ans <<= 1;
}
return ans;
}
// Function to find minimum number
// by shifting two unequal bits
static int minimize(int n){
int setBits = countSetBit(n);
int ans = 0;
// Iterate the set bit
for (int i = 0; i < setBits; i++){
ans |= 1;
if (i != setBits - 1)
ans <<= 1;
}
return ans;
}
// Function to find the maximum difference
static int maxDiff(int[] arr){
// Stores the maximum difference
int caseOne = 0;
// Stores the sum of elements
// placed at odd positions
int SumOfOdd = 0;
// Stores the sum of elements
// placed at even positions
int SumOfeven = 0;
// Traverse the array
for(int i = 0; i < arr.Length; i++){
if ((i % 2) != 0)
SumOfOdd += minimize(arr[i]);
else
SumOfeven += maximize(arr[i]);
}
// Update CaseOne
caseOne = Math.Abs(SumOfOdd - SumOfeven);
// Stores the maximum difference
int caseTwo = 0;
// Assign value O
SumOfOdd = 0;
SumOfeven = 0;
// Traverse the array
for(int i = 0; i < arr.Length; i++)
{
if ((i % 2) != 0)
SumOfOdd += maximize(arr[i]);
else
SumOfeven += minimize(arr[i]);
}
// Update caseTwo
caseTwo = Math.Abs(SumOfOdd - SumOfeven);
// Return maximum of caseOne and CaseTwo
return Math.Max(caseOne, caseTwo);
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = {54, 32, 11, 23};
// Function Call
Console.Write(maxDiff(arr));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// Javascript program for the above approach
// Function to count total number
// of bits present in a number
function countBit(n){
return parseInt(log2(n))+1;
}
// Function to count total
// set bits in a number
function countSetBit(n){
// Stores the count
// of set bits
let ans = 0;
while(n > 0){
ans += (n & 1);
// Right shift by 1
n >>= 1;
}
// Return the final count
return ans;
}
// Function to find maximum number
// by shifting two unequal bits
function maximize(n){
// Count set bits in number n
let bits = countBit(n);
let setBits = countSetBit(n);
let ans = 0;
// Iterate the string bits
for(let i = 0; i < bits; i++){
if (i < setBits)
ans |= 1;
if(i != setBits - 1)
ans <<= 1;
}
return ans;
}
// Function to find minimum number
// by shifting two unequal bits
function minimize(n){
let setBits = countSetBit(n);
let ans = 0;
// Iterate the set bit
for (let i = 0; i < setBits; i++){
ans |= 1;
if (i != setBits - 1)
ans <<= 1;
}
return ans;
}
// Function to find the maximum difference
function maxDiff(arr){
// Stores the maximum difference
let caseOne = 0;
// Stores the sum of elements
// placed at odd positions
let SumOfOdd = 0;
// Stores the sum of elements
// placed at even positions
let SumOfeven = 0;
// Traverse the array
for(let i = 0; i < arr.length; i++){
if (i % 2)
SumOfOdd += minimize(arr[i]);
else
SumOfeven += maximize(arr[i]);
}
// Update CaseOne
caseOne = Math.abs(SumOfOdd - SumOfeven);
// Stores the maximum difference
let caseTwo = 0;
// Assign value O
SumOfOdd = 0;
SumOfeven = 0;
// Traverse the array
for(let i = 0; i < arr.length; i++)
{
if (i % 2)
SumOfOdd += maximize(arr[i]);
else
SumOfeven += minimize(arr[i]);
}
// Update caseTwo
caseTwo = Math.abs(SumOfOdd - SumOfeven);
// Return maximum of caseOne and CaseTwo
return Math.max(caseOne, caseTwo);
}
// Drivers Code
let arr = [54, 32, 11, 23];
// Function Call
document.write(maxDiff(arr));
// This code is contributed by rishavmahato348.
</script>
Producción:
58
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