# Another OR Related Problem

**URL:** <https://discuss.codechef.com/t/another-or-related-problem/89877>\
**Category:** help\
**Tags:** problem, programming\
**Created:** [May 20, 2021, 6:03am UTC](https://discuss.codechef.com/t/another-or-related-problem/89877 "2021-05-20T06:03:19Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![roushan\_17](https://discuss.codechef.com/user_avatar/discuss.codechef.com/roushan_17/32/193746_2.png) [@roushan\_17](https://discuss.codechef.com/u/roushan_17)\
**Post date:** [May 20, 2021, 6:03am UTC](https://discuss.codechef.com/t/another-or-related-problem/89877/1 "2021-05-20T06:03:19Z")

</div>

I recently appeared for a contest and many questions were asked. I could solve all but 1.

The question is suppose you are given an array A consisting of N elements  
Then form a new Array B, such that it contains _ **binary or** _ of elements from Al | Al+1 | . . | Ar  
for all 1 \<= l \<= r \<= N

for example given Array is A = [1, 2, 4]  
then B contains = [1, 2, 4, 1|2, 2|4, 1|2|4] = [1, 2, 4, 3, 6, 7]

Given a list of Q Queries each query denoted a number K , we have to find the K’th smallest number in B

Lets say the queries are [2, 5]  
then answer would be a list = [2, 6] // 2nd and 5th smallest element respectively

Assume all arrays are 1 indexed

**Constraints**  
1 \<= N \<= 105  
1 \<= Q \<= 105  
1 \<= A[i] \<= 109

Time Limit: 4.sec

can anyone tell me how one could approach this

PS: I tried this article here but was not able to make much progress on finding rank of a number in subarray or

UPD: I HAVE SOLVED THE PROBLEM.

Tagging users  
@taran_1407@cubefreak777 @ashutosh450 @l_returns @vijju123 @nishant403@anshugarg12 @ssjgz @ayush_2407

---

<div class="post-metadata">

**Author:** ![demoralizer](https://discuss.codechef.com/user_avatar/discuss.codechef.com/demoralizer/32/100617_2.png) [@demoralizer](https://discuss.codechef.com/u/demoralizer)\
**Post date:** [May 20, 2021, 6:53am UTC](https://discuss.codechef.com/t/another-or-related-problem/89877/2 "2021-05-20T06:53:02Z")

</div>

“Tagging most frequent posters”

- Next time, don’t.  
Edit: I was tagged in the previous revision of the post

---

<div class="post-metadata">

**Author:** ![roushan\_17](https://discuss.codechef.com/user_avatar/discuss.codechef.com/roushan_17/32/193746_2.png) [@roushan\_17](https://discuss.codechef.com/u/roushan_17)\
**Post date:** [May 20, 2021, 6:53am UTC](https://discuss.codechef.com/t/another-or-related-problem/89877/3 "2021-05-20T06:53:24Z")

</div>

ok. Since you are here. Would you please answer the question

---

<div class="post-metadata">

**Author:** ![demoralizer](https://discuss.codechef.com/user_avatar/discuss.codechef.com/demoralizer/32/100617_2.png) [@demoralizer](https://discuss.codechef.com/u/demoralizer)\
**Post date:** [May 20, 2021, 6:56am UTC](https://discuss.codechef.com/t/another-or-related-problem/89877/4 "2021-05-20T06:56:08Z")

</div>

Since there are only 30 bits in the numbers, the OR won’t change more than 30 times if you start from a certain index. So array B will only have Nlog(maxA) elements.

There are multiple ways to efficiently find those elements, for example, segtree+descent or sparse table+binary search.

---

<div class="post-metadata">

**Author:** ![roushan\_17](https://discuss.codechef.com/user_avatar/discuss.codechef.com/roushan_17/32/193746_2.png) [@roushan\_17](https://discuss.codechef.com/u/roushan_17)\
**Post date:** [May 20, 2021, 7:00am UTC](https://discuss.codechef.com/t/another-or-related-problem/89877/5 "2021-05-20T07:00:24Z")

</div>

Yeah I removed you from tag. Didn’t knew it would be a bother. Anyway I would try what u said below and see if i could make it work. Thanks anyway

---

<div class="post-metadata">

**Author:** ![roushan\_17](https://discuss.codechef.com/user_avatar/discuss.codechef.com/roushan_17/32/193746_2.png) [@roushan\_17](https://discuss.codechef.com/u/roushan_17)\
**Post date:** [May 20, 2021, 5:51pm UTC](https://discuss.codechef.com/t/another-or-related-problem/89877/6 "2021-05-20T17:51:07Z")

</div>

I did see your video on segment tree and descent but am still confused how to do this. would you please explain in a bit more detail

---

<div class="post-metadata">

**Author:** ![vai53](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vai53/32/8794_2.png) [@vai53](https://discuss.codechef.com/u/vai53)\
**Post date:** [May 24, 2021, 8:01am UTC](https://discuss.codechef.com/t/another-or-related-problem/89877/8 "2021-05-24T08:01:14Z")

</div>

Send the solution @roushan_17

---

<div class="post-metadata">

**Author:** ![stupidgoat](https://discuss.codechef.com/user_avatar/discuss.codechef.com/stupidgoat/32/24644_2.png) [@stupidgoat](https://discuss.codechef.com/u/stupidgoat)\
**Post date:** [November 15, 2021, 9:44am UTC](https://discuss.codechef.com/t/another-or-related-problem/89877/9 "2021-11-15T09:44:40Z")

</div>

> [@roushan\_17](#):
>
> contains _ **binary or** _ of elements from Al | Al+1 | . . | Ar  
> for all 1 \<= l \<= r \<= N

can you share the solution