[C++] Graph Thinking, O(N) | O(1)
You can try the Brute method(Simulation) on your own but thats not good enough for any \ninterview, neither will that help you understand this question in depth
You can try the Brute method(Simulation) on your own but thats not good enough for any \ninterview, neither will that help you understand this question in depth.\n\n------\n\n**Better than Brute but still not optimal**\n\nIn this method we are making a graph consisting of:\n\n1) Nodes : i values\n2) Edges : from curr i to new i \n\t2.1) even then i/2\n\t2.2) odd then (n-1+i)/2\n\nYou can quickly see that this will form a graph like structure, where each node will have\nonly 1 out going edge and 1 incoming egde. For example try n = 16\n\n``0 -> 0``\n``1 -> 2 -> 4 -> 8 -> 1``\n``3 -> 9 -> 12 -> 6 -> 3``\n``5 -> 10 -> 5``\n``7 -> 11 -> 13 -> 14 -> 7``\n\nNotice these are all loops of certain lengths. This is important because we need to come\nback to our original permutation and the longest len loop will help us do this. \n\nI dont have the proof for this but I noticed that the **loop containing 1 will always be \nthe longest** and will be the **LCM of all the other loop lengths**\n\nfor n = 16 \nLCM(1, 2, 4) = 4 (which is our answer)\n\n```\n/* \n\tTime  : O(N)\n    Space : O(N)\n*/\nint reinitializePermutation(int n)\n{\n\tvector<int> graph(n);\n\tfor(int i=0;i<n;++i)\n\t\tgraph[i] = (i&1) ? (n-1+i)/2 : i/2;\n\n\tint curr = graph[1];\n\tint ans = 1;\n\twhile(curr != 1)\n\t{\n\t\tcurr = graph[curr];\n\t\tans++;\n\t}\n\n\treturn ans;\n}\n```\n\n------\n\n**Optimised method**\n\nFrom the above implementation we learnt that we can simply track the loop startig from\n1 and not worry about the other loops as they dont contribute to our answer.\n\n```\n/* \n\tTime  : O(N)\n    Space : O(1)\n*/\nint reinitializePermutation(int n)\n{\n\tint ans = 1;\n\tint curr = n/2; // we start at node 1 itself { (n-1+1)/2 }\n\twhile(curr != 1)\n\t{\n\t\tcurr = (curr&1) ? (n-1+curr)/2 : curr/2;\n\t\tans++;\n\t}\n\n\treturn ans;\n}\n\n```\n\n*Hope this helped you get a better understanding of this problem. Upvote if it helped*
[]