Commitdc7fdc5

authored

Update number-of-integers-with-popcount-depth-equal-to-k-ii.py

1 parent5536ace commitdc7fdc5Copy full SHA for dc7fdc5

File tree

-5

lines changed

-5

lines changed

Lines changed: 7 additions & 5 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,4 @@`
`1`		`-# Time: precompute: O((logr)^2),, r = max(n)`
	`1`	`+# Time: precompute: O((logr) * log(logr) + log(r) (logr)), r = max(n)`
`2`	`2`	`# runtime: O(nlogr + max_k * n + nlogn + qlogn)`
`3`	`3`	`# Space: O(logr + max_k * n)`
`4`	`4`
`@@ -7,6 +7,10 @@ def popcount(x):`
`7`	`7`	`returnbin(x).count('1')`
`8`	`8`
`9`	`9`
	`10`	`+defceil_log2_x(x):`
	`11`	`+return (x-1).bit_length()`
	`12`	`+`
	`13`	`+`
`10`	`14`	`classBIT(object):# 0-indexed.`
`11`	`15`	`def__init__(self,n):`
`12`	`16`	`self.__bit= [0]*(n+1)# Extra one for dummy node.`
`@@ -32,10 +36,8 @@ def query(self, i):`
`32`	`36`	`foriinxrange(2,MAX_BIT_LEN+1):`
`33`	`37`	`D[i]=D[popcount(i)]+1`
`34`	`38`	`MAX_K=0`
`35`		`-prev=-1`
`36`		`-whileMAX_N!=prev:`
`37`		`-prev=MAX_N`
`38`		`-MAX_N=MAX_N.bit_length()`
	`39`	`+whileMAX_N!=1:# O(log*(MAX_N)) times`
	`40`	`+MAX_N=ceil_log2_x(MAX_N)`
`39`	`41`	`MAX_K+=1`
`40`	`42`	`classSolution(object):`
`41`	`43`	`defpopcountDepth(self,nums,queries):`

Comments

(0)