- Practice
- Data Structures
- Stacks
- AND xor OR
- Discussions

# AND xor OR

# AND xor OR

AKSaigyouji + 10 comments This problem uses a rather peculiar trick with a stack that isn't at all intuitive and you're likely not to have seen before.

Suppose you have an array A and you want to know every pair of smallest integers for each subarray (i.e. given a subarray, you want the smallest integer and the second smallest integer, where a subarray is a contiguous subset of the original array).

This can be done in linear time using a stack. Here's the pseudocode ('yield' means a pair of smallest integers for some subarray has been found):

`For each int i in the array A while stack is nonempty yield (i, top of stack) if i is less than the top of the stack, pop the stack otherwise break the while loop push i onto stack`

The idea is that if you have a value b in your stack, and you encounter a value c which is smaller, then b cannot form a minimum pair with anything to the right of c. So once you yield the pair (b,c) you can safely dispose of b (you already handled possible pairs to the left).

This is the main subroutine for solving this problem, but I'll leave that to you.

jsa41394 + 0 comments This is correct, here's a Python implementation:

class Stack: def __init__(self): self.items = [] self.size = 0 def push(self, elem): self.items.append(elem) self.size += 1 def pop(self): self.size -= 1 return self.items.pop() def peek(self): return self.items[-1] def isEmpty(self): return self.size == 0 N = int(input()) A = [int(x) for x in input().split(" ")] mx = A[0]^A[1] stack = Stack() for i in A: popped = True while not stack.isEmpty(): top = stack.peek() Si = i^top if Si > mx: # yield mx = Si if i < top: stack.pop() else: break stack.push(i) print(mx)

I followed the pseudo-algorithm exactly. Is this correct intuition...?

-> For e.g. A=[4,5,3,7] yields => (i,top): (5,4);(3,5);(3,4);(7,3), which are the only contiguous pairs of two smallest elements. Note, for example, (4,7) is impossible, because that includes all of A => (3,4). [see below] New smaller elements pop out earlier (contiguously) elements, such as 3 popping 5 and 4.

-> Loop through A linearly.

-> When to push and pop to the stack? Push to the stack each new element in A, i, and if i is smaller than stack top, keep popping until all bigger earlier values popped (or stack empty) before adding i. This way any new smaller element pops all previous bigger elements, and the stack keeps pushing new elements when empty - always having a new pair (at least one element in non-empty stack and new element i).PKUGoodSpeed + 0 comments Thank so much

SamratK + 0 comments Thank you very much, AKSaigyouji for explaining the logic. I was stuck on this for half a day and was able to pass only 90% test cases. The code I implemented with your logic worked just fine for all cases.

kiberpress + 0 comments Elegant solution. Thank you for sharing.

samoan + 1 comment What I am not getting is why do you pop off the stack only if i is less than the top ? I guess my problem is I don't understand what it means b minimum pair. I get how the code works now but still stuck on what minimum pair means. Does it mean two numbers that are closest in value?

yayafuture + 1 comment It means the smallest and second smallest elemetns in this subarray

samoan + 0 comments Oh that make sense

samoan + 0 comments Maybe it is because I am think of the number rather then the binary version of it.

JimB6800 + 0 comments Nice algorithm.

Note: If you're using Java and running into timing issues, do not use one of the collections classes for implementing your stack. Use a primative

`int[]`

and a "top" index - much faster.procliton + 0 comments [deleted][deleted] + 0 comments Thank you very much !!!!

ksa_karan97 + 0 comments I got what you are trying to say. Can you please explain as to how this approach gives minimum pair of integers?

BugshotGG + 6 comments I think we can further simplify the above boolean function (^ is for XOR):

