Недавно мы с другом работали над этой проблемой:

В ряду 100 дверей, которые изначально закрыты. Вы делаете 100 проходов мимо дверей. В первый раз посетите каждую дверь и, если дверь закрыта, откройте ее; если он открыт, закройте его (т.е. переключите). Во второй раз посетите только каждую вторую дверь (дверь № 2, № 4, № 6, …) и переключите ее. В третий раз посетите каждую 3-ю дверь (дверь № 3, № 6, № 9, …) и т. д., пока не посетите только 100-ю дверь.

Сначала мы следовали задаче, как она была написана, и буквально восприняли идею пройти через все 100 дверей 100 раз. Мы начали решать ее, используя вложенный цикл for (т. е. время O(n2)).

function doors(){
  //initialize doors
  let doors = []
  for(let i=0; i<100; i++){
    doors[i] = 'closed'
  }
  //outer loop
  for (let i=1; i<=100; i++){
    for(let j=1; j<=100; j++){
      if (j % i === 0){
        doors[j] = !doors[j]
      }
     }
   }
   for(var i=0;i<=100;i++){
     console.log("Door %d is %s",i,doors[i]?true:false)
   }
}

После этого мы начали обсуждать способы сделать это проще, и моя подруга Мария сказала блестящую вещь, а именно то, что для каждой числовой двери, с которой вы начинаете, вы больше никогда не посещаете предыдущую. Итак, когда вы начнете с двери 4, вы не сможете ничего переключать перед ней. Когда вы поднимаетесь выше, это остается верным.

Это дало нам возможность начать думать о том, как можно пройтись по массиву всего один раз. Мой следующий вопрос заключался в том, что если бы вы могли переключать для каждой двери общее количество раз, которое она когда-либо коснется при первом проходе через нее? Например, если вы знаете, что № 6 нужно будет переключать в общей сложности 4 раза, можете ли вы выяснить это заранее (или, когда вы находитесь в 6), и просто сделать это?

Способ выяснить, сколько раз, состоит в том, чтобы увидеть, сколько из всех чисел перед этим числом является его множителями?

function doorsFaster(){
 
//initialize doors -- see above
for(let k=1; k<=100; k++){
  //go through the primes 
  for(let j=1; j<=k; j++){
    //if that prime is a factor of the door number
    if(k % j === 0){
   
       //toggle the door
       doors[k] = !doors[k]
     }
  }
   
   //print the state of the door
   for(var m=1; m<=50; m++){
     console.log("Door %d is %s",m,doors[m]?true:false)
   }
}

Это, как выясняется, еще долго. Но это было основой для моего понимания реального ответа, который был моим истинным моментом гениальности в этой проблеме, а не тем, который я не знаю, как воспроизвести (к сожалению).

Я понял, что каждое число будет делиться на четное число множителей само и на 1, и, если оно не простое, оно будет иметь пары из 2 других чисел (т.е. 8 делится на 1, 2, 4, 8), ЕСЛИ ЭТО НЕ ТАК. КВАДРАТ, потому что все, что является числом, умноженным на само себя, будет проходить это число только один раз, поэтому квадраты будут иметь нечетное количество делителей (например, 16 делится на 5 делителей: 1, 2, 4, 8, 16).

Самым элегантным решением, которое мы видели, было:

function doorsFastest(){
  for (var door = 1; door <= 100; door++) {
    var sqrt = Math.sqrt(door);    
    if (sqrt === (sqrt | 0)) {     
        console.log("Door %d is open", door);  
     }
  }
}

Это волшебным образом сработало, и после некоторого поиска в Google и тестирования мы узнали, что | часть уравнения необходима и не совпадает с ||. Я также обнаружил, что он работает так же, как Math.floor(), благодаря этим милым людям из StackOverflow. Как поясняется в документации, символ | является побитовым оператором ИЛИ, который выполняет операцию ИЛИ над каждой парой битов.

Как вы должны были просто волшебным образом добраться до той части, где вы определяете, что если номер двери является квадратом, то она открыта, до сих пор не понимаю.

Не хочу быть одним из этих надоедливых блоггеров, но я был бы очень рад услышать о других способах получения этого решения, которые можно повторно использовать / стандартизировать и которые можно применить к другим проблемам.