CODEWITHSUNDEEP
python
Chris
Chris

Reputation: 767

python - counting algorithm solving using "bitwise or of x and y"

I am analyzing a solution to the counting exercise from Codility (Frog_river_one).
Most of the solutions I have seen are based on looping through the positions and values of the given array. One of the solutions I came across seems to tackle this problem differently.


I recognize that the "bitwise or of x and y" was used there however I don't understand the logic of the solution. Especially the part checker=checker| 1<<(A[x]-1)
Can anybody explain please?

The problem

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river. You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes. The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.

The solution

A= [1,3,1,4,2,3,5,4]

def solution(X, A):
    checker=0
    final_val=pow(2,5)-1
    for x in range(len(A)):
        checker=checker| 1<<(A[x]-1)

        if(checker==final_val):
            return x
    return -1

Upvotes: 2

Views: 238

Answers (1)

Nurjan
Nurjan

Reputation: 6063

Actually the method solution should be changed slightly to:

def solution(X,A):
    checker = 0
    final_val = pow(2,X) - 1
    for x in range(len(A)):
        checker = checker | 1 << (A[x] - 1)

        if(checker == final_val):
            return x
    return -1

A = [1,3,1,4,2,3,5,4]

print(solution(5,A))

The basic idea behind this algorithm is to make sure that all leaves have fallen on the river up to and including position X by using the bitwise operations and binary representation of the positions of the leaves.

In order to make this work you define final_val which is equal to 2^X -1. In the case when X is 5, final_val is 2^5 - 1 = 31.

Then you iterate through list A.

This is the most interesting part.

checker = checker | 1 << (A[x] - 1)

You initialize checker as equal to 0.

Then let's break down the expression above:

1 << (A[x] - 1) is the same as 2^(A[x] - 1). This operation shifts binary 1 to the left by A[x] - 1' bits. This operation is done to make sure that the leave exists at positionA[x]`.

Then goes the | operator (OR). In this case this some sort of a plus operator but it does not add repetitive terms.

So let's go through the given example to show how it works.

x = 0: 

1 << A[0] - 1 which is 1 << 1 - 1
                       1 << 0

No shift. 1 remains 1. 

checker = 0 | 1

The bitwise | gives 1.

So checker is now 1. This means that there is a leaf at position 1.

x = 1:

1 << A[1] - 1 which is 1 << 3 - 1
                       1 << 2

So now 1 becomes 100 in binary. This means that there is a leaf at position 3.

Then:

checker = 1 | 100

Actually it is 001 | 100 which gives 101.

x = 2:

checker = 101 | 1 << 0
        = 101

Note here position 1 has already appeared, so it does not change the checker variable.

x = 3:

checker = 101 | 1 << 3
        = 101 | 1000
        = 0101 | 1000
        = 1101

Now checker is 1101. This means that there is a leaf at position 4.

x = 4:

checker = 1101 | 1 << 1
        = 1101 | 10
        = 1101 | 0010
        = 1111

This means that there is a leaf at position 2.

x = 5:            

checker = 1111 | 1 << 4
        = 1111 | 10000
        = 01111 | 10000
        = 11111

This means that there is a leaf at position 5.

But this is the position where the frog needs to get.

This is why there is a checking condition which compares checker with the final_val every iteration.

So we see that 11111 is equal to final_val (31 is 11111 in binary) and the algorithm returns the position of 5 which 6.

Note that if some of the positions did not appear before 5, e.g. instead of 2 there was 1, then algorithm would return -1 as there is no way for the frog to get to the position 5.

Upvotes: 2

Related Questions