`(((A B) ^ (A + B)) (A ^ B)) = apply A ^ B = (A'B) + (A B') ( ((A B)' (A + B)) + ((A B) (A + B)')) (A ^ B)) = apply DeMorgan law (X+Y+...)'=X'Y'Z'... and (XYZ...)'=X'+Y'+... ( ((A' + B') (A + B)) + ((A B) (A' B'))) (A ^ B)) = apply Distributive Law X(Y+Z) = XY + XZ (A'A + A'B + AB' + BB' + AA' + BB') (A ^ B) = apply X+X=X, XX=X (A'B + AB') (A ^ B) = (A ^ B) (A ^ B) = A ^ B = A xor B`

So we get the same result by just using a simple

**A XOR B**. Is the above simplifacation correct? Can anyone confirm that?hahaha2009 + 1 comment I agree that the entire logical operation can be simplified down to A XOR B because:

`1. if you expand A ^ B you get exactly (A & B) ^ (A | B) 2. Idempotent laws states that C & C = C 3. so to save calculation time we can reduce the operation down to finding the max of what A ^ B is.`

BTANguyen + 0 comments Simplify proof

- Since (A ^ B) = (A & B) ^ (A | B)

Substitute (A ^ B)

(((A & B) ^ (A | B)) & (A ^ B)) = (((A & B) ^ (A | B)) & ((A & B) ^ (A | B)))

- Since X & X = X

((A & B) ^ (A | B)) & ((A & B) ^ (A | B)) = (A & B) ^ (A | B)

And (A & B) ^ (A | B) = A ^ B --- first equation

Therefore

(((A & B) ^ (A | B)) & (A ^ B)) = A ^ B

kushalsengar_si1 + 0 comments yes u r right

Anirudh_K + 0 comments YES IT IS :)

sebastian_keller + 0 comments I came to the same result. When there are only 2 inputs A and B, you can also build a truth table to show that (((A & B) ^ (A | B)) & (A ^ B)) = A ^ B ;)

jason_goemaat + 0 comments Or since they are all bitwise operations, just figure it out for 4 cases. If you look at the first part:

`// s = ((a & b) ^ (a | b)) ((0 & 0) ^ (0 | 0)) == 0 ^ 0 == 0 ((0 & 1) ^ (0 | 1)) == 0 ^ 1 == 1 ((1 & 0) ^ (1 | 0)) == 0 ^ 1 == 1 ((1 & 1) ^ (1 | 1)) == 1 ^ 1 == 0`

So you do an equivalent of xoring a number and 'and' that with xoring the number.

pujita_tipnis + 0 comments Yep I agree. Did the same :)

dxin2 + 1 comment **Another way to think about this problem:**1.Naive approach:

`Search all subsequences, check min0 and min1 where 0< min0 < min1 < data[i] to maximize y=min0^min1(simplified version of the original AND-XOR-OR expression).`

2.How much time this takes?

`o(n^2)`

3.Once the beginning element of the intervel is no longer min0 or min1, then we can break the loop and move on.

`e.g. with data 9 6 3 5 2, we check 9/6,9/6/3 and we don't need to check 9/6/3/5 and 9/6/3/5/2 any more and move on to 6/3, 6/3/5.... because the results will be the same.`

4.How much difference does not make?

`Best case, the input is sorted in decending order, then it's O(n); Worst case, if the input is sorted in acending order, then it's still O(n^2)`

5.Can we break the loop earlier?

`What about we pre-process the data, mark if the data is smaller than everything to the right of it? If we have reached the smallest value amont the rest of the sequence, we can break.`

6.Is it good?

`No, consider case: 2 3 4 5 6 7 1, still O(n^2);`

7.Anything that works?

`Since each time we expand the interval to the right, our min0 and min1 updates if and only if the newly checked value is smaller than either or both of them. So if we knew where that is, we can look it up and jump to it.`

8.psudocode:

`let n be number of elements let v be data let min0 and min1 be smallest and second smallest value between interval [i,j] for i=1:n-1 for j=i+1:n update min0,min1 using v[j]; if v[i] does not equal to min0 or min1 break the j loop;// rule #3 above jump j to location l where v[l]<v[j] and j<l<n`

9.How do we know l?

