Minimum number of iterations

user_14542409 0
Viewed 258

We are given an array with numbers from ranging from 1 to n (no duplicates) where n = size of the array. We are allowed to do the following operation :
arr[i] = arr[arr[i]-1] , 0 <= i < n

Now, one iteration is considered when we perform above operation on the entire array. Our task is to find the number of iterations after we encounter a previously encountered sequence.

Constraints :  
a) Array has no duplicates
b) 1 <= arr[i] <= n , 0 <= i < n  
c) 1 <= n <= 10^6

Ex 1:

n = 5  
arr[] = {5, 4, 2, 1, 3}  

  
After 1st iteration array becomes : {3, 1, 4, 5, 2}  
After 2nd iteration array becomes : {4, 3, 5, 2, 1}  
After 3rd iteration array becomes : {2, 5, 1, 3, 4}  
After 4th iteration array becomes : {5, 4, 2, 1, 3}    
In the 4th iteration, the sequence obtained is already seen before  
So the expected output is 4.

This question was asked in one of job hiring tests, so I dont have any link to the question. There were 2 sample test cases given out of which I remember one which is given above. I would really appreciate any help on this question

P.S.
I was able to code the brute force solution, where in I stored all the results in a Set and then kept advancing to the next permutation. But it gave TLE

arrays algorithm c++
1 Answers

First, note that an array of length n containing 1, 2, ..., n with no duplicates is a permutation.

Next, observe that arr[i] := arr[arr[i] - 1] is squaring the permutation. That is, consider permutations as elements of the symmetric group S_n, where multiplication is composition of permutations. Then the above operation is arr := arr * arr.

So, in terms of permutations and their composition, the question is as follows:

You are given a permutation p (= arr).
Consider permutations p, p^2, p^4, p^8, p^16, ...
What is the number of distinct elements among them?

Now, to solve it, consider the cycle notation of the permutation. Every permutation is a product of disjoint cycles. For example, 6 1 4 3 5 2 is the product of the following cycles: (1 6 2) (3 4) (5). In other words, every application of this permutation:

  • moves elements at positions 1, 6, 2 along the cycle;
  • moves elements at positions 4, 3 along the cycle;
  • leaves element at position 5 in place.

So, when we consider p^k (take an identity permutation and apply the permutation p to it k times), we actually process three independent actions:

  • move elements at positions 1, 6, 2 along the cycle, k times;
  • move elements at positions 4, 3 along the cycle, k times;
  • leave element at position 5 in place, k times.

Now, take into account that, after d applications of a cycle of length d, it just returns all the respective elements to their initial places. So, we can actually formulate p^k as:

  • move elements at positions 1, 6, 2 along the cycle, (k mod 3) times;
  • move elements at positions 4, 3 along the cycle, (k mod 2) times;
  • leave element at position 5 in place.

We can now prove (using Chinese Remainder Theorem, or just using general knowledge of group theory) that the permutations p, p^2, p^3, p^4, p^5, ... are all distinct up to p^m, where m is the least common multiple of all cycle lengths. In our example with p = 6 1 4 3 5 2, we have p, p^2, p^3, p^4, p^5, and p^6 all distinct. But p^6 is the identity permutation: moving six times along a cycle of length 2 or 3 results in the items at their initial places. So p^7 is the same as p^1, p^8 is the same as p^2, and so on.

Our question however is harder: we want to know the number of distinct permutations not among p, p^2, p^3, p^4, p^5, ..., but among p, p^2, p^4, p^8, p^16, ...: p to the power of a power of two. To do that, consider all cycle lengths c_1, c_2, ..., c_r in our permutation. For each c_i, find the pre-period and period of 2^k mod c_i:

  • For example, c_1 = 3, and 2^k mod 3 look as 1, 2, 1, 2, 1, 2, ..., which is (1, 2) with pre-period 0 and period 2.

  • As another example, c_2 = 2, and 2^k mod 2 look as 1, 0, 0, 0, ..., which is 1, (0) with pre-period 1 and period 1.

In this problem, this part can be done naively, by just marking visited numbers mod c_i in some array.

By Chinese Remainder Theorem again, after all pre-periods are considered, the period of the whole system of cycles will be the least common multiple of all individual periods.

What remains is to consider pre-periods. These can be processed with your naive solution anyway, as the lengths of pre-periods here is at most log_2 n. The answer is the least common multiple of all individual periods, calculated as above, plus the length of the longest pre-period.

user_14887990
Related