[java] Simulate an arbitrary element iteratively, until it reaches the original position. O(n)
It can be proved that as long as an element returns to its original position. The whole array will be the same again. Thus time complexitiy is O(n) if you do th
It can be proved that as long as an element returns to its original position. The whole array will be the same again. Thus time complexitiy is O(n) if you do the simulation of an arbitrary element, say 1.\n\n```\nclass Solution {\n    public int reinitializePermutation(int n) {\n        /* in case n can be odd. but not required in the question.\n        if (n%2==1){\n            reinitializePermutation(n+1);\n        }\n        */\n        int ops=0;\n        int pos=1;\n        while (pos!=1 || ops==0){\n            ops++;\n            if (pos <= n/2-1){ //n must be even\n                pos =pos*2;\n            } else {\n                pos=2*(pos-(n/2-1))-1;\n            }\n        }\n        return ops;\n    }\n\n}\n```\n\nIn case you need some concrete examples to come up with the algorithm by your own. I am attaching some.\n\n/*\n0 1 2 3 4\n0 3 1 4 2\n0 4 3 2 1\n0 2 4 1 3\n0 1 2 3 4\n\n5-4\n\n0 1 2 3 4 5\n0 3 1 4 2 5\n0 4 3 2 1 5\n0 2 4 1 3 5\n0 1 2 3 4 5\n\n6-4\n\n0 1 2 3 4 5 6\n0 4 1 5 2 6 3\n0 2 4 6 1 3 5\n0 1 2 3 4 5 6\n\n7-3\n\n0 1 2 3 4 5 6 7\n0 4 1 5 2 6 3 7\n0 2 4 6 1 3 5 7\n0 1 2 3 4 5 6 7\n\n8-3\n\n0 1 2 3 4 5 6 7 8\n0 5 1 6 2 7 3 8 4\n0 7 5 3 1 8 6 4 2\n0 8 7 6 5 4 3 2 1\n0 4 8 3 7 2 6 1 5\n0 2 4 6 8 1 3 5 7\n0 1 2 3 4 5 6 7 8\n\n9-6\n0 1 2 3 4 5 6 7 8 9\n0 5 1 6 2 7 3 8 4 9\n0 7 5 3 1 8 6 4 2 9\n0 8 7 6 5 4 3 2 1 9\n0 4 8 3 7 2 6 1 5 9\n0 2 4 6 8 1 3 5 7 9 \n0 1 2 3 4 5 6 7 8 9\n\n10-6\n\n
[]