HackerRank DSA Solutions Tutorial

AND xor OR| Stack

❮ Previous Next ❯

TASK(hard)

Given an array A of N distinct elements. Let M1 and M2 be the smallest and the next smallest element in the interval [L,R] where 1<=L<R<=N.

S_i=(((M1 & M2)^(M1| M2)) ^(M1|M2)) are the bitwise operators , and respectively.
Your task is to find the maximum possible value of S_i.

Input Format

First line contains integer N.
Second line contains N integers, representing elements of the array A.

Constraints

1<N<=106
1<=Ai<=109

Output Format

Print the value of maximum possible value of S_i.

Sample Input

5

9 6 3 5 2

Sample Output

SOLUTION 1

def andXorOr(a):

    m = 0

    s = []

    for i in a:    

        while s and s[-1] >= i:

            m = max(m, i^s.pop())

        if s:

            m = max(m, i^s[-1])

        s.append(i)

    return m

EXPLANATION STEPS

1. Understand Bitwise Properties:
The expression can be rewritten as (a XOR b) AND NOT(a AND b).
1. Optimization Insight:

To maximize (a XOR b), ideally a and b should differ significantly in their binary representation (i.e., have many differing bits).
1. Strategy:

Use a stack-based approach to efficiently find the maximum value of (a XOR b) across all possible pairs (a, b) in the array.
Utilize properties of the bitwise operations to compute the maximum value of the given expression.
1. Edge Cases:

Handle arrays with small sizes or extreme values (like minimum or maximum possible integers).
Ensure the implementation is efficient and handles the bitwise operations correctly.

❮ Previous Next ❯

HackerRank DSA Solutions Tutorial

HackerRank DSA Solutions Tutorial

HackerRank DSA Solutions

AND xor OR| Stack

Important Links