`http://stackoverflow.com/questions/9493853/given-an-array-find-out-the-next-smaller-element-for-each-element`

10.Fast enough?

`For each i(start of the interval), the j(end of interval) won't jump more than twice, because rule #3 will kick in and break the loop and move on. Then this should be O(n), so is the subroutine to calculate the l table, so O(n) overall`

vipulvikram3499 + 0 comments Thanks.

ksinghyadav + 3 comments Solution in C++:

#include<iostream> #include<stack> #include<vector> using namespace std; int main() { vector <long int> v; stack <long int> s; long int temp,i,n; long long max_xor=0,min_xor; cin>>n; for(i=0;i<n;i++) { cin>>temp; v.push_back(temp); } for(i=0;i<n;i++) { while(!s.empty()) { min_xor=v[i]^s.top(); if(min_xor>max_xor) max_xor=min_xor; if(v[i]<s.top()) s.pop(); else break; } s.push(v[i]); } cout<<max_xor<<endl; }

grdaukiya1996 + 0 comments thank u so much for cpp solution

CiPHeR33 + 0 comments what's the logic behind this?

claudiocidade + 0 comments Here is the C# implementation:

using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void Main(String[] args) { uint n = uint.Parse(Console.ReadLine()); uint[] v = Array.ConvertAll(Console.ReadLine().Split(' '), uint.Parse); Stack<uint> s = new Stack<uint>(); long max = 0; for (int i = 0; i < n; i++) { while (s.Any()) { uint c = s.Peek() ^ v[i]; if (c >= max) { max = c; } if (v[i] < s.Peek()) { s.Pop(); } else { break; } } s.Push(v[i]); } Console.WriteLine(max); } }

yikes + 9 comments I cannot get test cases 17, 19, 23 Test case 17: Expected = 262143 Actual = 262141 Test case 19: Expected = 65535 Actual = 65534 Test case 23: Expected = 262141 Actual = 262140

Here is my code, any input is appreciated:

`public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner in = new Scanner(System.in); int count = in.nextInt(); int arr[] = new int[count]; Stack<Integer> stack = new Stack<Integer>(); int currS1 = 0; int maxS1 = 0; arr[0] = in.nextInt(); stack.push(0); for (int i = 1; i < count; i++) { arr[i] = in.nextInt(); currS1 = arr[i] ^ arr[i - 1]; maxS1 = Math.max(currS1, maxS1); while (!stack.empty() && arr[stack.peek()] > arr[i]) { int top = stack.pop(); if (i != top + 1) { currS1 = arr[top] ^ arr[i]; maxS1 = Math.max(currS1, maxS1); } } stack.push(i); } while(!stack.empty()) { int top = stack.pop(); if (stack.empty()) { break; } int peek = stack.peek(); currS1 = arr[top] ^ arr[peek]; maxS1 = Math.max(currS1, maxS1); } System.out.println(maxS1); }`

diksha0207 + 1 comment Did you figure it out? I am facing the same problem.

prasoontrivedi + 0 comments Any progress? I am getting the same WA

BugshotGG + 0 comments I am getting the same wrong answers. Any ideas?

Chaitanya_Shah + 1 comment Me too :)

prasoontrivedi + 0 comments Any progress? same WA for me too!

prasoontrivedi + 0 comments How did you calculate your answer ie. how did u feed such a large input to ur program?

prasoontrivedi + 2 comments I checked test case 19 , and the only values that could produce 65535 were 97799 and 98808...Now if one opens the input data and does a simple Ctrl+F for the values, it seems as if the test case is wrong. Please confirm!

mryux + 0 comments actually there are 16000+ value pairs to get 65535, but the correct sequence is '96624 107397 99983', so there is a flaw in above code.

and it failed due to this sequence '96624, 107397, 99983, 108634, 105921, 95587'

arun1530siva + 0 comments I too faced the same problem and solved it check the below code

