tag:blogger.com,1999:blog-4115025577315673827.post2169767332622094066..comments2020-02-15T12:41:34.617+05:30Comments on CSE Blog - quant, math, computer science puzzles: Evenly Spaced Ones in Binary StringPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-4115025577315673827.post-7443027225139410562013-12-17T09:55:02.961+05:302013-12-17T09:55:02.961+05:30This will only find the consecutive ones. The ques...This will only find the consecutive ones. The question I guess asks for any set of three ones equally spaced, whether there exists one between them or not. Sakshihttps://www.blogger.com/profile/05799411739751219076noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-58737766980616592312013-02-06T23:37:18.489+05:302013-02-06T23:37:18.489+05:30I think this can be done in O(n) as follows
let&#...I think this can be done in O(n) as follows<br /><br />let's say i have the bit string in a array str[].<br /><br />public class EvenlySpacedOnes {<br /><br /> <br /> public static void main(String[] args) {<br /> int prev=-1;<br /> <br /> String str="";<br /> <br /> InputStreamReader inp = new InputStreamReader(System.in);<br /> BufferedReader br = new BufferedReader(inp);<br /> try {<br /> str=br.readLine();<br /> } catch (IOException e) { <br /> e.printStackTrace();<br /> }<br /> <br /> for(int i=0;i<str.length();i++){<br /> <br /> if(str.charAt(i)=='1'){<br /> if(prev!=-1){<br /> int next=2*i-prev;<br /> if(next<str.length()){<br /> if(str.charAt(next)=='1'){<br /> System.out.println(prev+" "+i+" "+next);<br /> }<br /> else<br /> prev=i;<br /> }<br /> else<br /> prev=i;<br /> }<br /> else<br /> prev=i;<br /> }<br /> }<br /> }<br />}<br /><br />Sobhanhttps://www.blogger.com/profile/07432769964940457366noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55283357273089240192013-02-06T23:09:15.551+05:302013-02-06T23:09:15.551+05:30I think this can be done in O(n).
Lets start sca...I think this can be done in O(n). <br /><br />Lets start scanning the bits one by one from the left. I stop When I find the 1st '1'. Let's say I store this index in a variable called a. I continue my search for the next '1'. I find out the distance of the two 1's (subtraction of indices of current and previous '1'). Suppose the distance is coming out to be 'd'. I will just chk whether a+dth bit is '1' or not. If it is '1' I just found a solution. Otherwise I store the index of the current '1' and move on to search the next '1'. Sobhanhttps://www.blogger.com/profile/07432769964940457366noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-74576460118683753052013-01-29T18:56:35.372+05:302013-01-29T18:56:35.372+05:30Great solution. Thanks.
Adding to what you said,...Great solution. Thanks. <br /><br />Adding to what you said, the question just asks to find one set of evenly spaced 1s. Hence, even if the number of b's for which the coefficient is > 1 is large, in first scan for one b, you will find the set of 1s that you want to. :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-83755907111220258062013-01-19T12:15:27.830+05:302013-01-19T12:15:27.830+05:301. Make a list L of positions of 1 in the string. ...<b>1.</b> Make a list L of positions of 1 in the string. This is O(n).<br /><br /><i>The problem is now to find an arithmetic progression of length 3 in L.</i><br /><br /><b>2.</b> Make a polynomial p with terms xᵏ for each k in L. This is O(n).<br /><br /><b>3.</b> Find the polynomial q = p² using the Fast Fourier Transform. This is O(n(log n)).<br /><br /><i>In this new polynomial q, the coefficient of any x²ᵇ for b in L is exactly the number of pairs (a,c) in L such that a+c=2b. One such pair is always (b,b) (with coefficient at least 1), but if there is any other pair (a,c), then the coefficient is at least 3, from (a,c) and (c,a).</i><br /><br /><b>4.</b> Scan the coefficients of the terms x²ᵇ looking for values greater than 1. This is O(n).<br /><br /><i>If none are greater than 1 then there are no evenly spaced 1s. If there is b in L for which the coefficient of x²ᵇ is greater than 1, then we know there is some pair (a,c) for which a+c=2b.</i><br /><br /><b>5.</b> Try each a in L (the corresponding c is 2b-a) and check if there is a 1 at position 2b-a in S. This will give our solution. This step is O(n).JDGMhttps://www.blogger.com/profile/11829357060109505064noreply@blogger.com