In this post I introduce you to a competitive programming problem called Jolly jumpers. This problem is available on UVa online judge on this link.
UVa site is one of the first online judge websites which listed programming problems from different competitions like ACM ICPC and IOI and allowed users to solve and submit their programs online to check if their solutions are correct or not. This site contains a huge number of programming problems of varying complexities. Go and register yourself on this site if you are passionate about programming and start solving the problems!
The problem is defined as follows…
A sequence of n > 0 integers is called a jolly jumperif the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,
1 4 2 3
is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper.
Input
Each line of input contains an integer n <= 3000 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
The C++ code to solve this problem is given below.
To solve this problem we use a diff array. We try to calculate the absolute difference between each of the successive elements and populate the result in the diff array. while populating, we check if the result lies in the range [1, N-1]. If not, the array is not a jolly jumper. Also if the same difference appears more than once, it is not a jolly jumper.