We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Stacks
  4. AND xor OR
  5. Discussions

AND xor OR

Sort by

recency

|

153 Discussions

|

  • dehaka
     + 1 comment

    O(n), 3 pass over the array A. there are only linearly many pairs (M1, M2)

    int andXorOr(int N, const vector<int>& A) {
    int maxXOR = 0;
    vector<int> prevSmaller(N, -1), nextSmaller(N, N);
    stack<int> prev, next;
    prev.push(0);
    next.push(N - 1);
    for (int i = 1; i < N; i++) {
        while (!prev.empty() and A[prev.top()] >= A[i]) prev.pop();
        if (!prev.empty()) prevSmaller[i] = prev.top();
        prev.push(i);
    }
    for (int i = N - 2; i >= 0; i--) {
        while (!next.empty() and A[i] <= A[next.top()]) next.pop();
        if (!next.empty()) nextSmaller[i] = next.top();
        next.push(i);
    }
    for (int i = 0; i < N; i++) {
        if (prevSmaller[i] != -1) maxXOR = max(maxXOR, A[i] ^ A[prevSmaller[i]]);
        if (nextSmaller[i] != N) maxXOR = max(maxXOR, A[i] ^ A[nextSmaller[i]]);
    }
    return maxXOR;
}

  • zallesov
     + 1 comment

    How is it that 9 and 6 are the smallest and the next smallest numbers in the given array? I struggle to understand this part of the assignment ` Let M0 and M1 be the smallest and the next smallest element in the interval. What defines L and M in this case? Is it just the 0 and 1 values in the whole array?

  • gfostick
     + 1 comment
    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

  • omar2004
     + 0 comments

    My JS Solution

    function andXorOr(A) {
    var stack = [A[0], A[1]];
    var S = A[0] ^ A[1];
    
    for(let i = 2; i < A.length; i++){
        while(stack.length > 0 && stack.slice(-1) >= A[i]){
            S = Math.max(S, stack.slice(-1) ^ A[i]);
            stack.pop();
        }
        if(stack.length > 0) S = Math.max(S, stack.slice(-1) ^ A[i]);
        stack.push(A[i])
    }
    return S;
}

  • omar2004
     + 0 comments

    My Python Solution

    def andXorOr(a):
    stack = [a[0], a[1]]
    S = a[0] ^ a[1]
    for i in range(2, len(a)):
        while len(stack) > 0 and stack[-1] >= a[i]:
            S = max(S, stack[-1] ^ a[i])
            stack.pop()
        if len(stack) > 0:
            S = max(S, stack[-1] ^ a[i])
        stack.append(a[i])
    return S