Python BFS solution


  • 2
    D
    class Solution(object):
        def countArrangement(self, N):
            """
            :type N: int
            :rtype: int
            """
            
            counter = 0
            queue = []
            x = []
            queue.append(x);
            while(len(queue) >0):
                x = queue.pop()
                if len(x) == N:
                    counter+=1
                else:
                    for i in range(1,N+1):
                        y = x[:]
                        if i not in y:
                            if (i % (len(y)+1) ==0) or ((1+len(y)) % i ==0):
                                y.append(i)
                                queue.append(y)
            return counter
            ```

  • 0
    Z

    Can't pass the last testcase, I got TLE.


  • 1

    Did that actually get accepted? I consistently get Time Limit Exceeded for it. I do get it accepted (in over 6000ms) if I change pop(0) to pop() (there's really no point in going BFS, and pop(0) is just slow).

    Bit shorter and faster (usually under 4000ms) and not changing the meaning of i (the problem text uses it for the positions, you used it for the numbers, which is confusing).

    def countArrangement(self, N):
        counter = 0
        pool = [[]]
        while pool:
            a = pool.pop()
            if len(a) == N:
                counter += 1
            else:
                for x in xrange(1, N + 1):
                    if x not in a:
                        i = len(a) + 1
                        if x % i == 0 or i % x == 0:
                            pool.append(a + [x])
        return counter

  • 0
    D

    @StefanPochmann No its failing for N = 14 and 15. Changing to pop() from pop(0) helped in passing the test for N=14. Now only N =15 is failing.


  • 0
    D
    This post is deleted!

  • 0
    P

    @StefanPochmann

    Is python slow on leetcode? why are there so many accepted java solutions?


Log in to reply
 

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