# Decreasing complexity one step at a time

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

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

**every time we go. In every**

*‘i’**i*term, we have to press the switch(es) which all are

^{th}**divisible by**. After repeating the process

*i**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**.

- For the first pass,
**i = 1**and every number from 1 to 6 is divisible by 1 so**all switches get pressed**. - For the second pass,
**i = 2**. Only**2, 4 and 6**are divisible by 2 so switch 2, 4 and 6 are pressed and change their state. - For the third pass,
**i = 3**. This time**3 and 6**are divisible by 3 so they get pressed and change their state.

and so on…**(see picture)**

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:**

- Get
**N**from the user. - Create an array of
**N+1**elements**all set to 0**. - Loop through
**1 to N**. - Check all the element if they are divisible by i then change it from 1 to 0 or 0 to 1.
- After loop gets over, print
**“ON” if A[n] is 1 else print “OFF”**.

**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:**

- Get
from the user.*N* - Set switch to
**False**. - Loop through
**1**to.*N* - For every
**i**, ifis divisible by*N***i**then change switch from**False**to**True**or**True**to**False**. - After loop gets over if the switch is set to
**True print “ON” else print “OFF”**.

**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**.

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

Due to

1, it will change it toON.

Due to2, it will change it toOFF.

Due to3, it will change it toON.

Due to4, it will change it toOFF.

Due to6, it will change it toON.

Due to12, it will change it toOFF.

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.

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