Not best, but interesting, Golang, O(n^2) time on worst case, O(n) space


  • 0
    F

    the basic idea is that creating a tree, each path in the tree is a subset of numbers satisfying the condition.
    The case [1,2,3,4,5,6,24], it will create a tree:

    1 ---> 2 ------> 4 --------|
     |     |                  \|/
     |     \-------> 6 -----> 24
     |---> 3--------/|\
     |-> 5
    

    and find the longest path(s), so the result should be [1,2,4,24] OR [1,2,6,24] OR [1,3,6,24]

    
    
    import "sort"
    import "fmt"
    
    type Node struct{
        val int
        children []*Node
    }
    
    func add(n, toAdd *Node) {
        if n.val==toAdd.val{
            //remove cycle
            return
        }
        //assumed v % n.val ==0
        count := 0
        for _,c := range n.children{
            if toAdd.val % c.val == 0{
                add(c, toAdd)
                count+=1
            }
        }
        if count > 0{
            return
        }
        //fmt.Printf("added %d to %d \n",toAdd.val,  n.val)
        n.children = append(n.children,toAdd)
    }
    
    func visit(n *Node, path []int) ([]int, []int){
        path = append(path, n.val)
        var ret []int = nil
        if len(n.children)==0{
            //leaf
            ret = make([]int, len(path))
            copy(ret, path)
        }else{
            for _,c := range n.children{
                var r []int = nil
                path,r =  visit(c, path)
                if ret==nil || len(r)>len(ret){
                    ret = make([]int, len(r))
                    copy(ret, r)
                }
            }
        }
        path = path[:len(path)-1]
        return path,ret
    }
    
    func largestDivisibleSubset(nums []int) []int {
        if len(nums)==0{
            return nil
        }
        sort.Ints(nums)
        hasOne := nums[0]==1
        root := &Node{1, make([]*Node,0)}
        i := 0
        if hasOne{
            i =1 
        }
        for ;i<len(nums);i++{
            add(root, &Node{nums[i], make([]*Node, 0)} )
        }
        
        //find the lognest path
        _,ret := visit(root, make([]int,0))
        if !hasOne{
            return ret[1:]
        }
        return ret
    }
    
    
    

Log in to reply
 

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