Given an array ‘arr’, the task is to find all possible integers each of which is the bitwise AND of at least one non-empty sub-array of ‘arr’.
Examples:
Input: arr = {11, 15, 7, 19}
Output: [3, 19, 7, 11, 15]
3 = arr[2] AND arr[3]
19 = arr[3]
7 = arr[2]
11 = arr[0]
15 = arr[1]
Input: arr = {5, 2, 8, 4, 1}
Output: [0, 1, 2, 4, 5, 8]
0 = arr[3] AND arr[4]
1 = arr[4]
2 = arr[1]
4 = arr[3]
5 = arr[0]
8 = arr[2]
Naive Approach:
- An array of size ‘N’ contains N*(N+1)/2 sub-arrays. So, for small ‘N’, iterate over all possible sub-arrays and add each of their AND result to a set.
- Since sets do not contain duplicates, it’ll store each value only once.
- Finally, print the contents of the set.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;int main(){ int A[] = {11, 15, 7, 19}; int N = sizeof(A) / sizeof(A[0]); // Set to store all possible AND values. unordered_set<int> s; int i, j, res; // Starting index of the sub-array. for (i = 0; i < N; ++i) // Ending index of the sub-array. for (j = i, res = INT_MAX; j < N; ++j) { res &= A[j]; // AND value is added to the set. s.insert(res); } // The set contains all possible AND values. for (int i : s) cout << i << " "; return 0;}// This code is contributed by// sanjeev2552 |
Java
// Java implementation of the approachimport java.util.HashSet;class CP { public static void main(String[] args) { int[] A = { 11, 15, 7, 19 }; int N = A.length; // Set to store all possible AND values. HashSet<Integer> set = new HashSet<>(); int i, j, res; // Starting index of the sub-array. for (i = 0; i < N; ++i) // Ending index of the sub-array. for (j = i, res = Integer.MAX_VALUE; j < N; ++j) { res &= A[j]; // AND value is added to the set. set.add(res); } // The set contains all possible AND values. System.out.println(set); }} |
Python3
# Python3 implementation of the approach A = [11, 15, 7, 19] N = len(A) # Set to store all possible AND values. Set = set() # Starting index of the sub-array. for i in range(0, N): # Ending index of the sub-array. res = 2147483647 # Integer.MAX_VALUE for j in range(i, N): res &= A[j] # AND value is added to the set. Set.add(res) # The set contains all possible AND values. print(Set)# This code is contributed by Rituraj Jain |
C#
// C# implementation of the approach using System;using System.Collections.Generic;class CP { public static void Main(String[] args) { int[] A = {11, 15, 7, 19}; int N = A.Length; // Set to store all possible AND values. HashSet<int> set1 = new HashSet<int>(); int i, j, res; // Starting index of the sub-array. for (i = 0; i < N; ++i) { // Ending index of the sub-array. for (j = i, res = int.MaxValue; j < N; ++j) { res &= A[j]; // AND value is added to the set. set1.Add(res); } } // displaying the values foreach(int m in set1) { Console.Write(m + " "); } } } |
Javascript
// JavaScript implementation of the approachconst A = [11, 15, 7, 19];const N = A.length;// Set to store all possible AND values.const set = new Set();// Starting index of the sub-array.for (let i = 0; i < N; i++) {// Ending index of the sub-array.let res = 2147483647; // Integer.MAX_VALUEfor (let j = i; j < N; j++) {res &= A[j];// AND value is added to the set.set.add(res);}}// The set contains all possible AND values.console.log(set); |
Output:
[3, 19, 7, 11, 15]
Time Complexity: O(N^2)
Efficient Approach: This problem can be solved efficiently by divide-and-conquer approach.
- Consider each element of the array as a single segment. (‘Divide’ step)
- Add the AND value of all the subarrays to the set.
- Now, for the ‘conquer’ step, keep merging consecutive subarrays and keep adding the additional AND values obtained while merging.
- Continue step 4, until a single segment containing the entire array is obtained.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// c++ equivalent code of the Python codeclass Segment{ public: vector<int> leftToRight; vector<int> rightToLeft; void addToLR(int value){ if(leftToRight.size() == 0){ leftToRight.push_back(value); } else{ int lastElement = leftToRight[leftToRight.size() - 1]; // value decreased after AND-ing with 'value' if((lastElement & value) < lastElement){ leftToRight.push_back(lastElement & value); } } } void addToRL(int value){ if(rightToLeft.size() == 0){ rightToLeft.push_back(value); } else{ int lastElement = rightToLeft[rightToLeft.size() - 1]; // value decreased after AND-ing with 'value' if((lastElement & value) < lastElement){ rightToLeft.push_back(lastElement & value); } } } // copies 'lr' to 'leftToRight' void copyLR(vector<int> lr){ for(auto x: lr){ leftToRight.push_back(x); } } // copies 'rl' to 'rightToLeft' void copyRL(vector<int> rl){ for(auto x: rl){ rightToLeft.push_back(x); } } };Segment mergeSegments(Segment a, Segment b) { Segment res;// The resulting segment will have same prefix sequence as segment 'a' res.copyLR(a.leftToRight); // The resulting segment will have same suffix sequence as segment 'b' res.copyRL(b.rightToLeft); for (auto x: b.leftToRight){ res.addToLR(x); } for (auto x: a.rightToLeft){ res.addToRL(x); } return res;}Segment divideThenConquer(vector<int> ar,int l,int r,set<int> &allPossibleAND) { // can't divide into further segments if (l == r){ allPossibleAND.insert(ar[l]); // Therefore, return a segment containing this single element. Segment ret; ret.leftToRight.push_back(ar[l]); ret.rightToLeft.push_back(ar[l]); return ret; }// can be further divided into segments else { // recursive calls to divide the array into two halves Segment left = divideThenConquer(ar, l, floor((l+r)/2), allPossibleAND); Segment right = divideThenConquer(ar, floor((l+r)/2)+1, r, allPossibleAND); // Now, add all possible AND results, contained in these two segments for(auto itr1: left.rightToLeft){ for(auto itr2: right.leftToRight){ allPossibleAND.insert(itr1 & itr2); } } // 'conquer' step return mergeSegments(left, right); }}int main() { vector<int> ar = {11, 15, 7, 19}; int n = ar.size(); set<int> allPossibleAND; // call divideThenConquer function divideThenConquer(ar, 0, n-1, allPossibleAND); for(auto x: allPossibleAND){ cout << x << " "; } cout << endl;}// The code is contributed by Nidhi goel. |
Java
// Java implementation of the approachimport java.util.*;public class CP { static int ar[]; static int n; // Holds all possible AND results static HashSet<Integer> allPossibleAND; // driver code public static void main(String[] args) { ar = new int[] { 11, 15, 7, 19 }; n = ar.length; allPossibleAND = new HashSet<>(); // initialization divideThenConquer(0, n - 1); System.out.println(allPossibleAND); } // recursive function which adds all // possible AND results to 'allPossibleAND' static Segment divideThenConquer(int l, int r) { // can't divide into //further segments if (l == r) { allPossibleAND.add(ar[l]); // Therefore, return a segment // containing this single element. Segment ret = new Segment(); ret.leftToRight.add(ar[l]); ret.rightToLeft.add(ar[l]); return ret; } // can be further divided into segments else { Segment left = divideThenConquer(l, (l + r) / 2); Segment right = divideThenConquer((l + r) / 2 + 1, r); // Now, add all possible AND results, // contained in these two segments /* ******************************** This step may seem to be inefficient and time consuming, but it is not. Read the 'Analysis' block below for further clarification. *********************************** */ for (int itr1 : left.rightToLeft) for (int itr2 : right.leftToRight) allPossibleAND.add(itr1 & itr2); // 'conquer' step return mergeSegments(left, right); } } // returns the resulting segment after // merging segments 'a' and 'b' // 'conquer' step static Segment mergeSegments(Segment a, Segment b) { Segment res = new Segment(); // The resulting segment will have // same prefix sequence as segment 'a' res.copyLR(a.leftToRight); // The resulting segment will have // same suffix sequence as segment 'b' res.copyRL(b.rightToLeft); Iterator<Integer> itr; itr = b.leftToRight.iterator(); while (itr.hasNext()) res.addToLR(itr.next()); itr = a.rightToLeft.iterator(); while (itr.hasNext()) res.addToRL(itr.next()); return res; }}class Segment { // These 'vectors' will always // contain atmost 30 values. ArrayList<Integer> leftToRight = new ArrayList<>(); ArrayList<Integer> rightToLeft = new ArrayList<>(); void addToLR(int value) { int lastElement = leftToRight.get(leftToRight.size() - 1); // value decreased after AND-ing with 'value' if ((lastElement & value) < lastElement) leftToRight.add(lastElement & value); } void addToRL(int value) { int lastElement = rightToLeft.get(rightToLeft.size() - 1); // value decreased after AND-ing with 'value' if ((lastElement & value) < lastElement) rightToLeft.add(lastElement & value); } // copies 'lr' to 'leftToRight' void copyLR(ArrayList<Integer> lr) { Iterator<Integer> itr = lr.iterator(); while (itr.hasNext()) leftToRight.add(itr.next()); } // copies 'rl' to 'rightToLeft' void copyRL(ArrayList<Integer> rl) { Iterator<Integer> itr = rl.iterator(); while (itr.hasNext()) rightToLeft.add(itr.next()); }} |
Python3
from typing import Listfrom collections import defaultdict# Segment class definitionclass Segment: def __init__(self): self.leftToRight = [] # left to right segment self.rightToLeft = [] # right to left segment def addToLR(self, value): if len(self.leftToRight) == 0: self.leftToRight.append(value) else: lastElement = self.leftToRight[-1] # value decreased after AND-ing with 'value' if (lastElement & value) < lastElement: self.leftToRight.append(lastElement & value) def addToRL(self, value): if len(self.rightToLeft) == 0: self.rightToLeft.append(value) else: lastElement = self.rightToLeft[-1] # value decreased after AND-ing with 'value' if (lastElement & value) < lastElement: self.rightToLeft.append(lastElement & value) # copies 'lr' to 'leftToRight' def copyLR(self, lr): self.leftToRight = lr.copy() # copies 'rl' to 'rightToLeft' def copyRL(self, rl): self.rightToLeft = rl.copy()# recursive function which adds all possible AND results to 'allPossibleAND'def divideThenConquer(ar: List[int], l: int, r: int, allPossibleAND: set): # can't divide into further segments if l == r: allPossibleAND.add(ar[l]) # Therefore, return a segment containing this single element. ret = Segment() ret.leftToRight.append(ar[l]) ret.rightToLeft.append(ar[l]) return ret # can be further divided into segments else: # recursive calls to divide the array into two halves left = divideThenConquer(ar, l, (l+r)//2, allPossibleAND) right = divideThenConquer(ar, (l+r)//2+1, r, allPossibleAND) # Now, add all possible AND results, contained in these two segments for itr1 in left.rightToLeft: for itr2 in right.leftToRight: allPossibleAND.add(itr1 & itr2) # 'conquer' step return mergeSegments(left, right)# returns the resulting segment after merging segments 'a' and 'b'# 'conquer' stepdef mergeSegments(a: Segment, b: Segment) -> Segment: res = Segment() # The resulting segment will have same prefix sequence as segment 'a' res.copyLR(a.leftToRight) # The resulting segment will have same suffix sequence as segment 'b' res.copyRL(b.rightToLeft) for value in b.leftToRight: res.addToLR(value) for value in a.rightToLeft: res.addToRL(value) return res# driver codedef main(): ar = [11, 15, 7, 19] n = len(ar) allPossibleAND = set() # initialize with default values leftToRight = defaultdict(int) rightToLeft = defaultdict(int) # call divideThenConquer function divideThenConquer(ar, 0, n-1, allPossibleAND) print(allPossibleAND)if __name__ == '__main__': main() |
Javascript
// JavaScript equivalent code of the Python codefunction Segment() {this.leftToRight = []; // left to right segmentthis.rightToLeft = []; // right to left segment}Segment.prototype.addToLR = function (value) {if (this.leftToRight.length === 0) {this.leftToRight.push(value);} else {let lastElement = this.leftToRight[this.leftToRight.length - 1];// value decreased after AND-ing with 'value'if ((lastElement & value) < lastElement) {this.leftToRight.push(lastElement & value);}}};Segment.prototype.addToRL = function (value) {if (this.rightToLeft.length === 0) {this.rightToLeft.push(value);} else {let lastElement = this.rightToLeft[this.rightToLeft.length - 1];// value decreased after AND-ing with 'value'if ((lastElement & value) < lastElement) {this.rightToLeft.push(lastElement & value);}}};Segment.prototype.copyLR = function (lr) {this.leftToRight = lr.slice();};Segment.prototype.copyRL = function (rl) {this.rightToLeft = rl.slice();};function divideThenConquer(ar, l, r, allPossibleAND) {// can't divide into further segmentsif (l === r) {allPossibleAND.add(ar[l]);// Therefore, return a segment containing this single element.let ret = new Segment();ret.leftToRight.push(ar[l]);ret.rightToLeft.push(ar[l]);return ret;}// can be further divided into segmentselse { // recursive calls to divide the array into two halves let left = divideThenConquer(ar, l, Math.floor((l+r)/2), allPossibleAND); let right = divideThenConquer(ar, Math.floor((l+r)/2)+1, r, allPossibleAND); // Now, add all possible AND results, contained in these two segments for (let itr1 of left.rightToLeft) { for (let itr2 of right.leftToRight) { allPossibleAND.add(itr1 & itr2); } } // 'conquer' step return mergeSegments(left, right);}}function mergeSegments(a, b) {let res = new Segment();// The resulting segment will have same prefix sequence as segment 'a'res.copyLR(a.leftToRight);// The resulting segment will have same suffix sequence as segment 'b'res.copyRL(b.rightToLeft);for (let value of b.leftToRight) { res.addToLR(value);}for (let value of a.rightToLeft) { res.addToRL(value);}return res;}// driver codefunction main() {let ar = [11, 15, 7, 19];let n = ar.length;let allPossibleAND = new Set();// call divideThenConquer functiondivideThenConquer(ar, 0, n-1, allPossibleAND);console.log(allPossibleAND);}main(); |
Output:
[19, 3, 7, 11, 15]
Analysis: The major optimization in this algorithm is realizing that any array element can yield a maximum of 30 distinct integers (as 30 bits are needed to hold 1e9). Confused?? Let’s proceed step by step. Let us start a sub-array from the ith element which is A[i]. As the succeeding elements are AND-ed with Ai, the result can either decrease or remain same (because a bit will never get changed from ‘0’ to ‘1’ after an AND operation). In the worst case, A[i] can be 2^31 – 1 (all 30 bits will be ‘1’). As the elements are AND-ed, atmost 30 distinct values can be obtained because only a single bit might get changed from ‘1’ to ‘0’ in the worst case, i.e. 111111111111111111111111111111 => 111111111111111111111111101111 So, for each ‘merge’ operation, these distinct values merge to form another set having atmost 30 integers. Therefore,
Worst Case Time Complexity for each merge can be O(30 * 30) = O(900).
Time Complexity: O(900*N*logN). PS: The time complexity can seem too high, but in practice, the actual complexity lies around O(K*N*logN), where, K is much less than 900. This is because, the lengths of the ‘prefix’ and ‘suffix’ arrays are much less when ‘l’ and ‘r’ are quite close.
Take a part in the ongoing discussion
