Decreasing complexity one step at a time

- 7 mins

cover image

“Knowing it and seeing it are two different things.” ― Suzanne Collins

I solve a lot of competitive programming(cp) problems in my free time. Recently I got a very interesting problem. I discovered many ways of solving it. Every new solution I got was better than the previous one. This blog post is just about showing that what we see is not always the reality.

The problem

This is the problem I encountered - Light, more light

Let me explain the question first in a concise manner. There are N toggle switches (i.e. if pressed, then it will turn on. Another press will turn it off) arranged linearly. There are N switches, so we have to go N times through all the switches. Assume the term ‘i’ every time we go. In every ith term, we have to press the switch(es) which all are divisible by i. After repeating the process N times, in the end, we have to tell that the last switch is ON or OFF.

Example

For example, assume N = 6 means there are 6 switches as of now. Initially, all the switches are set to OFF.

and so on…(see picture)

toogle switch

After simulating the whole process the last switch (i.e. switch 6) is OFF. So the result will be OFF.

Solutions

There are many ways of solving it. Let’s see.

* The First Glance *

The very first solution which came into my mind was to do the simulation.

Algorithm:

Pseudocode

PROGRAM slow_code:
	READ n
	DECLARE A[n+1] = {0}
	FOR i IN 1 TO n: DO
		j = i
		WHILE j <= n:
			IF A[j] == 1:
				A[j] = 0
			ELSE
				A[j] = 1
			ENDIF;
			j = j + i
		ENDWHILE;
	ENDFOR;

	IF A[n] == 1:
		WRITE "ON"
	ELSE:
		WRITE "OFF"
	ENDIF;
ENDPROGRAM

Time complexity   - O(nlogn)
Space complexity - O(n)

* The Elimination Round *

When you don’t know what you want, first figure out what you don’t want. - Biswa, Laakhon Mein Ek

If you see the problem very keenly, then you can notice that we don’t need to know about the rest of the switches except the last one. It means, we only need to know the numbers between 1 to N which can divide N.

Algorithm:

Pseudocode

PROGRAM fast_code:
	READ n
	switch = False
	FOR i IN 1 TO n: DO
		IF n%i == 0:
			IF switch == False:
				switch = True
			ELSE:
				switch = False
			ENDIF;
		ENDIF;
	ENDFOR;
	IF switch == True:
		WRITE "ON"
	ELSE:
		WRITE "OFF"
	ENDIF;
ENDPROGRAM

Time complexity   - O(n)
Space complexity - O(1)

* The Ninja Way *

Now it’s time to be the ninja. From the previous solution, we can observe a very important thing. What we want to know is the count of numbers that can divide N is even or odd. If the count is even, it will set the switch to False and if it’s odd that means it will set it to True.

factors even odd

E.g. For number 12, Initally the switch is set to OFF.

Due to 1, it will change it to ON.
Due to 2, it will change it to OFF.
Due to 3, it will change it to ON.
Due to 4, it will change it to OFF.
Due to 6, it will change it to ON.
Due to 12, it will change it to OFF.

So all we want to know now is that the factors count of N is even or odd. If we get any way to know that then we can easily get the answer. This answer is hidden inside a mathematical concept “Perfect Square”.

Perfect Square

def : A perfect square is a number that can be expressed as the product of two equal integers. e.g. 1(1x1), 4(2x2), 16(4x4), 25(5x5), etc.

There is one property of perfect square. The factor count of perfect square is always odd. The factors count of rest of the numbers is always even. The question is HOW??

If you take any number X, you can write it as a product of two numbers. There can be multiple ways. See the picture below to understand the differece between a perfect square and a non-perfect square.

perfect square

In the above example, first see the right hand side. For number 12, the first three lines are same as the last three lines. Each lines are written as a * b, where a is not equal to b in all the lines. i.e. the count will always be even because the factors come in pairs.

Now let’s see the left hand side. For number 16, the first two lines are same as last two lines. These four lines is also written as a * b, where a is not equal to b. The special part is the third line. It is written as a * b but here a is equal to b. i.e. the first and last two lines makes the factor count even but due to third line, it will become odd because the third line gives only one factor.

PHEW!

So, to know that the switch is ON or OFF all we really need to know is that the number given is perfect square or not. If it is perfect square, then the switch will be ON else it will be OFF.

Pseudocode

PROGRAM fastest_code:
	READ n
	y = FLOOR(SQRT(n))
	IF y*y == n:
		WRITE "ON"
	ELSE:
		WRITE "OFF"
	ENDIF;
ENDPROGRAM

Python implementation

import math
switch_status = lambda x:"ON" if math.floor(math.sqrt(x))**2==x else "OFF"
print(switch_status(int(input())))

Time complexity   - Depends on the sqrt function. know more
Space complexity - O(1)

Conclusion

Coding is not the toughest part, thinking is. At the very beginning, we tried to simulate the whole process to get the result. Then we removed the noise to make the problem less lumbering. We end up checking that the number is a perfect square or not. Can you see the beauty of thoughts that are deeply rooted in this whole journey? To know the answer that lies within, we first need to find out what is the real question. This time, it was just asking to know that the number is a perfect square or not but the question in itself was beautifully crafted to make it sound very complex. It all boils down to this quote -

The art of programming is the art of organizing complexity, of mastering multitude and avoiding its bastard chaos as effectively as possible. - E. W. DIJKSTRA

Aman Roy

Aman Roy

Geek, coder and pythonista!

comments powered by Disqus
rss facebook twitter github youtube mail spotify instagram linkedin google pinterest medium vimeo keybase stackoverflow reddit quora