Check if there exists a subsequence such that its cumulative AND is equal to X
Given an array A[] of length N along with an integer X. Then the task is to output the subsequence such that the cumulative AND of all elements that are present in the subsequence is equal to X. If such a subsequence is present, then print it else print -1.
Examples:
Input: N = 3, A[] = {67, 44, 23}, X = 7
Output: -1
Explanation: It can be verified that no such subsequence exists such that the bitwise AND of that subsequence is equal to 7. Therefore, output is -1.Input: N = 5, A[] = {2, 8, 5, 4, 3}, X = 1
Output: {5, 3}
Explanation: The bitwise AND of 5 and 3 is 1.
Approach: To solve the problem follow the below idea:
The idea for the solving the problem is: Bitwise AND equal to X can be made only and only by those elements in which set bits are same as which are present in X. So, the simple intuition comes that, iterate over the given array A[] and collect all the elements of A[] into a list such that Bitwise AND of element with X is equal to X. After that find cumulative Bitwise AND of all elements present in list, If it is equal to X then output elements present in list else -1.
Steps were taken to solve the problem:
- Iterating over array
- If element & X == X (all bits which are set in X are also set in element(A[i])) Then add it to the list
- If there is no element in the list Output -1
- Else check that, the cumulative AND of All elements present in the list is equal to X
- If yes then output list elements else -1
Below is the code to implement the approach:
C++
#include <iostream> #include <vector> using namespace std; // Function to check if such a subsequence exists or not void AND_Subsequence( int N, vector< int >& A, int X) { // Vector to store relevant elements, which can possibly make cumulative AND as X vector< int > list; // Iterating over the array for ( int element : A) { // If element & X == X (all bits which are set in X are also set in element(A[i])) // Then add it into the list if ((element & X) == X) { list.push_back(element); } } // If there is no element in the list // Output -1 if (list.empty()) { cout << -1 << endl; } else { int AND = list[0]; // Calculate the cumulative AND of all elements present in the list for ( int i = 1; i < list.size(); i++) { AND = AND & list[i]; } // If the cumulative AND is equal to X, output the list elements; otherwise, -1 if (AND == X) { for ( int element : list) { cout << element << " " ; } cout << endl; } else { cout << -1 << endl; } } } int main() { // Inputs int N = 5; vector< int > A = {2, 8, 5, 4, 3}; int X = 1; // Function call AND_Subsequence(N, A, X); return 0; } //Contributed by Aditi Tyagi |
Java
// Java code to implement the approach import java.util.*; public class Main { // Driver Function public static void main(String[] args) { // Inputs int N = 5 ; int A[] = { 2 , 8 , 5 , 4 , 3 }; int X = 1 ; // Function call AND_Subsequence(N, A, X); } // Function to check such subsequence // exists or not public static void AND_Subsequence( int N, int A[], int X) { // List to store relvent elements, which // can possibly make cumulative AND as X ArrayList<Integer> list = new ArrayList<>(); // Iterating over array for ( int element : A) { // If element&X == X (all bits which // are set in X are also set in // element(A[i])) Then add it // into the list if ((element & X) == X) { list.add(element); } } // If there is no element in list // Output -1 if (list.size() == 0 ) { System.out.println(- 1 ); } // Else check that, cumulative AND of // all elements present in list is equal // to X. If yes then output list // elements else -1 else { int AND = list.get( 0 ); for ( int i = 1 ; i < list.size(); i++) { AND = AND & list.get( 1 ); } System.out.println(AND == X ? list : - 1 ); } } } |
Python3
# Python implementation def AND_Subsequence(N, A, X): # List to store relevant elements, which can possibly make cumulative AND as X lst = [] # Iterating over the array for element in A: # If element & X == X (all bits which are set in X are also set in element(A[i])) # Then add it into the list if (element & X) = = X: lst.append(element) # If there is no element in the list # Output -1 if not lst: print ( - 1 ) else : AND = lst[ 0 ] # Calculate the cumulative AND of all elements present in the list for i in range ( 1 , len (lst)): AND = AND & lst[i] # If the cumulative AND is equal to X, output the list elements; otherwise, -1 if AND = = X: for element in lst: print (element, end = " " ) print () else : print ( - 1 ) # Inputs N = 5 A = [ 2 , 8 , 5 , 4 , 3 ] X = 1 # Function call AND_Subsequence(N, A, X) # This code is contributed by Sakshi |
C#
using System; using System.Collections.Generic; class Program { // Function to check if such a subsequence exists or not static void AND_Subsequence( int N, List< int > A, int X) { // List to store relevant elements, which can possibly make cumulative AND as X List< int > list = new List< int >(); // Iterating over the array foreach ( int element in A) { // If element & X == X (all bits which are set in X are also set in element(A[i)) // Then add it into the list if ((element & X) == X) { list.Add(element); } } // If there is no element in the list // Output -1 if (list.Count == 0) { Console.WriteLine(-1); } else { int AND = list[0]; // Calculate the cumulative AND of all elements present in the list for ( int i = 1; i < list.Count; i++) { AND = AND & list[i]; } // If the cumulative AND is equal to X, output the list elements; otherwise, -1 if (AND == X) { foreach ( int element in list) { Console.Write(element + " " ); } Console.WriteLine(); } else { Console.WriteLine(-1); } } } static void Main( string [] args) { // Inputs int N = 5; List< int > A = new List< int > { 2, 8, 5, 4, 3 }; int X = 1; // Function call AND_Subsequence(N, A, X); } } //This code is contributed by chinmaya121221 |
Javascript
// JavaScript code to implement the approach // Function to check if such a subsequence exists or not function AND_Subsequence(N, A, X) { // Array to store relevant elements, // which can possibly make cumulative AND as X const list = []; // Iterating over the array for (const element of A) { // If element & X == X (all bits which // are set in X are also set in element(A[i])) // Then add it into the list if ((element & X) === X) { list.push(element); } } // If there is no element in the list // Output -1 if (list.length === 0) { console.log(-1); } else { let AND = list[0]; // Calculate the cumulative AND of // all elements present in the list for (let i = 1; i < list.length; i++) { AND = AND & list[i]; } // If the cumulative AND is equal to // X, output the list elements; otherwise, -1 if (AND === X) { console.log(list.join( " " )); } else { console.log(-1); } } } // Inputs const N = 5; const A = [2, 8, 5, 4, 3]; const X = 1; // Function call AND_Subsequence(N, A, X); |
[5, 3]
Time Complexity: O(N)
Auxiliary Space: O(N), an ArrayList is created to store relevant elements, The maximum size of ArrayList can be equal to A[].