XorPuzzle

import java.util.*;

public class XorPuzzle {
  static int[] noAns = {-1};

  boolean order(int x, int y, int z) {
    return x <= y && y <= z;
  }

  public String checkData(int n, int[] a) {
    if (!order(1, a.length, 1 << n))
      return "a must containt between 1 and (2 ^ k) integers, inclusive.";

    for (int x : a)
      if (!order(0, 1, (1 << n) - 1))
        return "Each element of a must be between 0 and (2 ^ k) - 1, inclusive.";

    return "";
  }

  boolean unique(int[] a, int l, int r) {
    for (int i = l; i < r; ++i)
      for (int j = i + 1; j < r; ++j)
        if (a[i] == a[j])
          return false;
    return true;
  }

  public String checkAnswer(int n, int[] a, int[] ans, int[] refAns) {
    if (ans.length != refAns.length)
      return "The length of answer must exactly match the expected one.";

    if (refAns.length == 1)
      if (ans[0] == -1)
        return "";
      else
        return "Must be {-1}.";

    for (int x : ans)
      if (!order(0, x, (1 << n) - 1))
        return "Each element of ans must be between 0 and (2 ^ k) - 1, inclusive.";

    if (!unique(ans, 0, a.length) || !unique(ans, a.length, 2 * a.length))
      return "Elements in b and c must be unique.";

    for (int i = 0; i < a.length; ++i)
      if (a[i] != (ans[i] ^ ans[i + a.length]))
        return "xor of b[" + i + "] and c[" + i + "] is not equal to a[" + i + "]";

    return "";
  }

  int[] a, b, pa, c;

  void swp(int v, int u) {
      //amazing swap
      a[u] ^= a[v];
      a[v] ^= a[u];
      a[u] ^= a[v];

      int x = a[u], y = a[v];
      pa[x] ^= pa[y];
      pa[y] ^= pa[x];
      pa[x] ^= pa[y];
  }


  public int[] find(int n, int[] input) {
    assert(checkData(n, input) == "");

    int xor = 0;
    for (int x : input)
      xor = xor ^ x;

    if (input.length == (1 << n) && xor != 0)
      return noAns;

    a = new int[1 << n];
    pa = new int[1 << n];
    b = new int[1 << n];
    c = new int[1 << n];

    for (int i = 0; i < (1 << n); ++i)
      a[i] = b[i] = pa[i] = i;

    for (int i = 0; i < input.length; ++i)
      c[i] = input[i];
    if (xor != 0)
      c[input.length] = xor;

    //solution always exist at this point

    for (int i = 0; i < (1 << n); ++i) {
      int u = i;
      while ((a[u] ^ b[u]) != c[u]) {

        int v = -1;
        /*
        for (int j = 0; j < (1 << n); ++j)
          if ((a[j] ^ b[u]) == c[u])
            v = j;
        */

        v = pa[b[u] ^ c[u]];

        assert(v != pa[b[u] ^ c[u]]);

        swp(u, v);

        if (v > i)
          break;
        else {
          //here it goes again
          b[v] ^= b[i + 1];
          b[i + 1] ^= b[v];
          b[v] ^= b[i + 1];
          u = v;
        }
      }
    }

    int[] ans = new int[2 * input.length];
    for (int i = 0; i < input.length; ++i) {
      ans[i] = a[i];
      ans[i + input.length] = b[i];
    }

    /*
    for (int i = 0; i < input.length; ++i) {
      System.out.print(a[i]);
      System.out.print(" ");
      System.out.print(b[i]);
      System.out.print(" ");
      System.out.println(c[i]);
    }
    */

    return ans;
  }

  public static void main(String[] args) {
    XorPuzzle solver = new XorPuzzle();
    int n = 2;
    int[] a = {2, 2, 0, 0};
    solver.find(n, a);
  }
};