Commit1123fd7

authored

Create 0779-k-th-symbol-in-grammar.kt

1 parent9ce8a27 commit1123fd7Copy full SHA for 1123fd7

File tree

+33

-0

lines changed

+33

-0

lines changed

Lines changed: 33 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,33 @@`
	`1`	`+classSolution {`
	`2`	`+funkthGrammar(n:Int,k:Int):Int {`
	`3`	`+var cur=0`
	`4`	`+var left=1`
	`5`	`+var right=2.0.pow(n-1).toInt()`
	`6`	`+`
	`7`	`+ repeat (n-1) {`
	`8`	`+val mid= (left+ right)/2`
	`9`	`+if (k<= mid) {`
	`10`	`+ right= mid`
	`11`	`+ }else {`
	`12`	`+ left= mid+1`
	`13`	`+ cur=if (cur==1)0else1`
	`14`	`+ }`
	`15`	`+ }`
	`16`	`+`
	`17`	`+return cur`
	`18`	`+ }`
	`19`	`+}`
	`20`	`+`
	`21`	`+// another solution using the same thought but different way of coding it`
	`22`	`+classSolution {`
	`23`	`+funkthGrammar(n:Int,k:Int):Int {`
	`24`	`+if (n==1)return0`
	`25`	`+if (k%2==0)returnif (kthGrammar(n-1, k/2)==0)1else0`
	`26`	`+elsereturnif (kthGrammar(n-1, (k+1)/2)==0)0else1`
	`27`	`+ }`
	`28`	`+}`
	`29`	`+`
	`30`	`+// another solution, recommend reading https://leetcode.com/problems/k-th-symbol-in-grammar/solutions/113705/java-one-line/ for explanation`
	`31`	`+classSolution {`
	`32`	`+funkthGrammar(n:Int,k:Int)=Integer.bitCount(k-1)and1`
	`33`	`+}`

Comments

(0)