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.

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 = 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