Dada una array arr[] que consiste en N enteros y un entero positivo K , la tarea es encontrar todas las permutaciones de la array arr[] tales que la suma de Bitwise AND de elementos adyacentes en cada permutación sea mayor o igual que K . Si no existe tal permutación, imprima “-1” .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}, K = 8
Salida:
2, 3, 1, 5, 4
4, 5, 1, 3, 2
Explicación:
Para la permutación {2, 3 , 1, 5, 4}: (2 y 3) + (3 y 1) + (1 y 5) + (5 y 4) = 8, que es al menos K( = 8).
Para la permutación {4, 5, 1, 3, 2}: (4 y 5) + (5 y 1) + (1 y 3) + (3 y 2) = 8, que es al menos K( = 8) .Entrada: arr[] = {1, 2, 3}, K = 4
Salida: -1
Enfoque: La idea es generar todas las permutaciones posibles de arr[] y verificar para cada permutación, si la condición requerida se cumple o no.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable booleana, diga marcar como falsa , para verificar si existe alguna permutación requerida o no.
- Genere todas las permutaciones posibles de la array arr[] y realice los siguientes pasos:
- Calcule la suma de Bitwise AND de todos los pares adyacentes de elementos de array en la permutación actual y almacene t en una variable, digamos sum .
- Atraviese la permutación actual en el rango [0, N – 2] y agregue Bitwise AND de arr[i] y arr[i + 1] a la suma .
- Si el valor de sum es al menos K , establezca el indicador en verdadero e imprima la permutación actual.
- Después de completar los pasos anteriores, si el valor de la bandera es falso , se imprime «-1» .
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 print all permutations of
// arr[] such that the sum of Bitwise AND
// of all adjacent element is at least K
void printPermutation(int arr[], int n,
int k)
{
// To check if any permutation
// exists or not
bool flag = false;
// Sort the given array
sort(arr, arr + n);
// Find all possible permutations
do {
// Stores the sum of bitwise AND
// of adjacent elements of the
// current permutation
int sum = 0;
// Traverse the current
// permutation of arr[]
for (int i = 0; i < n - 1; i++) {
// Update the sum
sum += arr[i] & arr[i + 1];
}
// If the sum is at least K, then
// print the current permutation
if (sum >= k) {
// Set the flag variable
flag = true;
// Print the current permutation
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
} while (next_permutation(arr, arr + n));
// If flag is unset, then print -1
if (flag == false) {
cout << "-1";
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int K = 8;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
printPermutation(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print all permutations of
// arr[] such that the sum of Bitwise AND
// of all adjacent element is at least K
static void printPermutation(int arr[], int n,
int k)
{
// To check if any permutation
// exists or not
boolean flag = false;
// Sort the given array
Arrays.sort(arr);
// Find all possible permutations
do
{
// Stores the sum of bitwise AND
// of adjacent elements of the
// current permutation
int sum = 0;
// Traverse the current
// permutation of arr[]
for (int i = 0; i < n - 1; i++)
{
// Update the sum
sum += arr[i] & arr[i + 1];
}
// If the sum is at least K, then
// print the current permutation
if (sum >= k)
{
// Set the flag variable
flag = true;
// Print the current permutation
for (int i = 0; i < n; i++)
{
System.out.print(arr[i]+ " ");
}
System.out.print("\n");
}
} while (next_permutation(arr));
// If flag is unset, then print -1
if (flag == false)
{
System.out.print("-1");
}
}
static boolean next_permutation(int[] p) {
for (int a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.length - 1;; --b)
if (p[b] > p[a]) {
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int K = 8;
int N = arr.length;
// Function Call
printPermutation(arr, N, K);
}
}
// This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
class GFG{
// Function to print all permutations of
// []arr such that the sum of Bitwise AND
// of all adjacent element is at least K
static void printPermutation(int []arr, int n,
int k)
{
// To check if any permutation
// exists or not
bool flag = false;
// Sort the given array
Array.Sort(arr);
// Find all possible permutations
do
{
// Stores the sum of bitwise AND
// of adjacent elements of the
// current permutation
int sum = 0;
// Traverse the current
// permutation of []arr
for (int i = 0; i < n - 1; i++)
{
// Update the sum
sum += arr[i] & arr[i + 1];
}
// If the sum is at least K, then
// print the current permutation
if (sum >= k)
{
// Set the flag variable
flag = true;
// Print the current permutation
for (int i = 0; i < n; i++)
{
Console.Write(arr[i] + " ");
}
Console.Write("\n");
}
} while (next_permutation(arr));
// If flag is unset, then print -1
if (flag == false)
{
Console.Write("-1");
}
}
static bool next_permutation(int[] p) {
for (int a = p.Length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.Length - 1;; --b)
if (p[b] > p[a]) {
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.Length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 5 };
int K = 8;
int N = arr.Length;
// Function Call
printPermutation(arr, N, K);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach
def next_permutation(a):
for i in reversed(range(len(a) - 1)):
if a[i] < a[i + 1]:
break
else:
return False
j = next(j for j in
reversed(range(i + 1, len(a)))
if a[i] < a[j])
a[i], a[j] = a[j], a[i]
a[i + 1:] = reversed(a[i + 1:])
return True
# Function to print all permutations of
# arr[] such that the sum of Bitwise AND
# of all adjacent element is at least K
def printPermutation(arr, n, k):
# To check if any permutation
# exists or not
flag = False
# Sort the given array
arr.sort()
# Find all possible permutations
while True:
# Stores the sum of bitwise AND
# of adjacent elements of the
# current permutation
sum = 0
# Traverse the current
# permutation of arr[]
for i in range(n - 1):
# Update the sum
sum += arr[i] & arr[i + 1]
# If the sum is at least K, then
# print the current permutation
if (sum >= k):
# Set the flag variable
flag = True
# Print the current permutation
for i in range(n):
print(arr[i], end = " ")
print()
if (next_permutation(arr) == False):
break
# If flag is unset, then print -1
if (flag == False):
print("-1")
# Driver Code
arr = [1, 2, 3, 4, 5]
K = 8
N = len(arr)
# Function Call
printPermutation(arr, N, K)
# This code is contributed by Dharanendra L V
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to print all permutations of
// arr[] such that the sum of Bitwise AND
// of all adjacent element is at least K
function printPermutation(arr, n, k)
{
// To check if any permutation
// exists or not
let flag = false;
// Sort the given array
arr.sort();
// Find all possible permutations
do
{
// Stores the sum of bitwise AND
// of adjacent elements of the
// current permutation
let sum = 0;
// Traverse the current
// permutation of arr[]
for (let i = 0; i < n - 1; i++)
{
// Update the sum
sum += arr[i] & arr[i + 1];
}
// If the sum is at least K, then
// print the current permutation
if (sum >= k)
{
// Set the flag variable
flag = true;
// Print the current permutation
for (let i = 0; i < n; i++)
{
document.write(arr[i]+ " ");
}
document.write("<br/>");
}
} while (next_permutation(arr));
// If flag is unset, then print -1
if (flag == false)
{
System.out.print("-1");
}
}
function next_permutation(p) {
for (let a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (let b = p.length - 1;; --b)
if (p[b] > p[a]) {
let t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver code
let arr = [ 1, 2, 3, 4, 5 ];
let K = 8;
let N = arr.length;
// Function Call
printPermutation(arr, N, K);
</script>
Producción:
2 3 1 5 4 4 5 1 3 2
Complejidad de tiempo: O(N*(N!))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pushpendrayadav1057 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA