Commit56f5b02

authored

1018 Binary Prefix Divisible By 5.py

1 parent5e56791 commit56f5b02Copy full SHA for 56f5b02

File tree

+52

-0

lines changed

+52

-0

lines changed

Lines changed: 52 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,52 @@`
	`1`	`+#!/usr/bin/python3`
	`2`	`+"""`
	`3`	`+Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i]`
	`4`	`+interpreted as a binary number (from most-significant-bit to`
	`5`	`+least-significant-bit.)`
	`6`	`+`
	`7`	`+Return a list of booleans answer, where answer[i] is true if and only if N_i is`
	`8`	`+divisible by 5.`
	`9`	`+`
	`10`	`+Example 1:`
	`11`	`+`
	`12`	`+Input: [0,1,1]`
	`13`	`+Output: [true,false,false]`
	`14`	`+Explanation:`
	`15`	`+The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10.`
	`16`	`+Only the first number is divisible by 5, so answer[0] is true.`
	`17`	`+Example 2:`
	`18`	`+`
	`19`	`+Input: [1,1,1]`
	`20`	`+Output: [false,false,false]`
	`21`	`+Example 3:`
	`22`	`+`
	`23`	`+Input: [0,1,1,1,1,1]`
	`24`	`+Output: [true,false,false,false,true,false]`
	`25`	`+Example 4:`
	`26`	`+`
	`27`	`+Input: [1,1,1,0,1]`
	`28`	`+Output: [false,false,false,false,false]`
	`29`	`+`
	`30`	`+Note:`
	`31`	`+1 <= A.length <= 30000`
	`32`	`+A[i] is 0 or 1`
	`33`	`+"""`
	`34`	`+fromtypingimportList`
	`35`	`+`
	`36`	`+`
	`37`	`+classSolution:`
	`38`	`+defprefixesDivBy5(self,A:List[int])->List[bool]:`
	`39`	`+"""`
	`40`	`+ brute force`
	`41`	`+ """`
	`42`	`+cur=0`
	`43`	`+ret= []`
	`44`	`+forainA:`
	`45`	`+cur= (cur<<1)+a`
	`46`	`+cur%=5`
	`47`	`+ifcur==0:`
	`48`	`+ret.append(True)`
	`49`	`+else:`
	`50`	`+ret.append(False)`
	`51`	`+`
	`52`	`+returnret`

Comments

(0)