# HackerRank Coding Interview 8. Maximum Or-Sum

--

**Time to complete **— 30 minutes

**Question Type =** Medium

**Asked in = Netflix, Amazon, Uber, Lyft, Bloomberg, Morgan Stanley, Apple, and Google, Synchrony.**

**Skills:** arrays, bit manipulation, prefix array

**Insights — **It should be read very carefully read and you must ask questions in between.

**Question —**

For an array of *n* integers, *arr[n]*, perform the following operation up to some integer *k* times.

- Choose an index
*i*such that 1 ≤*i*≤*n.* - Replace
*arr[i]*with*arr[i]×2.*

The *or-sum* is the bitwise-or of all elements in the final array after the operations. Return the maximum *or-sum *possible*.*

`# HINT is below`

# bitwise operators

a = 10

b = 4

# Print bitwise AND operation

print("a & b =", a & b)

# Print bitwise OR operation

print("a | b =", a | b)

# Print bitwise NOT operation

print("~a =", ~a)

# print bitwise XOR operation

print("a ^ b =", a ^ b)

`HINT `

.....for Bitwise OR operation with integer 2

.....K-times, is nothing but RIGHT shift the number K times.

Interger_value << k ==== K-times [Interger_value (bitwise-OR) 2 ]

**Example**

*arr* = [12, 9]

*k = 1*

These outcomes are possible after *1* operation.

- Select
*i = 1*:

- The final array is
*arr*= [24, 9]. - Its
*or-sum*is 25*.*

- Select
*i = 2*:

- The final array is
*arr*= [12, 18]. - Its
*or-sum*is 30*.*

Of these, 30 is the greater *or-sum*. Return 30.

**Function Description**

Complete the* getMaxOrSum *function in the editor below.

*getMaxOrSum* has the following parameters:

*int arr[n]:* the original array

*int k: *the* *maximum number of operations

**Returns**

*long int*: the maximum possible *or-sum*

**Constraints**

- 1 ≤
*n*≤ 105 - 1 ≤
*arr[i]*≤ 106 - 1 ≤
*k*≤ 11

**Input Format For Custom Testing**

The first line of input contains an integer *n*, the size of *arr*.

Each of the following *n* lines contains an integer, *arr[i].*

The last line contains an integer, *k.*

**Sample Case 0**

Sample Input For Custom Testing

`STDIN FUNCTION`

----- --------

2 → n = 2

10 → arr = [10, 1]

1

1 → k = 1

Sample Output

`21`

**Explanation**

Select i = 1. The final array is *[20, 1].*

*20 OR 1 = 21.*

# Sample Case 1

Sample Input For Custom Testing

`STDIN FUNCTION`

----- --------

2 → n = 2

5 → arr = [5, 8]

8

3 → k = 3

Sample Output

`69`

**Explanation**

Select *i = 2* and apply the operation three times (8 -> 16 -> 32 -> 64) to get *[5, 64].*

*5 OR 64 = 69*

# Solution

Sample Input For Custom Testing

`STDIN FUNCTION`

----- --------

2 → n = 2

5 → arr = [5, 8]

8

3 → k = 3

Sample Output

`69`

**Explanation**

Select *i = 2* and apply the operation three times (8 -> 16 -> 32 -> 64) to get *[5, 64].*

*5 OR 64 = 69*

**Optimal Solution:**

The operation is basically a right shift operator. The key observation is that it is always optimal to do **all k operations on the one element **with the

**highest significant bit set**.

`What is most significant bit (MSB)?`

The most significant bit (MSB) is the bit in a multiple-bit binary number with the largest value. This is usually the bit farthest to the left, or the bit transmitted first in a sequence.

For example,

- in the binary number 1000, the MSB is 1, and

- in the binary number 0111, the MSB is 0.

Now, iterate over all the indices and assume that the operations are performed on the element of that index.

To calculate the *or-sum* after applying the operation to index *i,* maintain a prefix array *pre* and a suffix array *post* representing the *or-sums *of the prefix and suffix subarrays of the array *arr* at index *i *respectively.

The answer is the maximum among all values after performing operations, that is:

ans =Max(pre[i — 1]|new_arr[i]|post[i + 1])where

new_arr[i] = arr[i] * pow(2, k)and | is the bitwise or operation.

`def getMaxOrSum(arr, k):`

n = len(arr)

if n==1:

return arr[0]<<k

pre = [0]*n

post = [0]*n

# From the FRONT of the array

# bitwise-or of each element with its next ARR element

# and store in array PRE

pre[0] = arr[0]

for i in range(1,n):

pre[i] = pre[i-1] | arr[i]

# From the BACK of the array

# bitwise-or of each element with its previous ARR element

# and store in array POST

post[n-1] = arr[n-1]

for i in range(n-2,-1,-1):

post[i] = post[i+1] | arr[i]

front_max = arr[0] << k | post[1]

last_max = arr[n-1] << k | pre[n-2]

ans = max(last_max, front_max)

for i in range(1, n-1):

ans = max(ans, (arr[i]<<k) | pre[i-1]| post[i+1] )

return ans

Complete Solution with read in from the disk

`#!/bin/python3`

import math

import os

import random

import re

import sys

#

# Complete the 'getMaxOrSum' function below.

#

# The function is expected to return a LONG_INTEGER.

# The function accepts following parameters:

# 1. INTEGER_ARRAY arr

# 2. INTEGER k

#

def getMaxOrSum(arr, k):

n = len(arr)

if n==1:

return arr[0]<<k

pre = [0]*n

post = [0]*n

# From the FRONT of the array

# bitwise-or of each element with its next ARR element

# and store in array PRE

pre[0] = arr[0]

for i in range(1,n):

pre[i] = pre[i-1] | arr[i]

# From the BACK of the array

# bitwise-or of each element with its previous ARR element

# and store in array POST

post[n-1] = arr[n-1]

for i in range(n-2,-1,-1):

post[i] = post[i+1] | arr[i]

last_max = arr[0] << k | post[1]

front_max = arr[n-1] << k | pre[n-2]

ans = max(last_max, front_max)

for i in range(1, n-1):

ans = max(ans, (arr[i]<<k) | pre[i-1]| post[i+1] )

return ans

def getMaxOrSum(arr, k):

n = len(arr)

if n==1:

return (arr[0]<<k)

pre = [0]*n

post = [0]*n

pre[0] = arr[0]

for i in range(1,n):

pre[i] = pre[i-1] | arr[i]

post[n-1] = arr[n-1]

for i in range(n-2,-1,-1):

post[i] = post[i+1] | arr[i]

ans = max((arr[0]<<k)|post[1],(arr[n-1]<<k)|pre[n-2])

for i in range(1, n-1):

ans = max(ans, (arr[i]<<k)|pre[i-1]|post[i+1] )

return ans

if __name__ == '__main__':

fptr = open(os.environ['OUTPUT_PATH'], 'w')

arr_count = int(input().strip())

arr = []

for _ in range(arr_count):

arr_item = int(input().strip())

arr.append(arr_item)

k = int(input().strip())

result = getMaxOrSum(arr, k)

fptr.write(str(result) + '\n')

fptr.close()

**Time Complexity** — O(*n *)

- O(
*n*) to calculate prefix and suffix values - O(
*n*) to calculate the final answer

**Space Complexity** — O(*n *)

- O(
*n)*to store the*pre*and*post*arrays.

`Github link to run and experiment with the file:`

`https://github.com/AI-Org/interview_preparation_answers/blob/main/src/array_Maximum_Or-Sum.py`