Beautiful Arrangement


  • 0

    Click here to see the full article post


  • 0

    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 end-to-start 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 position i (from left end, give or take).


  • 0
    A

    Space complexity seems incorrect. We're using just one array of O(n) size all 3 approaches.


  • 0
    P

    use || instead of && in 1st solution


  • 0
    G

    Approach #3 got TLE in Python. And a return statement is needed in function calculate.


  • 1
    A

    Approach #3 is TLE for Python. Please fix


  • 0
    W

    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 condition

    Please help clarify


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.