The idea is very simple for each item a[i] from the array check if it is greater than the top of stack... if yes then calc sum and add i to the stack if a[i] is lesser than top of stack then calc sum for each popped out element from stack until you find an element from stack which is lesser then a[i]

import java.io.*; import java.util.*; public class Solution { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] a = new int[N]; //3 9 6 4 5 2 10 11 12 1 for (int i = 0; i < a.length; i++) { a[i] = sc.nextInt(); } Stk stk1 = new Stk(N); int s = 0; int min = 0; int max = 0; min = a[0]; stk1.push(0); for(int i=1;i<N;i++){ if(a[stk1.peep()]<a[i]) { int m = sum(a[stk1.peep()], a[i]); if(m>max) max=m; stk1.push(i); } else if(a[stk1.peep()]>a[i]){ while(stk1.peep()!=-99 && a[stk1.peep()]>a[i]){ int m = sum(a[stk1.pop()], a[i]); if(m>max) max=m; } if(stk1.peep()!=-99){ int k = a[stk1.peep()]; int m = sum(k, a[i]); if(m>max) max=m; } stk1.push(i); } } System.out.println(max); } public static int sum(int a , int b) { return (((a&b)^(a|b))&(a^b)); } } class Stk { private int[] stkArr = null; private static int[] stkMaxArr = null; private static int maxPointer = 0; private int currentPointer = -1; private int size = 0; private int total = 0; public Stk(int size) { super(); this.size = size; stkArr = new int[size]; } public void push(int x) { currentPointer++; stkArr[currentPointer] = x; total = total + x; } public int getTotal() { return total; } public int pop() { int val = stkArr[currentPointer]; stkArr[currentPointer] = 0; currentPointer--; total = total - val; return val; } public int peep() { if (currentPointer > -1) return stkArr[currentPointer]; else return -99; } public int getCurrentPointer() { return currentPointer; } public int getSize() { return size; } public int getMax() { return stkMaxArr[maxPointer]; } }

ace_pocket + 1 comment your checking only in one direction just reverse the array and apply same algo again you'll get ac

douaaatouailaa + 0 comments i have only one case failing 16 any ideas

parthade + 0 comments [deleted]code_99 + 0 comments could you explain the logic by example?????

job4year + 2 comments If the stack is empty just push the element else If an element is smaller than the top of the stack then take xor with the top of the stack and pop the element until element become greater than the top of the stack. if an element is greater than the top of the stack take xor with top of the stack and push it. Really easy implementation. If any doubt, ping me :)

rishabh0_9 + 0 comments Ok , i got it .. but can you tell me how you have got the idea of this approach?

ashwiniabhishek1 + 0 comments I am not able to understand it,Please explain more elaborately or atleast give some other resource..

manan1 + 1 comment I'm getting n^2 runtime. Any way to do this faster?

DragoaAsked to answer + 1 comment Alright, the big trick to this one is trying to understand what values you can actually check from any given number, and trying to devise a method of figuring this out while you read the numbers in to manage it in roughly O(n).

First point of advice, is your going to want to use a stack. Should be obvious from where you are, but I tried a bunch of other solutions before I found the stack based one.

Second is what values can you actually check against a new input value? Given the smallest value restriction, the number of valid values it can be checked against is going to be harshly limited, and there is a way you can use that to your advantage to reduce the number of checks you need to the bare minimum. You'll want to break this down into a few cases: What does it mean when you read in a number larger then the last number? Smaller? Equal?

the_dark_kai + 0 comments This insight was extremely helpful. Just revealing enough to get us going. Great work !

vibhor3 + 1 comment testcase 5:-

the last two numbers give the operations si's result as 131809270 , shouldn't this be the answer. A quick response would be very much appreciated . The answer in testcase is a lesser number than this.The last numbers fall in range [n-1,n] too

SOURABHs23 + 0 comments not able to understand the ques can someone help me

malharjajoo + 0 comments These stack based solutions are hard to identify. But once spotted, they lead to quite elegant solutions.

Sort 104 Discussions, By:

Please Login in order to post a comment