Java: 3 Solutions From Brute Force to Math using the OEIS for help, expained
Method/Goals\nLet\'s evolve a solution starting from brute force and working our way towards an efficient O(n) time O(1) space solution. In Approach 1, we\'ll s
**Method/Goals**\nLet\'s evolve a solution starting from brute force and working our way towards an efficient O(n) time O(1) space solution. In _Approach 1_, we\'ll start with simulation. Then, we\'ll use a powerful tool, the Online Encyclopedia of Integer Sequences (OEIS) to get some ideas about what\'s happening here and confirm an intuition which we implement in _Approach 2_. Finally, we\'ll optimize that approach to arrive at a final _Approach 3_. There will be some math, but nothing beyond modular arithmetic and powers of 2. The goal of this is to show how to start with something that works but is slow, and work towards something that works, and works quickly.\n\n**Approach 1: Brute Force (Accepted)** We can start with brute force.  Compute the initial permutation, perform the operation once as described, and while the result does not match the original permutation, continue performing the operation successively. This is a perfect use case for the somewhat rare `do { ... } while (...)` loop.\n\n```\nclass Solution {\n\n    public int reinitializePermutation1(int n) {\n        final int halfN = (n >> 1);\n        int[] perm = initInOrder(n);\n        int ops = 0;\n        do {\n            int[] arr = new int[n];\n            for (int i = 0; i < n; ++i) {\n                final int halfI = (i >> 1); // faster divide by 2\n                if ((i & 1) == 0) { // faster mod 2\n                    arr[i] = perm[halfI];\n                } else {\n                    arr[i] = perm[halfI + halfN];\n                }\n            }\n            perm = arr;\n            ops++;\n        } while (!isInOrder(perm));\n        return ops;\n    }\n\n    private final int[] initInOrder(int n) {\n        final int[] perm = new int[n];\n        for (int i = 1; i < n; ++i) {\n            perm[i] = i;\n        }\n        return perm;\n    }\n\n    private final boolean isInOrder(int[] arr) {\n        for (int i = 0; i < arr.length; ++i) {\n            if (arr[i] != i) {\n                return false;\n            }\n        }\n        return true;\n    }\n\n}\n```\nThis leaves something to be desired.  And it\'s worst case O(n^2) for time and O(n) space for the extra array.  It feels a bit like shuffling cards in reverse, but that\'s about the extent of what I could figure out looking at it.  Then, I thought, "why not see if the [OEIS](https://oeis.org/) knows about this as a sequence?"  So I looked at the output for 2, 4, 6, 8, 10, 12, ... and did a search for the first few terms.  Sure enough, up pops https://oeis.org/A002326.  And the card shuffling intuition was right.  But there\'s an even more precise statement of the sequence:  "In other words, least m > 0 such that (2n)+1 divides (2^m)-1" (parentheses added for readability).  But, the OEIS sequence assumes inputs of n=0,1,2,3,4, etc.  We can do a bit of shuffling (pun intended, sorry not sorry) of variables to adapt this to our needs. That is, we\'re going to do some variable substitution so we can use our even inputs and our range of n to fit the sequence\'s inputs and figure out a way to use it.\n\nLet\'s say this sequence defines the smallest m > 0 such that (2k)+1 divides (2^m)-1, for k = 0, 1, 2, ... (in other words we are writing k here instead of n in the sequence formulation from the OEIS). We want to use inputs of n = 2, 4, 6, ... such that when n = 2, k = 0, when n = 4, k = 1, etc.  This means n = 2(k+1) = 2k+2, and n-1 = 2k+1.  So, by substituting, we can say we are seeking the smallest m > 0 such that n-1 divides (2^m)-1, for n = 2, 4, 6, 8, ... and this solves our problem.  Well, we could do some brute force math and start at m=1 and increase m until (2^m)-1 is divisible by n-1.  And then whatever m we find is our answer.  But n can be as large as 1000 and we don\'t know how large m can get.  We might need BigInteger here.  Maybe we can start with `long` for m < 64 and switch to BigInteger if we need it?  Because we know BigInteger is going to be pretty slow, maybe avoiding it whenever we can will be nice.\n\nNote that `(1L << 63)` overflows but then `(1L << 63) - 1` underflows back to `Long.MAX_VALUE` or 2^63 - 1. This means we can safely use `long` for `(1L << m) - 1` up to m=63, inclusive. The value 63 is based on `Long.SIZE - 1` as `Long.SIZE` is `64` (bits). So in other words, we can use `long` whenever `m < Long.SIZE`.\n\n**Approach 2: Brute Force Math (Accepted)**\n```\nclass Solution {\n\n    public int reinitializePermutation(int n) {\n        final long factor = n - 1; // 2n+1 in 0-based OEIS, we are 2-based\n        BigInteger biFactor = null; // if we need it\n        for (int m = 1; m <= n; m++) {\n            if (m < Long.SIZE) {\n                final long test = (1L << m) - 1; // 2^m - 1\n                if ((test % factor) == 0) {\n                    return m;\n                }\n            } else {\n                // we need the BigInteger factor, initialize it only once\n                if (biFactor == null) {\n                    biFactor = BigInteger.valueOf(factor);\n                }\n                final BigInteger test = BigInteger.ONE.shiftLeft(m).subtract(BigInteger.ONE);\n                if (test.remainder(biFactor).equals(BigInteger.ZERO)) {\n                    return m;\n                }\n            }\n        }\n        return -1;\n    }\n\n}\n```\nOkay, so it turns out, even with the optimization to use `long` instead of `BigInteger` whenever we can, this is barely faster than the brute force solution, even though it runs in O(n) time and uses O(1) space (if you consider BigInteger operations to use constant time and the BigInteger itself to use constant space, which it actually does not, more like O(log n) time per operation and O(log n) space as the internal representation grows larger). So, it might be more accurate to say that we are at O(n log n) time and O(log n) space. Maybe if we do some more math, we can speed this up and use less space.\n\nFirst we can see that we are looking for the smallest m > 0 such that (2^m)-1 is divisible by n-1.  But this is equivalent to saying that we seek the smallest m > 0 such that (2^m) is congruent to 1, modulo n-1.  In other words, find the smallest m > 0 such that (2^m) % (n-1) is 1.  And now we can use the fact that (a * b) % c is congruient to (a % c) * (b % c). Also, this is congruent to ((a % c) * b) % c. This is useful because it means we can track successive powers of two _modulo n - 1_.  That is, if n-1 is 9, we can track 2, 4, 8, _7_ [(2 x 8) % 9], _5_ [(2 x 7) % 9], ... instead of 2, 4, 8, 16, 32, ... and we won\'t need BigInteger or long anymore. To get the next `powerOfTwo` modulo (n - 1), we just multiply `powerOfTwo` by 2, and take the result mod (n - 1).\n\n**Approach 3: Faster Math (Accepted)**\n```\nclass Solution {\n\n    public int reinitializePermutation(int n) {\n        final int factor = n - 1;\n        if (factor < 2) {\n            return 1;\n        }\n        int powerOfTwo = 2;\n        int ops = 1;\n        while (powerOfTwo != 1) { // (mod n-1)\n            powerOfTwo = ((powerOfTwo << 1) % factor);\n            ops++;\n        }\n        return ops;\n    }\n\n}\n```\nThis is now actually O(n) and by using only int primitives, it runs much faster (0ms), and we have truly only used O(1) space.\n\nThanks for reading and I hope this was helpful (especially the **OEIS - Online Encyclopedia of Integer Sequences** if that is new to you - it\'s great for finding out more information about sequences).\n\nHappy problem solving!
['Math', 'Java']