Given an array arr[] consisting of N integers and a positive integer K, the task is to find all permutations of the array arr[] such that the sum of Bitwise AND of adjacent elements in each permutation is greater than or equal to K. If no such permutation exists, print “-1”.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}, K = 8
Output:
2, 3, 1, 5, 4
4, 5, 1, 3, 2
Explanation:
For the permutation {2, 3, 1, 5, 4}: (2 & 3) + (3 & 1) + (1 & 5) + (5 & 4) = 8, which is at least K( = 8).
For the permutation {4, 5, 1, 3, 2}: (4 & 5) + (5 & 1) + (1 & 3) + (3 & 2) = 8, which is at least K( = 8).Input: arr[] = {1, 2, 3}, K = 4
Output: -1
Approach: The idea is to generate all possible permutations of arr[] and check for each permutation, if the required condition is satisfied or not.
Follow the steps below to solve the problem:
- Initialize a boolean variable, say flag as false, to check if any required permutation exists or not.
- Generate all possible permutations of the array arr[] and perform the following steps:
- Calculate the sum of Bitwise AND of all adjacent pairs of array elements in the current permutation and store t in a variable, say sum.
- Traverse the current permutation over the range [0, N – 2] and add Bitwise AND of arr[i] and arr[i + 1] to the sum.
- If the value of sum is at least K, then set the flag to true and print the current permutation.
- After completing the above steps, If the value of flag is false, the print “-1”.
Below is the implementation of the above approach:
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 Kvoid 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 Codeint 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 approachimport 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 approachusing 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 approachdef 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 Kdef 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 Codearr = [1, 2, 3, 4, 5]K = 8N = len(arr)# Function CallprintPermutation(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> |
Output:
2 3 1 5 4 4 5 1 3 2
Time Complexity: O(N*(N!))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
