Wednesday, August 3, 2016

Jolly Jumper Sequence - GeeksforGeeks

Jolly Jumper Sequence - GeeksforGeeks
A sequence of n numbers (n < 3000) is called Jolly Jumper if the absolute values of the differences between the successive elements take on all possible values from 1 through n-1. The definition implies that any sequence of a single integer is a jolly jumper.
`bool` `isJolly(``int` `a[], ``int` `n)`
`{`
`    ``// Boolean vector to diffSet set of differences.`
`    ``// The vector is initialized as false.`
`    ``vector<``bool``> diffSet(n, ``false``);`

`    ``// Traverse all array elements`
`    ``for` `(``int` `i=0; i < n-1 ; i++)`
`    ``{`
`        ``// Find absolute difference between current two`
`        ``int` `d = ``abs``(a[i]-a[i+1]);`

`        ``// If difference is out of range or repeated,`
`        ``// return false.`
`        ``if` `(d == 0 || d > n-1 || diffSet[d] == ``true``)`
`            ``return` `false``;`

`        ``// Set presence of d in set.`
`        ``diffSet[d] = ``true``;`
`    ``}`

`    ``return` `true``;`
`}`