Last Updated: February 25, 2016
·
6.885K
· saurabhksingh

Algorithm : Jolly Jumpers

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the
differences between successive elements take on all possible values 1 through n − 1. For
instance,
1 4 2 3
is a jolly jumper, because the absolute differences are 3, 2, and 1, respectively. The
definition implies that any sequence of a single integer is a jolly jumper. Write a program
to determine whether each of a number of sequences is a jolly jumper.

Input
Each line of input contains an integer n < 3, 000 followed by n integers representing the
sequence.

Output
For each line of input generate a line of output saying “Jolly” or “Not jolly”.

Sample Input
4 1 4 2 3
5 1 4 2 -1 6
Sample Output
Jolly
Not jolly

Solution :
We need to concentrate on the fact that difference in consecutive numbers should cover all number from 1 to n-1.
The heart of solution is in selecting a data structure who's value at an index corresponding to the i (1 <= i < n) will be set
if absolute value of difference between consecutive numbers is i. Absolute values of differences will fail to cover
the range of 1 to n-1 if any of the difference value is repeated or any of the difference will fall out side the range
of 1 to n-1 and there will be no need to check for the numbers further.

Below is the solution code :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.BitSet;

public class JollyJumpers {

/**
 * @param args
 * @throws IOException 
 */
public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = "";
    //read the input from the console
    while ((input = br.readLine()) != null && !input.trim().equals("\n") && !input.trim().equals(""))
    {
        String[] data = input.split("\\s+");

        int numberOfInputs = Integer.parseInt(data[0]);

        if ((data.length - 1) != numberOfInputs)
        {
            System.out.println("Wrong input. Exiting....");
            System.exit(1);
        }
        BitSet bitSet = new BitSet(numberOfInputs);

        boolean isJolly = true;

        for(int i = 1; i< data.length-1; i++)
        {
            int diff = Math.abs(Integer.parseInt(data[i]) - Integer.parseInt(data[i+1]));
            if (diff < 1 || diff >= numberOfInputs || bitSet.get(diff))
            {
                System.out.println("Not Jolly");
                isJolly = false;
                break;
            }
            bitSet.set(diff);
        }
        if(isJolly)
        {
            System.out.println("Jolly");
        }
    }
}

}