Commit40e7a58

authored

Update 0343-integer-break.kt

1 parent0ac8f44 commit40e7a58Copy full SHA for 40e7a58

File tree

+19

-2

lines changed

+19

-2

lines changed

Lines changed: 19 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,5 +1,5 @@`
`1`	`1`	`/*`
`2`		`-* DP solution`
	`2`	`+* DP solution O(n^2) time and space`
`3`	`3`	`*/`
`4`	`4`	`classSolution {`
`5`	`5`	`funintegerBreak(n:Int):Int {`
`@@ -19,7 +19,7 @@ class Solution {`
`19`	`19`	`}`
`20`	`20`
`21`	`21`	`/*`
`22`		`-* DFS + memoization solution`
	`22`	`+* DFS + memoization solution O(n^2) time and space`
`23`	`23`	`*/`
`24`	`24`	`classSolution {`
`25`	`25`	`funintegerBreak(n:Int):Int {`
`@@ -40,3 +40,20 @@ class Solution {`
`40`	`40`	`return dfs(n)`
`41`	`41`	`}`
`42`	`42`	`}`
	`43`	`+`
	`44`	`+// Math solution O(n) time and O(1) space`
	`45`	`+classSolution {`
	`46`	`+funintegerBreak(n:Int):Int {`
	`47`	`+if (n<4)return n-1`
	`48`	`+`
	`49`	`+var res=1`
	`50`	`+var n2= n`
	`51`	`+while (n2>4) {`
	`52`	`+ res*=3`
	`53`	`+ n2-=3`
	`54`	`+ }`
	`55`	`+`
	`56`	`+ res*= n2`
	`57`	`+return res`
	`58`	`+ }`
	`59`	`+}`

Comments

(0)