Commitac8783d

authored

Create minimum-jumps-to-reach-end-via-prime-teleportation.py

1 parent4641b40 commitac8783dCopy full SHA for ac8783d

File tree

+61

-0

lines changed

+61

-0

lines changed

Lines changed: 61 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,61 @@`
	`1`	`+# Time: precompute: O(r)`
	`2`	`+# runtime: O(nlogr)`
	`3`	`+# Space: O(r + nlogr)`
	`4`	`+`
	`5`	`+importcollections`
	`6`	`+`
	`7`	`+`
	`8`	`+# number theory, bfs`
	`9`	`+deflinear_sieve_of_eratosthenes(n):# Time: O(n), Space: O(n)`
	`10`	`+primes= []`
	`11`	`+spf= [-1]*(n+1)# the smallest prime factor`
	`12`	`+foriinxrange(2,n+1):`
	`13`	`+ifspf[i]==-1:`
	`14`	`+spf[i]=i`
	`15`	`+primes.append(i)`
	`16`	`+forpinprimes:`
	`17`	`+ifi*p>norp>spf[i]:`
	`18`	`+break`
	`19`	`+spf[i*p]=p`
	`20`	`+returnspf`
	`21`	`+`
	`22`	`+`
	`23`	`+MAX_NUM=10**6`
	`24`	`+SPF=linear_sieve_of_eratosthenes(MAX_NUM)`
	`25`	`+classSolution(object):`
	`26`	`+defminJumps(self,nums):`
	`27`	`+"""`
	`28`	`+ :type nums: List[int]`
	`29`	`+ :rtype: int`
	`30`	`+ """`
	`31`	`+adj=collections.defaultdict(list)`
	`32`	`+fori,xinenumerate(nums):`
	`33`	`+whilex!=1:`
	`34`	`+p=SPF[x]`
	`35`	`+whilex%p==0:`
	`36`	`+x//=p`
	`37`	`+adj[p].append(i)`
	`38`	`+dist= [-1]*len(nums)`
	`39`	`+dist[0]=0`
	`40`	`+q= [0]`
	`41`	`+whileq:`
	`42`	`+new_q= []`
	`43`	`+foriinq:`
	`44`	`+ifi==len(nums)-1:`
	`45`	`+returndist[-1]`
	`46`	`+fordiin (-1,+1):`
	`47`	`+ni=i+di`
	`48`	`+if0<=ni<len(nums)anddist[ni]==-1:`
	`49`	`+dist[ni]=dist[i]+1`
	`50`	`+new_q.append(ni)`
	`51`	`+p=nums[i]`
	`52`	`+ifSPF[p]!=porpnotinadj:`
	`53`	`+continue`
	`54`	`+forniinadj[p]:`
	`55`	`+ifdist[ni]!=-1:`
	`56`	`+continue`
	`57`	`+dist[ni]=dist[i]+1`
	`58`	`+new_q.append(ni)`
	`59`	`+deladj[p]`
	`60`	`+q=new_q`
	`61`	`+return-1`

Comments

(0)