Commitebc1f0f

committed

use base conversion to solve power of three

1 parenta87a7d8 commitebc1f0fCopy full SHA for ebc1f0f

File tree

-0

lines changed

-0

lines changed

Lines changed: 8 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -11,6 +11,14 @@`
`11`	`11`	`*/`
`12`	`12`
`13`	`13`	`publicclassPowerOfThree {`
	`14`	`+//then I turned to the Editorial solution, it's pretty elegant to use base conversion which can be easily extended to any radix k`
	`15`	`+//Idea: for a number in base 10, if it's power of 10, then it must be in this format: 10, 100, 1000... with a leading one and all trailing zeros`
	`16`	`+//similarly, if a number is power of 3, then in its base 3 format, it must be in this format as well: 10, 100, 1000, 1000...`
	`17`	`+//some Java built-in function could help us along the way:`
	`18`	`+publicbooleanisPowerOfThree_base_conversion(intn){`
	`19`	`+returnInteger.toString(n,n).matches("^10*$");`
	`20`	`+ }`
	`21`	`+`
`14`	`22`	`//it turns out they're using a trick to solve this question without using a loop: find the max possible integer that is a power of 3, then do modulor with this number`
`15`	`23`	`publicbooleanisPowerOfThree_without_loop(intn) {`
`16`	`24`	`return (n >0 &&1162261467 %n ==0);`

Comments

(0)