Minimum Distance Between Ones

 It's 10:05 in the evening, and I just solved a problem with 3 different ways (all through Python), why Python? Ehh, just because I wanted to, I could have done this with C++14 too.

So, the 1st approach got rejected due to TLE, the 2nd one passed all the Test Cases, but we are using Python, c'mon, I was about 27-29 lines long...so I decided to think more 'bout it and I tried to decrease the lines of code, I came up with an idea, and Voila! It passed all the Test Cases in the first go.

I have started explaining my code in CodeChef, because I thought I would be a good practice, and I have explained both of these codes, so I will just paste that explanation here, try if you can get the idea before seeing the solution, if not then try to understand the code first, without looking into the explanation part. I have my DBMS exam on 1'st Feb so most probably this was the one and only problem statement for today, now I think I will be getting some lectures and finish some more topics from it.

The first 2 codes are below:

t=int(input())

while(t):

    n=int(input())

    s=input()

    size=len(s)

    itr=0

    ls=[i if(elem=='1') else None for i,elem in enumerate(s)]

    while(itr<size):

        elem=s[itr]

        s_itr=itr

        chk=False

        upd=False

        if(elem=='1'):

            for i in range(itr+1,size):

                if(s[i]=='1'):

                    itr=i

                    upd=True

                    if((i-s_itr)%2!=0):

                        print(1)

                        chk=True

                        break

            if(chk==True):

                break

        if(upd==False):

            itr+=1

    if(chk!=True):

        print(2)

       

    ''' The below code was failing to pass the Time Constraints of the Problem '''

    # for i,c in enumerate(s):

    #     # Did i get a good case?

    #     chk=False

    #     if(c=='1'):

    #         for j in range(i+1,size):

    #             if(s[j]=='1'):

    #                 # Means I can now get the distance of this one with

                      # the first one

    #                 dist=j-i

    #                 if(dist%2!=0):

    #                     print(1)

    #                     chk=True

    #                     break

    #         if(chk==True):

    #             break

    # if(chk==False):

    #     # No best case found, then distance(minimum) will be 2

    #     print(2)

    t-=1

Explanation of above code:

The code shows 2 approaches, the first approach passes all the test cases and the second approach was failing the Time Constraints for the problem. The approach used in the second code was, I was iterating through the string, and whenever I found a '1', I compared it's index with all the ones after it and check the difference with the indices, anytime I will find an odd difference I will print 1 and get out of the loop bcz I got the best case, else the process will go on, and the problem was after comparing this index with the indices after it, I was then iterating normally and for every 0 I was checking if it is a '1', but this was a bad practice bcz if I can get to know that at which index will I get the next '1' so why do I have to traverse through so many elements to get to that '1', in the first algo I just took this problem and fixed it by using an iterator, so that I would just jump to the next index with '1' as the element instead of wasting time to traverse through all the 0's. I also made a code of just 7 lines which did the exact same thing but it is failing 1 test case because of Time Constraint. Cya...:)

The last code is below:

for _ in range(int(input())):

    n,s=int(input()),input()

    ls=list(filter(lambda x:x!=None,[i if(elem=='1') else None for i,elem

in enumerate(s)]))

    print(1 if 1 in [1 if((ls[j]-ls[0])%2!=0) else 2 for j in range(1,len(ls))]

else 2)

Explanation of above code:

So, this code is my 3rd implementation for this problem, the 1st got TLE, the 2nd got accepted but was about 27 lines long code, and now I finally thought about this implementation. In the 3rd line, I have just fetched indices containing '1' from the string s, and I have used List comprehension so with the if condition I had to use the else too, which made me insert the None too, and to remove that None from the list 'ls', I used the filter function which just takes a function and a container and keeps the values for which the function returns True else discards that value. Now, the last line just compares all the indices other than the first index containing a '1', bcz we need to understand this trick...if the index of first '1' is at an even distance from all other indices of the other 1's, then all those 1's will also have even distances between them, so we just have to check the first index containing 1 with all the other indices once, if we get an odd distance then we print 1 else if we get 0 distances odd then we just print 2. For that I have made another list inside the print and I am printing 1 if the list contains a 1 and otherwise I am printing 2(for the bad case when no distance is odd, that means we can only reduce the distance uptill 2, not less than that).