XOR of permutation of strings
This is a competitive programming question I came across, but couldn't solve.
The question gives two inputs: two strings A & B of length N, consisting of only 1s and 0s.
Each of these strings can be permuted and then XORed. The question asks to find the total number of distinct XORs that can be achieved.
For eg: Given N = 2, A = 00, B = 10
A = 00, B = 10, A^B = 10
A = 00, B = 01, A^B = 01
A = 00, B = 10, A^B = 10 | Swap the zeroes xD
A = 00, B = 01, A^B = 01 |
Thus the answer would be 2. But given that N <= 10^5, it is impossible to permute the strings and calculate each value with a time limit of 1 second.
Any help is appreciated!
The question gives two inputs: two strings A & B of length N, consisting of only 1s and 0s.
Each of these strings can be permuted and then XORed. The question asks to find the total number of distinct XORs that can be achieved.
For eg: Given N = 2, A = 00, B = 10
A = 00, B = 10, A^B = 10
A = 00, B = 01, A^B = 01
A = 00, B = 10, A^B = 10 | Swap the zeroes xD
A = 00, B = 01, A^B = 01 |
Thus the answer would be 2. But given that N <= 10^5, it is impossible to permute the strings and calculate each value with a time limit of 1 second.
Any help is appreciated!
Try bigger sizes and see if you can find a pattern.
Btw, a simple way to xor would be '0' + (a[i] != b[i]);
Btw, a simple way to xor would be '0' + (a[i] != b[i]);
Last edited on
Topic archived. No new replies allowed.