# 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

# 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 ≤ in.
• 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 = 10b = 4 # Print bitwise AND operationprint("a & b =", a & b) # Print bitwise OR operationprint("a | b =", a | b) # Print bitwise NOT operationprint("~a =", ~a) # print bitwise XOR operationprint("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.

1. Select i = 1 :
• The final array is arr = [24, 9].
• Its or-sum is 25.
1. 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 = 210      →    arr = [10, 1]11       →    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 = 25       →    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 = 25       →    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<<k            pre = *n    post = *n     # From the FRONT of the array     # bitwise-or of each element with its next ARR element    # and store in array PRE    pre = arr    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 << k | post    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/python3import mathimport osimport randomimport reimport 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<<k            pre = *n    post = *n     # From the FRONT of the array     # bitwise-or of each element with its next ARR element    # and store in array PRE    pre = arr    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 << k | post    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 ansdef getMaxOrSum(arr, k):    n = len(arr)    if n==1:        return (arr<<k)            pre = *n    post = *n        pre = arr    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<<k)|post,(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 ansif __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`

--

--

I write about Technical stuff, interview questions, and finance Deep Learning, LLM, Startup, Influencer, Executive, Data Science Manager