Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la suma máxima de Bitwise AND de elementos de permutación del mismo índice de los primeros N números naturales y la array arr[] .
Ejemplos:
Entrada: arr[] = {4, 2, 3, 6}
Salida: 5
Explicación: Considere la permutación {1, 0, 3, 2}. Suma de Bitwise AND de la permutación anterior y la array dada = 1 & 4 + 0 & 2 + 3 & 3 + 2 & 6 = 0 + 0 + 3 + 2 = 5, que es el máximo entre todas las permutaciones.Entrada: arr[] = {3, 4, 1, 0, 5}
Salida: 8
Enfoque: La idea para resolver el problema dado es generar todas las permutaciones de los primeros N números naturales y calcular la suma de Bitwise AND de la permutación generada con la array arr[] . Después de verificar cada permutación, imprima el valor máximo de la suma de Bitwise AND obtenido.
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 calculate sum of
// Bitwise AND of same indexed
// elements of the arrays p[] and arr[]
int calcScore(vector<int> p, int arr[], int N)
{
// Stores the resultant sum
int ans = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update sum of Bitwise AND
ans += (p[i] & arr[i]);
}
// Return the value obtained
return ans;
}
// Function to generate all permutations
// and calculate the maximum sum of Bitwise
// AND of same indexed elements present in
// any permutation and an array arr[]
int getMaxUtil(vector<int> p, int arr[], int ans,
bool chosen[], int N)
{
// If the size of the array is N
if (p.size() == N) {
// Calculate cost of permutation
ans = max(ans, calcScore(p, arr, N));
return ans;
}
// Generate all permutations
for (int i = 0; i < N; i++) {
if (chosen[i]) {
continue;
}
// Update chosen[i]
chosen[i] = true;
// Update the permutation p[]
p.push_back(i);
// Generate remaining permutations
ans = getMaxUtil(p, arr, ans, chosen, N);
chosen[i] = false;
p.pop_back();
}
// Return the resultant sum
return ans;
}
// Function to find the maximum sum of Bitwise
// AND of same indexed elements in a permutation
// of first N natural numbers and arr[]
void getMax(int arr[], int N)
{
// Stores the resultant maximum sum
int ans = 0;
bool chosen[N];
for (int i = 0; i < N; i++)
chosen[i] = false;
// Stores the generated permutation P
vector<int> p;
// Function call to store result
int res = getMaxUtil(p, arr, ans, chosen, N);
// Print the result
cout << res;
}
// Driven Program
int main()
{
int arr[] = { 4, 2, 3, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
getMax(arr, N);
return 0;
}
// This code is contributed by Kingash.
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to calculate sum of
// Bitwise AND of same indexed
// elements of the arrays p[] and arr[]
static int calcScore(ArrayList<Integer> p, int arr[])
{
// Stores the resultant sum
int ans = 0;
// Traverse the array
for (int i = 0; i < arr.length; i++) {
// Update sum of Bitwise AND
ans += (p.get(i) & arr[i]);
}
// Return the value obtained
return ans;
}
// Function to generate all permutations
// and calculate the maximum sum of Bitwise
// AND of same indexed elements present in
// any permutation and an array arr[]
static int getMaxUtil(ArrayList<Integer> p, int arr[],
int ans, boolean chosen[], int N)
{
// If the size of the array is N
if (p.size() == N) {
// Calculate cost of permutation
ans = Math.max(ans, calcScore(p, arr));
return ans;
}
// Generate all permutations
for (int i = 0; i < N; i++) {
if (chosen[i]) {
continue;
}
// Update chosen[i]
chosen[i] = true;
// Update the permutation p[]
p.add(i);
// Generate remaining permutations
ans = getMaxUtil(p, arr, ans, chosen, N);
chosen[i] = false;
p.remove(p.size() - 1);
}
// Return the resultant sum
return ans;
}
// Function to find the maximum sum of Bitwise
// AND of same indexed elements in a permutation
// of first N natural numbers and arr[]
static void getMax(int arr[], int N)
{
// Stores the resultant maximum sum
int ans = 0;
boolean chosen[] = new boolean[N];
// Stores the generated permutation P
ArrayList<Integer> p = new ArrayList<>();
// Function call to store result
int res = getMaxUtil(p, arr, ans, chosen, N);
// Print the result
System.out.println(res);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, 2, 3, 6 };
int N = arr.length;
// Function Call
getMax(arr, N);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to calculate sum of # Bitwise AND of same indexed # elements of the arrays p[] and arr[] def calcScore(p, arr): # Stores the resultant sum ans = 0 # Traverse the array for i in range(len(arr)): # Update sum of Bitwise AND ans += (p[i] & arr[i]) # Return the value obtained return ans # Function to generate all permutations # and calculate the maximum sum of Bitwise # AND of same indexed elements present in # any permutation and an array arr[] def getMaxUtil(p, arr, ans, chosen, N): # If the size of the array is N if len(p) == N: # Calculate cost of permutation ans = max(ans, calcScore(p, arr)) return ans # Generate all permutations for i in range(N): if chosen[i]: continue # Update chosen[i] chosen[i] = True # Update the permutation p[] p.append(i) # Generate remaining permutations ans = getMaxUtil(p, arr, ans, chosen, N) chosen[i] = False p.pop() # Return the resultant sum return ans # Function to find the maximum sum of Bitwise # AND of same indexed elements in a permutation # of first N natural numbers and arr[] def getMax(arr, N): # Stores the resultant maximum sum ans = 0 chosen = [False for i in range(N)] # Stores the generated permutation P p = [] # Function call to store result res = getMaxUtil(p, arr, ans, chosen, N) # Print the result print(res) # Driver Code if __name__ == '__main__': # Given array arr = [4, 2, 3, 6] N = len(arr) # Function Call getMax(arr, N)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate sum of
// Bitwise AND of same indexed
// elements of the arrays p[] and arr[]
static int calcScore(List<int> p, int[] arr)
{
// Stores the resultant sum
int ans = 0;
// Traverse the array
for(int i = 0; i < arr.Length; i++)
{
// Update sum of Bitwise AND
ans += (p[i] & arr[i]);
}
// Return the value obtained
return ans;
}
// Function to generate all permutations
// and calculate the maximum sum of Bitwise
// AND of same indexed elements present in
// any permutation and an array arr[]
static int getMaxUtil(List<int> p, int[] arr,
int ans, bool[] chosen,
int N)
{
// If the size of the array is N
if (p.Count == N)
{
// Calculate cost of permutation
ans = Math.Max(ans, calcScore(p, arr));
return ans;
}
// Generate all permutations
for(int i = 0; i < N; i++)
{
if (chosen[i])
{
continue;
}
// Update chosen[i]
chosen[i] = true;
// Update the permutation p[]
p.Add(i);
// Generate remaining permutations
ans = getMaxUtil(p, arr, ans, chosen, N);
chosen[i] = false;
p.Remove(p.Count - 1);
}
// Return the resultant sum
return ans;
}
// Function to find the maximum sum of Bitwise
// AND of same indexed elements in a permutation
// of first N natural numbers and arr[]
static void getMax(int[] arr, int N)
{
// Stores the resultant maximum sum
int ans = 0;
bool[] chosen = new bool[N];
// Stores the generated permutation P
List<int> p = new List<int>();
// Function call to store result
int res = getMaxUtil(p, arr, ans, chosen, N);
// Print the result
Console.Write(res);
}
// Driver Code
public static void Main()
{
int[] arr = { 4, 2, 3, 6 };
int N = arr.Length;
// Function Call
getMax(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to calculate sum of
// Bitwise AND of same indexed
// elements of the arrays p[] and arr[]
function calcScore(p, arr, N)
{
// Stores the resultant sum
var ans = 0;
// Traverse the array
for (var i = 0; i < N; i++) {
// Update sum of Bitwise AND
ans += (p[i] & arr[i]);
}
// Return the value obtained
return ans;
}
// Function to generate all permutations
// and calculate the maximum sum of Bitwise
// AND of same indexed elements present in
// any permutation and an array arr[]
function getMaxUtil(p, arr, ans, chosen, N)
{
// If the size of the array is N
if (p.length == N) {
// Calculate cost of permutation
ans = Math.max(ans, calcScore(p, arr, N));
return ans;
}
// Generate all permutations
for (var i = 0; i < N; i++) {
if (chosen[i]) {
continue;
}
// Update chosen[i]
chosen[i] = true;
// Update the permutation p[]
p.push(i);
// Generate remaining permutations
ans = getMaxUtil(p, arr, ans, chosen, N);
chosen[i] = false;
p.pop();
}
// Return the resultant sum
return ans;
}
// Function to find the maximum sum of Bitwise
// AND of same indexed elements in a permutation
// of first N natural numbers and arr[]
function getMax(arr, N)
{
// Stores the resultant maximum sum
var ans = 0;
var chosen = Array(N).fill(false);
// Stores the generated permutation P
var p = [];
// Function call to store result
var res = getMaxUtil(p, arr, ans, chosen, N);
// Print the result
document.write( res);
}
// Driven Program
var arr = [ 4, 2, 3, 6 ];
var N = arr.length;
// Function call
getMax(arr, N);
</script>
Producción:
5
Complejidad temporal: O(N*N!)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA