Can someone help me with this problem.
Given an array A of N numbers. We are required to find the size of the smallest subset of the array such that Bitwise OR is maximum possible.
$$$1 \leq N \leq 10^5$$$
$$$1 \leq A[i] \leq 10^6$$$
Sample input:
5
1 2 3 4 5
Sample output:
2
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Auto comment: topic has been updated by elements (previous revision, new revision, compare).
Post the link to the original problem.
I couldn't find any. This was one of the questions asked for Round 1 of HackwithInfy conducted by Infosys.
This has been asked before here.
Oh sorry. I didn't find it. Thank you.
This problem has A[i]<=10^6. So, I think its possible to solve it in A[i]log(A[i])^2. We can create polynomial where exponent is equal to value and coefficient is equal to one if that value is present in the array and otherwise 0. Then, we perform or convolutions repeatedly until the element corresponding to maximum or has non-zero coefficient. It will take obviously <= log(A[i]) steps atmax and each step costs A[i]log(A[i]).
Edit: Using binary lifting kind of thing you can achieve complexity O(A[i]log(A[i])log(log(A[i]))). Not sure if that would be much faster.
Whatever you said is quite above my level. I think I should leave this problem.
Suppose input is: $$$A[] = {1,2,8,7}$$$
max or is 15
Consider Polynomial: $$$P$$$ = 0 $$$x^0$$$ + 1 $$$x^1$$$ + 1 $$$x^2$$$ + 0 $$$x^3$$$ ... 1 $$$x^7$$$ + 1 $$$x^8$$$ + 0 (Coefficient of $$$x^i$$$ is count of i in $$$A$$$)
Define Multiplication Operation on Polynomials:
$$$A[0..n] , B[0..n]$$$ and $$$C = A * B$$$
where $$$C[z]$$$ = $$$\sum_{z = x|y} A[x] B[y]$$$
(Coefficient of $$$x^i$$$ is count of $$$j,k$$$ such that $$$A[j]|B[k] = i$$$)
Now back to Question, If $$$P$$$ is the polynomial defined above coefficient of $$$x^i$$$ in $$$P*P$$$ is the number of $$$j,k$$$ such that $$$A[j]|A[k] = i$$$ (you will get all possible ORs after taking two elements from P)
similarly in $$$P*P*P$$$ coefficient of $$$x^i$$$ is number of $$$j,k,l$$$ such that $$$A[j]|A[k]|A[l] = i$$$
you need to repeatedly multiply $$$P$$$ until coefficient of $$$P^{n}[max Or]$$$ is non zero then report index of {n}
Ok, all this is fine but can we do this multiplication fast? Yes, we can!
to learn more about this algorithm open this
Can you share the code for this problem? I am still confused about the solution approach. I tried it for a long time but was not able to solve it.
here
Thank you :)
It's really useful, thanks for sharing
You can actually optimize that to O(A[i]log(A[i])). Using the transform for OR convolution you have something like a[i] = number of ways to get exact mask of i, transformed to A[i] = number of ways to get submasks of i, since the or of submasks of i are also submasks of i. You can convolute it using exponentiation then you can extract the a[maximum size of mask using or possible] in O(A[i]) using inclusion-exclusion, so you get O(A[i]log(A[i])) for the initial transformation and O(A[i]) for finding if that certain mask was possible to get * O(log(A[i])) being the maximum size of the set.
If you want to master binary search or segment tree then this is one of the best questions. Binary search on answer can be used.
What is the maximum OR?
It is the OR of all the elements. Let it be MaxOR.
Maintain a segment tree to find bitwise OR for any given range.
Now do binary search with l=1 and r=N.
In each step, find if there exists any subarray that has OR=MaxOR by traversing through the array and using the segtree to compute OR of range (i,i+mid), where mid is the value of binary step.
He's asking about subset and not subarray. Then why do we need segment tree? Sorry if i am missing something.
My bad. Extremely sorry, misread the question, unable to delete.
It's okay. Don't be sorry. Your answer was helpful for me even though you answered a different question. Thanks.
This problem was also asked in Google Internship Online Coding Round.
I found this, but it is too simple to be correct. Can anyone verify?
It is incorrect. Take
[12, 10, 5]for example, that algorithm will output 3 while the answer is 2.Thanks
Please explain approach for solving this question. I not get any logic.
This isn't a obvious question. Look at this comment. You will have some idea.
Are you sure?. I got same question with same constraint in Google test
Yeah. You don't have to assume it is right, just because it was asked by Google. Moreover, technically it is not wrong, as you should be able to squeeze the algorithm mentioned above in the time limit if you optimize it a bit.
If I remove the numbers whose mask is a subset of an already existing number. Would this be a correct solution.
For Example if we have A=[1,3,4,2] then here 1 is a submask of 3 so I remove it 2 is a submask of 4 Hence my final subset will be [4,3]
I would like to know if this solution is correct. Can anybody please help me here?
Sorry for necroposting, but I had a similar idea; my idea is that as usual I find the maximum OR by finding the OR of all the elements of the array.
And then I take the element with the maximum number of set bits and then at every iteration I remove those submasks from all the numbers in the array and keep on doing this till I hit the required maximum OR.
So I wanted to ask if this approach is correct; can someone please confirm? If it is incorrect, please tell me a testcase where this approach would fail.
Thanks in advance!
I had the same idea too. Could you please let me know if you were able to find if this is a right approach or not?