Bitwise OR Of Adjacent Elements

Easy
0/40
Average time to solve is 10m
profile
Contributed by
3 upvotes
Asked in company
D.E.Shaw

Problem statement

You are given an array 'ARR' of integers having 'N' elements. Your task is to replace each element of the array with the Bitwise OR of that element and the element placed adjacent to it on the right. If for a particular element, there is no element to its right, then keep the element unchanged.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains an integer, 'N,’ denoting the number of elements in the array 'ARR'.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.

Output Format :

For each test case, print 'N' space-separated integers in which the i’th integer should denote the bitwise OR of ARR[i] and ARR[i+1].

Print the output of each test case in a new line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
0 <= ARR[i] <= 10^9

Where 'ARR[i]' denotes the 'i'th' element of the array 'ARR'.

Time Limit: 1 sec

Sample Input 1 :

2
4 
1 2 5 3
3 
1 2 4

Sample Output 1 :

3 7 7 3
3 6 4

Explanation for Sample Input 1 :

For the first test case : 
1) ARR[0] changes to ARR[0] OR ARR[1]. So ARR[0] becomes 3 ( 1 OR 2 = 3 ).
2) ARR[1] changes to ARR[1] OR ARR[2]. So ARR[1] becomes 7 ( 2 OR 5 = 7 ).
3) ARR[2] changes to ARR[2] OR ARR[3]. So ARR[2] becomes 7 ( 5 OR 3 = 7 ).
4) ARR[3] remains unchanged as there is no element present to its right.

For the second test case : 
1) ARR[0] changes to ARR[0] OR ARR[1]. So ARR[0] becomes 3 ( 1 OR 2 = 3 ).
2) ARR[1] changes to ARR[1] OR ARR[2]. So ARR[1] becomes 6 ( 2 OR 4 = 6 ).
3) ARR[3] remains unchanged as there is no element present to its right.

Sample Input 2 :

2
4
3 3 2 5
2
1 2

Sample Output 2 :

3 3 7 5
3 2
Hint

Traverse the input array from left to right and update each element one by one except the last element.

Approaches (1)
Optimized Approach

The idea is to iterate through the input array from left to right, and for each element find the Bitwise OR of it and the element placed adjacent to it. We also need to observe that the last element of the array will never be modified as there will never be an element present to its right. It is important to note that, if we traverse the array

from right to left and not left to right, then the obtained result will not be correct as we will be using the updated values of the array elements in our calculations which will not produce the correct result.

 

Steps:

  1. Iterate from i = 0 to N - 2
    • Set ARR[i] to the Bitwise OR of ARR[i] and ARR[i+1]. Here, we are updating the value of the i'th element by taking Bitwise OR with the (i+1)'th element, which in turn is the element placed adjacent to its right.
  2. Return the modified array ARR.
Time Complexity

O(N), where N is the number of elements in the array.

 

As we are iterating through all the N elements of the array only once and it takes constant time to find the Bitwise OR and update the value of one array element. Hence, the overall Time Complexity is O(N).

Space Complexity

O(1).

 

We are using only constant extra space. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Bitwise OR Of Adjacent Elements
Full screen
Console