Optimising Lucky Number Program

Question

In this, we are given an array of numbers, say 1 2 3 4.

We start from a given position, let's say the 1st position. We cancel that number and move forward that many non-cancelled numbers. The number on which we stop again has the same procedure.This is repeated until only one number is left. That is the lucky number.

1 2 3 4

2 3 4

3 4

3

My code:

import java.util.*;

class ln
{
    public static void main(String[] ar)throws Exception
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("How many nos. will you enter: ");
        int n = sc.nextInt();
        int[] a = new int[n];
        System.out.print("Enter the nos.: ");
        for(int i = 0; i < a.length; i++)
            a[i] = sc.nextInt();
        System.out.print("From which position do you want to start: ");
        int st = sc.nextInt();
        for(int i = 0; i < a.length - 1; i++)
        {
            int j = a[st - 1];
            a[st - 1] = 0;
            int s = (int)Math.signum(j);
            while(j != 0)
            {
                if(a[st-1] != 0)
                    j -= s;
                st += s;
                if(st > a.length)
                    st = 1;
                else if(st < 1)
                    st = a.length;
            }
        }
        for(int i = 0; i < a.length; i++)
        {
            if(a[i] != 0)
            {
                System.out.println("Final no.: " + a[i]);
                break;
            }
        }

    }
}

Please tell if there is a more elegant way of doing this .

Answer 1

Yes, there is a more elegant way of doing this. (That's all you wanted to know, isn't it?)

First of all, here's some general comments about your code:

• Your Scanner should be closed when you are done with it. sc.close();
• You use in total six different names for variables. All of these have a variable name of one or two single characters. It is hard to understand their purpose because of the short variable names you have given them. Possible better names could be currentIndex, sign, currentNumber...

• Use methods. A method should do one thing and it should do that one thing well. Your main method currently does:

  • Receive user input and put it into an array
  • Determine the "final number" according to your rules for this array
  • Display result to user

  At least make a separate method for determining the final number for an array. The method could be something like this: public static int finalNumber(int[] inputArray)

Use an if-statement to check if you are currently processing the last number. This will get rid of the last for-loop in your current code, which only loops through the array and shows the non-zero number it encounters.

There is some things that can be simplified within your algorithm as well.

• loop x number of times, where x equals array size
• get the value at the current index
• get the sign of the current value
• modify the current index by + current value
• while the value at the current index is zero, modify the current index by the value of sign

When modifying the index, you can use the modulo % operator to make sure that it is within the bounds of the array.

Here is what I would do:

public static int luckyNumber(int[] a, int index) {
    List<Integer> ints = new ArrayList<Integer>(a.length);
    for (int i = 0; i < a.length; i++) {
        // Add the values to a list so that it is easy to remove them later
        ints.add(a[i]);
    }
    int lastValue = 0;
    while (!ints.isEmpty()) {
        // Save the index that should be removed later
        int oldIndex = index;
        int currentNumber = ints.get(index);
        index = index + currentNumber;

        // Make sure that the index is within a valid range
        if (index < 0)
            index += ints.size() * Math.abs(index);
        index = index % ints.size();

        // Remove the old index and adjust the index value if the index removed was before the current index.
        lastValue = ints.remove(oldIndex);
        if (oldIndex <= index) index--;
    }
    // Once the list is empty, return the last value that was removed
    return lastValue;
}

All these tests will print the lovely number 42:

System.out.println(luckyNumber(new int[]{ 1, 2, 42, 4 }, 0));
System.out.println(luckyNumber(new int[]{ 1, -1, 42, 4 }, 0));
System.out.println(luckyNumber(new int[]{ 1, -1, 2, 42, -4 }, 1));