Divisor Game using Golang

Today i try to solve this divisor game on leetcode, this problem is basic for dp programming, I solve this question using two methods, First one is without using any dynamic programming and second one by using dp.
 

Problem Statement:

divisor game


Solution 1: Without DP with 0ms Runtime:


func divisorGame(n int) bool {
flag := true
for n>0{
n--
if flag{
flag = false
continue
}
flag= true
}
return flag
}


Solution2: with DP with 8ms:

func divisor(n int, lstofInt map[int]bool) bool {
if n == 1 {
return false
}
if lstofInt[n] {
return lstofInt[n]
}
for i := 1; i < n; i++ {
if n%i == 0 {
if !divisor(n-i, lstofInt) {
lstofInt[n] = true
return true
}
}
}
lstofInt[n] = false
return lstofInt[n]
}

func divisorGame(n int) bool {
lstOfInt := make(map[int]bool, 0)
return divisor(n, lstOfInt)
}

Post a Comment

0 Comments