CODEWITHSUNDEEP
javaarraysalgorithm
David Lasry
David Lasry

Reputation: 1417

A riddle in java - Java

My friend gave me a riddle to solve. It goes like this:

There are 100 people. Each one of them, in his turn, does the following:

The first person opens all the boxes. The second person change the state to all the boxes whose number is divided by 2, without remainders. For instance, if a box is open and its number is divided by 2, it is closed. The same goes for a closed box.

The third person change the state to all the boxes whose number is divided by 3, without remainders. The "i" person change the state to all the boxes whose number is divided by i, without remainders.

Now, at then end of the process, I need to display all the boxes(their numbers) who are open.

I tried to implement a solution but I think it's not efficient. Here it is:

public class BoxesExc {

    public static void main(String[] args) {
        Box[] boxes = new Box[100];
        // Inflating the array with boxes
        for(int i=0; i<boxes.length; i++) {
            boxes[i] = new Box(i, false);
        }

        // Main part:
        for(int i=1; i<=boxes.length; i++) {
            for(int j=1; j<=i; j++) {
                // If the number is even
                if(i%2 == 0) {
                    if(j%i == 0) {
                        boxes[j].setOpen(!boxes[j].isOpen);
                    }
                } 
                // If the number is odd
                else {
                    if(j%2 != 0) {
                        if(j%i == 0) {
                            boxes[j].setOpen(!boxes[j].isOpen);
                        }
                    }
                }
            }
        }

    //Displaying the opened boxes:
    for(Box box : boxes) {
        if(box.isOpen)
            System.out.println(box.getNum()+",");
    }
    }

    public static class Box {
        private int num;
        private boolean isOpen;

        public Box(int num, boolean isOpen) {
            this.isOpen = isOpen;
        }

        public int getNum() {
            return num;
        }

        public boolean isOpen() {
            return isOpen;
        }

        public void setOpen(boolean isOpen) {
            this.isOpen = isOpen;
        }

    }
}

I haven't tried that yet but I just by looking at it, it looks awful. I need your help guys with finding a better solution.

EDIT: Alright guys I managed to solve this. Here is the solution:

public class BoxesExc {

    public static void main(String[] args) {
        int[] boxes = new int[101];
        // Inflating the array with boxes
        for(int i=1; i<boxes.length; i++) {
            boxes[i] = i;
        }

        int counter = 0;
        for(int i=1; i<boxes.length; i++) {
            for(int j=1; j<=i; j++) {
                if(i%j == 0)
                    counter++;
            }
            if(counter%2 != 0)
                System.out.print(""+i+", ");
            counter = 0;
        }
    }
}

Upvotes: 2

Views: 1778

Answers (4)

justmscs
justmscs

Reputation: 756

Since you only need to print the numbers, I think following is enough:

public class BoxesExc {
    public static void main(String[] args) {
        int boxNum = 100;
        for(int i = 1; i*i <= boxNum; i++) {
            System.out.print(i*i+",");
        }
    }
}

Upvotes: 0

Yuval David
Yuval David

Reputation: 93

it has very simple solution

the boxes which will be opened will be all the boxes which thier place is square exponentiation of a number.

for example in your question its between 1-100 so the answer will be:

1 4 9 16 25 36 49 64 81 100

also my solution is faster than yours because its order is θ(√n)

Upvotes: 2

njzk2
njzk2

Reputation: 39403

Here is a quick implementation of what I described in the comment:

public class BoxesExc {

    public static void main(String[] args) {
        Box[] boxes = new Box[100];
        // Inflating the array with boxes
        for(int i=0; i<boxes.length; i++) {
            boxes[i] = new Box(i, false);
        }

        // Main part:
        for (int i=1; i < boxes.length; i++) {
            // j+=i goes 3,6,9... for i = 3
            for (int j = i; j < boxes.length; j+=i) {
                 boxes[j].setOpen(!boxes[j].isOpen);
            }
        }

        //Displaying the opened boxes:
        for(Box box : boxes) {
            if(box.isOpen)
                System.out.println(box.getNum()+",");
        }
    }
}

Nota: you can init the box status to open and skip the first iteration (start with i = 2)

Upvotes: 0

Timothy Frisch
Timothy Frisch

Reputation: 2809

Iterate through all the boxes and modulate by your current indices. Do a switch to set the box open or closed depending on it's previous state. Then after you're done doing the 100 loop; do a secondary loop through the 100 boxes to see which ones are open and print them out.

Upvotes: 0

Related Questions