CODEWITHSUNDEEP
c
user12887858
user12887858

Reputation:

100 doors problem solution does not work as expected

This question will be about 100 doors problem which is a famous problem from rosetta. Here is the problem:

The question: what state are the doors in after the last pass? Which are open, which are closed?

So my point is give program an input ,lets say n, so after nth pass which doors will be open kind of thing but there is a flow in it and I could not find it. If there is anyone who can correct issues of my logic I would be happy. Thank you all. 

#include <math.h>
#include <stdio.h>
int a = 1;

int main(){
    int doors[101];
    int i,j,x,b;

    scanf("%d",&x);
    for(j=1;j<=x;j++)
    {
        for(i=j;i<=100;i=i+j)
        {
            if(doors[i] == 0)
            {
                doors[i]==1;
            }
            else
            {
                doors[i]==0;
            }
        }
    }

    for(b=1;b=100;b++){
        if(doors[b]==1)
        {
            printf("%d\n",b);
        }
    }

    return 0;
}

Upvotes: 0

Views: 1019

Answers (4)

Raushan Kumar
Raushan Kumar

Reputation: 1

solution in java

public class Door100 {
public static void main(String[] args) {

    int doors[]= new int[100]; //this is our 100 doors
   //cheaking condition
    for(int i=1;i<=doors.length;i++){
       int j = i;
       while(j<doors.length){
        if(doors[j]==0){
            doors[j]=1;
        }
        else{
            doors[j]=0;
        }
        j += i;
       }
       //desired outputO(open doors)
    }
    for(int i=0;i<doors.length;i++){
        if(doors[i]==1)
        System.out.println(i);
    }
}

}

Upvotes: 0

nimesh
nimesh

Reputation: 43

A Simple ruby code for this problem would be:

LEN = 100
array = [false] * LEN
(1..LEN).each do |pass|
  (-1..LEN).step(pass).each do |i|
    next if i == -1
    break if i >= LEN
    array[i] = !array[i]
  end
  # puts "Pass: #{pass}"
  # puts "Gates: #{array.inspect}"
end

array.count(true)

Output: 10

Upvotes: 0

4386427
4386427

Reputation: 44274

The answer given here https://stackoverflow.com/a/61366204/4386427 is the answer to accept as it explains the problems in the code and provide a solution.

I just want add that the problem is about the number of times you toggle a door.

If you toggle it an even number of times, the door will still be closed at the end.

If you toggle it an odd number of times, the door will be open at the end.

This comes down to the number of divisors a door number has, i.e. even number of divisors or odd number of divisors.

Example:

14 have the divisors 1, 2, 7, 14 That's an even number so door 14 is still closed

16 have the divisors 1, 2, 4, 8, 16 That's an odd number so door 16 will be open

The only numbers that have an odd number of divisors are square numbers.

Therefore you can simply do:

int numDoors = 100;
for (int i=1; (i*i) <= numDoors; ++i) printf("%d\n", i*i);

It's simple, fast, and without arrays - but requires that you know the puzzle in advance :-)

Upvotes: 1

Serge Ballesta
Serge Ballesta

Reputation: 148890

Ok, there were a few errors in your code:

int doors[101];   // uninitialized array. You want int doors[101] = {0};
...
        if(doors[i] == 0)      // ok == for a comparison
        {
            doors[i]==1;       // NO! an assignation is expected: doors[i] = 1;
        }
        else
        {
            doors[i]==0;       // id.: doors[i] = 0;
        }
...
for(b=1;b=100;b++){            // NO! a comparison is expected: for(b=1;b<=100;b++)

This is enough to get the sequence of perfect squares: 1 4 9 16 25 36 49 64 81 100.

But you consistently use your array starting from index 1 which is an antipattern in C language. Your code could be simplified into:

#include <stdio.h>
#define NDOORS 100

int main() {
    int doors[NDOORS] = { 0 };

    for (int j = 1; j <= NDOORS; j++)
    {
        for (int i = j-1; i < NDOORS; i += j)
        {
            doors[i] = 1 - doors[i];
        }
    }

    for (int b = 0; b <= NDOORS; b++) {
        if (doors[b] == 1)
        {
            printf("%d\n", b+1);
        }
    }

    return 0;
}

Upvotes: 2

Related Questions