Given 100 doors, all are closed initially, with each iteration, the current state of the door will be reversed or toggled, ie if the door is closed then it will be opened and if open then will be closed. The door visited will be dependent if it's multiple of the current iteration.
For example in 1st
iteration, all the doors will be visited (#1, #2, #3, #4, #5)
, in 2nd
iteration only multiple of 2 doors (#2, #4, #6, #8, #10)
will be visited, in 3rd
iteraton all the multiple of 3 doors (#3, #6, #9, #12, #15)
will be visited and so on.
package org.wesome.dsalgo;
import java.util.ArrayList;
import java.util.List;
public class HundredDoors {
public static List<Integer> hundredDoors(int doorCount) {
boolean[] doors = new boolean[doorCount];
List<Integer> openedDoors = new ArrayList<>();
for (int i = 1; i < doors.length; i++) {
System.out.println("\niteration = " + i);
for (int j = i; j < doors.length; j = j + i) {
System.out.println("toggling door = " + j + " which is currently " + doors[j]);
doors[j] = !doors[j];
}
}
for (int i = 1; i < doors.length; i++) {
if (doors[i]) {
System.out.println("Door is open" + i);
openedDoors.add(i);
}
}
System.out.println("openedDoors = " + openedDoors);
return openedDoors;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.ArrayList;
import java.util.List;
public class HundredDoorsTest {
@Test
void hundredDoorsTest1() {
List<Integer> openedDoors = new ArrayList<>();
openedDoors.add(1);
openedDoors.add(4);
openedDoors.add(9);
Assertions.assertTrue(openedDoors.equals(HundredDoors.hundredDoors(10)));
}
@Test
void hundredDoorsTest2() {
List<Integer> openedDoors = new ArrayList<>();
openedDoors.add(1);
openedDoors.add(4);
openedDoors.add(9);
openedDoors.add(16);
openedDoors.add(25);
openedDoors.add(36);
openedDoors.add(49);
openedDoors.add(64);
openedDoors.add(81);
Assertions.assertTrue(openedDoors.equals(HundredDoors.hundredDoors(100)));
}
}
plugins {
id 'java'
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}