1
\$\begingroup\$

I am learning Java right now and am coding some simple programs to practice. Right now, one of my for loops has an inelegant way of ending the loop. I was wondering if there was another way to express what I want the program to do.

Problem: Party Invitation

Problem Description

Number your friends 1,2,....,K and place them in a list in this order. Then perform m rounds. In each round, use a number to determine which friends to remove from the ordered list.

The numbers will use numbers r1, r2,....,rm. In round 'i' remove all the remaining people in positions that are multiples of ri (that is, ri, 2ri, 3ri,...) The beginning of the list is position 1.

Output the numbers of the friends that remain after this removal process.

Input Specification

The first line of input contains the integer K. The second line of input contains the integer m, which is the number of rounds of removal. The next m lines each contain one integer. The 'i'th of these lines contains ri indicating that every person at a position which is multiple of ri should be removed.

Output Specification

The output is the integers assigned to friends who were not removed. One integer is printed per line in increasing sorted order.

Sample Input

10

2

2

3

Output for Sample Input

1

3

7

9

Explanation of Output for Sample Input

Initially our list of invitees in 1,2,3,4,5,6,7,8,9,10. There will be two rounds of removals. After the first round of removals, we remove the even positions (because round 1 is '2', so every second position), which causes our list of invitees to be 1, 3, 5, 7, 9. After the second round of removals. we move every 3rd remaining invitee: thus, we keep 1 and 3, remove 5 and keep 7 and 9, which leaves us with an invitee list of 1, 3, 7, 9.

My code has a few System.out.printlns so I can keep track of what it is doing.

public class Party {

public static void main(String args[]) {
    try {

        BufferedReader input = new BufferedReader(new InputStreamReader(
                System.in));

        int totalFriends = Integer.parseInt(input.readLine());
        int rounds = Integer.parseInt(input.readLine());
        int[] roundNumber = new int[rounds];
        ArrayList<Integer> friendList = new ArrayList<Integer>(totalFriends);

        // create my list of friends
        for (int i = 0; i < totalFriends; i++) {
            friendList.add(i + 1);
        }

        // create an array for the number of rounds to cut, and how to cut
        // each time
        for (int i = 0; i < rounds; i++) {
            roundNumber[i] = Integer.parseInt(input.readLine());
        }

        System.out.println("Rounds: " + Arrays.toString(roundNumber));

        // for each round, do this
        for (int h = 0; h < rounds; h++) {

            System.out.println("Removing every " + roundNumber[h]
                    + " number");

            System.out.println("Starting with: " + friendList);


            int indexToRemove = 0;


            //the for loop here tells it to exit when the indexToRemove is larger
            //than the friendlist. I have to say +roundNumber[h] - 1, because the indexToRemove is
            //from the last iteration, not the one I want it to check.

            for (int i = 0; (indexToRemove + (roundNumber[h] - 1)) < friendList
                    .size(); i++) {

                indexToRemove = ((roundNumber[h] - 1) + (i * (roundNumber[h] - 1)));
                System.out.println("Removing index: " + indexToRemove);

                friendList.remove(indexToRemove);

                System.out.println(friendList);

            }

        }

        // the required output for this problem
        for (int i = 0; i < friendList.size(); i++) {
            System.out.println(friendList.get(i));
        }

    } catch (IOException e) {
        e.printStackTrace();
    }
}
}
\$\endgroup\$
1
\$\begingroup\$

for loop

You're right. Not much point in checking the boundary condition twice.

        // right now, it is doing 1 more calculation than necessary
        // before exiting the for loop
        int indexToRemove = 0;

        for (int i = 0; indexToRemove < friendList.size(); i++) {
            // what I'm trying to say is that if the index you're
            // cutting is longer than the friendList, then exit the for
            // loop
            // but the indexToRemove here is from the last iteration, so
            // it doesn't work
            indexToRemove = ((roundNumber[h] - 1) + (i * (roundNumber[h] - 1)));
            System.out.println("Removing index: " + indexToRemove);
            if (indexToRemove < friendList.size()) {
                friendList.remove(indexToRemove);
            }
            System.out.println(friendList);

        }

You need to update indexToRemove at the end of the loop, not the beginning.

        int indexToRemove = roundNumber[h] - 1;

        for (int i = 1; indexToRemove < friendList.size(); i++) {
            System.out.println("Removing index: " + indexToRemove);
            friendList.remove(indexToRemove);
            System.out.println(friendList);
            indexToRemove = ((roundNumber[h] - 1) + (i * (roundNumber[h] - 1)));
        }

Perhaps this would be clearer as a while loop:

        int indexToRemove = roundNumber[h] - 1;
        int i = 1;

        while ( indexToRemove < friendList.size() ) {
            System.out.println("Removing index: " + indexToRemove);
            friendList.remove(indexToRemove);
            System.out.println(friendList);

            indexToRemove = ((roundNumber[h] - 1) + (i * (roundNumber[h] - 1)));
            i++;
        }

Remember that you can always write a for loop as a while loop. It's just syntactic sugar. Or vice versa:

        for (int indexToRemove = roundNumber[h] - 1, i = 1; indexToRemove < friendList.size(); i++, indexToRemove = ((roundNumber[h] - 1) + (i * (roundNumber[h] - 1))) ) {
            System.out.println("Removing index: " + indexToRemove);
            friendList.remove(indexToRemove);
            System.out.println(friendList);
        }

Although that's a bit long and complicated for a single line. Note that we can rewrite the first line as

        for (int indexToRemove = roundNumber[h] - 1, i = 1; indexToRemove < friendList.size(); i++, indexToRemove = (i + 1) * (roundNumber[h] - 1) ) {

That's a bit better, but we can still do better:

        for (int indexToRemove = roundNumber[h] - 1; indexToRemove < friendList.size(); indexToRemove += roundNumber[h] - 1 ) {

That seems more like a for loop. We've done away with i altogether and only work with indexToRemove.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.