Yahoo Interview Question Software Engineer / Developers
Its the factorization problem.
All numbers except the squares have even number of factors, so if all those doors which are at position number i, where i is not a square should remain closed at the last pass.
So, all those doors which are on open state are 1,4,9,16,25,36,49,64,81,100
All others are remain closed.
Novice is correct. If a door is toggled odd number of times , it is left open . Similarly if it is toggled even number of times, it is left closed.Example: When I toggle a door first time, its open. When I toggle it the second time its closed, 3rd time its open , 4th time its closed and so on..
Perfect squares doesnt necessarily work . 16 is open(1,2,4,8,16) , 36 is closed(1,2,3,4,6,12,18,36)
there is a thing about squares that many might not be knowing .....only squares are the numbers which have odd number of factor pairs......for ex:-
100=10*10
=5*20
=20*5
=25*4
=4*25
=2*50
=50*2
so whatever be the state of gate before start its exactly opposite will be its state after the end so only squares would be open and rest closed
The number of times a door will be toggled is based on the number of divisors the locker number has. For example, door #6 will be toggled on pass 1, 2, 3 and 6. Further note that most numbers have an even number of divisors. This makes sense since each divisor must have a matching one to make a pair to yield the product. For example, 1*6=6, 2*3=6.
The only numbers that do not have an even number of divisors are the square numbers, since one of their divisors is paired with itself. For example, door #9 is toggled an odd number of times on passes 1, 3 and 9 since 1*9=9 and 3*3=9.
Thus, all non-square numbered lockers will end up closed and all square numbered lockers will end up open.
//code in Java
public class DoorProblem {
public static void main(String arg[]) {
/**
* Starting position of doors are closed
* Logic behind this problem is simple
* if we visit each door odd times it will remain open
* else it will be closed(means even times)
* Find the number factor of each number .
* check whether factor is odd or even
*/
// 1 means open 0 means close
int door[] = new int[101];
//Factor calculation
for (int j = 1; j < door.length; j++) {
int count = 0;
for (int i = 1; i <= j; i++) {
if (j % i == 0) {
count++;
}
}
//Factor is odd of even
if (count % 2 == 1) {
door[j] = 1;
} else
door[j] = 0;
}
for (int i = 1; i < door.length; i++) {
if(door[i]== 1){
System.out.println("Door "+ i +" is open");
}
else
System.out.println("Door "+ i +" is close");
}
}
}
How to solve this problem?
You have n doors in a row that are all initially closed. You make n passes by the doors. The first
time through, you visit every door and toggle the door (if the door is closed, you open it; if it is
open, you close it). The second time you only visit every 2nd door (door #2, #4, #6, ...). The
third time, every 3rd door (door #3, #6, #9, ...), etc, until you only visit the nth door.
You need to find out what state are the doors in after the last pass? Which are open, which are
closed?
You'll be given number of doors, n.
You need to print out pair of (door_number, state) separated by '\n' aka 'end of line'. See
SAMPLE_OUTPUT for more clarity.
SAMPLE_INPUT:
3
SAMPLE_OUTPUT:
1,open
2,closed
3,closed
package com.akamai;
public class DoorOpenClose {
public static void main(String args[]) {
Boolean []doors = new Boolean[100];
//start all with zeros
for (int i = 0; i< 100; i++) {
doors[i] = false;
}
int increment = 1;
for (int i = 0; i < 100; i++) {
for (int j = increment - 1; j < 100; j = j + increment) {
doors[j] = !doors[j];
}
increment ++;
}
for (int i = 0; i< 100; i ++) {
if (doors[i]) {
System.out.print(i+1 + " ");
}
}
}
}
Output
1 4 9 16 25 36 49 64 81 100
class puzzle_door
{public static void main()
{boolean door[]=new boolean[100];
int walk=0;
for(walk=1;walk<=100;walk++){
System.out.println("walk no."+walk);
for(int seq=walk-1;seq<100;seq+=walk){
if(door[seq]) //false means the door is closed and vice-versa
{
door[seq]=false;
}
else
{
door[seq]=true;} } }
int count=0;
System.out.print("The doors ");
for(int i=0;i<100;i++)//counting the number of true values in the array 'door'
{if(door[i])
{System.out.print(i+1+" ");
count++;} }
System.out.print("will remain open");
System.out.print("\n\nThe answer is "+count);}}
class puzzle_door
{
public static void main()
{
boolean door[]=new boolean[100];
int walk=0;
for(walk=1;walk<=100;walk++)
{
System.out.println("walk no."+walk);
for(int seq=walk-1;seq<100;seq+=walk)
{
if(door[seq]) //false means the door is closed and vice-versa
{
door[seq]=false;
}
else
{
door[seq]=true;
}
}
}
int count=0;
System.out.print("The doors ");
for(int i=0;i<100;i++)//counting the number of true values in the array 'door'
{
if(door[i])
{
System.out.print(i+1+" ");
count++;
}
}
System.out.print("will remain open");
System.out.print("\n\nThe answer is "+count);
}
}
Hi,
- Novice September 13, 2010According to me, all the doors marked with squares (the numbers having odd number of factors) will be left open at the end i.e. 1,4,9,25...100. The rest of them would be closed.