Dutch National Flag

The Dutch national flag problem is a famous computer science related programming problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colours: red, white and blue. Given balls of these three colours arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same colour are together and their collective colour groups are in the correct order.

Here is a problem that is stimulated by the idea:

Q. Write a function that takes an array A and index i into A, and rearranges the elements such that all elements less than A[i] appear first, followed by elements equal to A[i], followed by elements greater than A[i]. Your algorithm should have O(1) space complexity and O(|A|) time complexity.

Soln:

 

#Function to swap two variables    
def swapNormal(A,pos1,pos2):
    t = 0
    t=A[pos1]
    A[pos1] = A[pos2]
    A[pos2] = t
    
#initializing an array of randomly generated numbers
j = 0
while j < 10:
    A.append(random.randint(1,100))
    j+= 1

print "The array of numbers is:",A

#asking for the position of the pivotal element
i = input("Please enter the index number")

pivot = A[i]

print "The pivot element is:",pivot

def dutchNationalFlag(A,pivot):
    equal = 0
    small = 0
    large = len(A)-1
    
    while (equal <= large):
        if A[equal] < pivot:
            swapNormal(A,equal,small)
            equal += 1
            small += 1
        elif (A[equal] == pivot):
                equal += 1
        else:
            swapNormal(A,equal,large)
            large -= 1
    
    return A

Advertisement

Finding The Smallest Divisor of Any Given Integer

This is a very basic problem and the lessons that we learn from this problem can be very useful 
in tackling more complex problems.

Say suppose we have an integer n and we are asked to find its smallest divisor except 
1. The first approach that anyone would take is to start from 2 and then go on dividing 
it with the number n and select the first number that divides n. 

n = 130

n = 130

for i in range(2,n-1):
    if 130 % i == 0:
        print i
        break


All this looks very cool and straight.Now say suppose n is a prime number.

May be n is a very large prime number (1013). So are we

going to count all the way upto 1012 starting from 2 and check whether 1013 gets divided

by any one of these numbers on the way? That sounds little stupid and requires a lot of work.

Now the main question is :

Do we have a better way?

In order to investigate into this matter lets start with few observations. 

Let us take a number n=100.

We have the following divisors of 100: [2,4,5,10,20,25,50]

Let us take the first divisor 2. We can easily observe that:



Similarly we can take other numbers and observe the following:






So from this we can observe that the smallest divisor 2 is

linked with the largest divisor 50.

Similarly the second smallest divisor 4 is linked with second

largest divisor 25. This goes on with 5 linked with 20 and finally

10 linked with 10. So if we want to generalize this, we can observe

that if any number n has a divisor then that divisor is always linked

with another divisor. The general pattern is that a smaller divisor is

linked with a larger one and vice versa.

Another interesting thing that can be observed is that if we go on

increasing the value of smaller divisor and consider the next larger

divisor, at the same time if we go on decreasing the value of the

larger divisor and consider the next smaller divisor then we reach

a cross over point.
2->4->5->10

50->25->20->10
For our example that cross over point is 10. Also at the cross over

point smaller divisor = larger divisor.

So what is 10 in our case? 10 is the square root of 100.
So once we find the square root of any number n  we don't

need to look beyond the value of the square root for the smallest divisor.

The other side of the square root will always have the larger divisors.

Also we need to check if the given number n is an even number or an

odd number. If n is even then we know that 2 will be its smallest

divisor. If it is odd we just need to start with 3 and go on checking

the next odd number until we reach the value of the square root of n.

So the more efficient program for finding the smallest divisor of any

given number n is as follows:
from math import sqrt
from math import floor
def smallestDivisor(n):
    if n % 2 == 0:
        print "The smallest divisor of %d is %d" %(n,2)

    else:
        squareRootOfn = floor(sqrt(n))
        for i in (3,squareRootOfn,2):
            if n % i == 0:
                print "The smallest divisor of %d is %d" %(n,i)
                break
            else:
                if i == squareRootOfn:
                    print "The smallest divisor of %d is %d" %(n,1)
                    print "The given number %d is a prime number" % (n)

smallestDivisor(1024)
smallestDivisor(63)
smallestDivisor(1013)

'''The outputs are as follows:
The smallest divisor of 1024 is 2
The smallest divisor of 63 is 3
The smallest divisor of 1013 is 1
The given number 1013 is a prime number'''