Beautiful Arrangement


Why is the permutation based solution significantly faster than the 3rd Backtracking solution? I submitted these solutions, and the 3rd solutions reports 110ms ~ 130ms, while the 2nd approach reports 50ms ~ 60ms. Neither solution implemented the from endtostart optimization. As far as I can see now, what the two solutions are doing are essentially the same: at each recursive depth
i
, we pick a number to be seated at positioni
(from left end, give or take).

Can someone please help clarify why input of N=3 should return 3?
Permutations of N=3: [123], [132], [213], [231], [321], [312]
According to problem statement, valid permutation is one such that either is true:
1. The number at the ith position is divisible by i.
2. i is divisible by the number at the ith position.From those 6 permutations, all 6 match the criteria. why is the answer 3?
[123] > i = 1, i = 2, i = 3 satisfies condition
[132] > i = 1 satisfies condition
[213] > i = 1, i = 2, i = 3 satisfies condition
[231] > i = 1, i = 3 satisfies condition
[321] > i = 1, i = 2, i = 3 satisfies condition
[312] > i = 1, i = 2 satisfies conditionPlease help clarify
