You are given an array A, create an another array B all or subarrays of A.
[ Note - Subarrays B are formed by removing zero or more elements from the front or/and back of the original array without changing the order of the remaining element ]
Do a Bitwise OR on the subarrays and get the Kth smallest element
Inputs :
A = [1, 2, 3]
K = 6
Output:
3
Explanation:
Given array A = [1, 2, 3], generate a Array B using A
B = [ 1, (1, 2), (1, 2, 3), 2, (2, 3), 3]
Now do Bitwise OR among the subarrays, which gives you
B = [1, 3, 3, 2, 3, 3]
Atlast get the Kth smallest element of B, if K = 6 , from sorted B we will get
B=[1, 2, 3, 3, 3, 3]
6th smallest element is 3
Now I am able to solve the problem in Worst Case time complexity, which is below.
But what will be optimized approach for the problem
public static List<Integer> worstCase(int[] A, int K) {
List<Integer> _or = new ArrayList<>();
for(int i = 0; i < A.length; i++) {
_or.add(A[i]);
int prevOr = A[i];
for(int j = i + 1; j < A.length; j++) {
prevOr = prevOr | A[j];
_or.add(prevOr);
}
}
Collections.sort(_or);
Integer output = _or.get(K);
return _or;
}