You need to find the state of the 'k'th switch/bulb (1

Expected O(1) time and space complexity.

skip to main |
skip to sidebar
"Gebo" means to "give and take". This is my attempt to share the knowledge & experience with the community. Focus on Puzzles, Algorithms, Problem Solving, Java & other Technical Discussions.

#
100 Switches & 100 bulbs

## Labels / Tag

There are 100 switches in a room operating 100 bulbs. At iteration '0' all switches are OFF. For every iteration 'i', all switches that are multiples of 'i' are toggled (turn OFF if ON, turn ON if OFF).

You need to find the state of the 'k'th switch/bulb (1<=100) after the 'i' th iteration

Expected O(1) time and space complexity.

You need to find the state of the 'k'th switch/bulb (1

Expected O(1) time and space complexity.

Subscribe to:
Post Comments (Atom)

algorithms
(15)
amazon
(3)
antivirus
(1)
arithmetic series
(1)
array
(5)
backtracking
(1)
bash
(1)
basics
(1)
binary trees
(1)
brindavan garden
(1)
bulb
(1)
C++
(1)
callback
(1)
clam
(1)
clamav
(1)
clock
(1)
CLRS
(2)
cormen
(3)
data structures
(1)
duplicate
(1)
easymock
(1)
education
(1)
excel
(1)
freshclam
(1)
hanoi
(1)
hashing
(1)
httpclient
(1)
humor
(1)
induction
(1)
interview question
(9)
irrational
(1)
Java
(5)
jmockit
(1)
learning
(1)
level_easy
(1)
linux
(3)
logger
(1)
macro
(1)
madhur
(2)
mathematics
(5)
matrix
(1)
microsoft
(6)
mock
(2)
mockito
(2)
mysore
(1)
networking
(1)
OCW
(1)
odd man out
(1)
oocalc
(1)
OOTB
(1)
pattern
(1)
Persistent
(1)
probability
(2)
problem
(1)
problem solving
(17)
proxy
(1)
proxy selector
(1)
puzzle
(5)
quote
(1)
randomized
(1)
recurrsion
(2)
repeating
(1)
resolution
(1)
reverse
(1)
riddle
(5)
road trip
(1)
script
(1)
search
(2)
shell
(1)
shell script
(1)
socks
(1)
solaris
(1)
solved
(1)
sort
(3)
stock
(1)
strategy
(1)
subversion
(1)
summation
(1)
svn
(1)
switch
(1)
tanwani
(2)
TDD
(2)
technology
(2)
theorem
(1)
timer
(1)
todo
(1)
travel
(1)
trees
(1)
tutorial
(1)
unimodal
(1)
unit test
(2)
walk the bridge
(1)
warmup
(1)
water jugs
(1)
windows
(1)
xkcd joke
(1)

## 2 comments:

Lets calculate what the state of the bulb i will be with few examples.

If i = 6, the ith bulb will be toggled for 1,2,3,6 multiples. So it will be back to the state where it started as there are even number of toggles.

If i = 25, then 1,5,25 are the only factors of i. So the state of the ith bulb will be the opposite of what you started from.

Look at what caused the difference in both the cases.

In the first case,

1*6 = 2*3 = 6

In the 2nd case,

1*25, 5*5 = 25

In the 2nd case, we have same factor multiplied twice. ie if the factor is f, then the given number has been f^2 which reduced the toggle by 1.

So the answer is, all the square numbers within 100 will be in one state and the rest of the numbers will be in the other state.

Madan

@Madan

As far as I understand, your soln holds correct only for the cases where i >= k.

The soln I could think of is to find all the factors of k that are less than or equal to i and if their count is odd, then its ON otherwise its OFF.

Post a Comment