Hey guys and welcome to another The Daily Programmer web series and in this one
We're going to talk about a problem called Jolly Jumper. Which is number 311 on The Daily Programmer's subreddit.
So let's go ahead and break down this problem on the whiteboard. Okay, so for this problem
You were provided with a list of integers and what you're trying to do is take the sequential difference between each integer
so for instance if I do the difference between 1 & 4 in fact, I should say the absolute
difference, so this will give us 3
and then again the difference between
4 & 2 will give us a difference of 2 and then the absolute difference of 2 & 3 will give us 1, right?
So the goal is given this list, can you create the same set of integers that lead up to n - 1?
So to kind of break that down. We have n = 4 here, right? We have 4 numbers.
So n = 4 and our goal is to create a set
which = 1 to n-1
Which is also you know 1, 2, 3, in this case because n = 4
So in this particular case, it turns out that this is
considered a Jolly jumper list because we were able to create the 3
we were able to create the 2 and then we're also able to create the 1
So that's the overview of the problem now. Let's try to work it out by hand.
Starting off you know what n is. You know that n = length of the array - 1
So over here, you just create a set and
just let it equal to all the numbers that lead up to n - 1 so again 1, 2, 3
and then we can iterate through this list where i = 1 here and
then this is i + 1 and
then stop before you reach this 3
So again you take i + 1 which is going to be
4 - i which is going to be 1
Take the absolute value of that which will give us the 3 and then once you have this value, you just go ahead and remove it
from the set here, so if it exists in the set just go ahead and remove it
then continue on to the next number, so we're increment i by 1
So this is now, i + 1 here. We have 4
actually this would be 2 so we have 2 and
this is 4
Which leaves us an absolute
difference of 2 and again if it's in the set just go ahead and remove it and which it is and
then start doing the process one more time until you reach that i - 1 location. So again, I'll just increment i by 1
so this is i now this is i + 1 and
Then we can take the difference between 3 and 2
Absolute value of 3 - 2 = 1 and then remove it from the set
Then finally once you reach the end of this array like when your for loop is done running
Or wire loop of whatever type of loop or iteration you want to do is done
just check if the set.length = 0 because if equal to zero you know that you've removed everything from the set
and you're okay
Then if it's not then obviously it's not a Jolly Jumper
So you just say it's not a Jolly Jumper, and that's pretty much how you solve it by paper. Again loop over your set.
Loop over from 1 to n to create your set then loop over your list
And then keep taking the difference an absolute value of it
remove it from the set and then when you reach the end of your list
check if the set = 0. So let's go ahead and implement this in Javascript
All right, so starting off the first thing
We're going to do is just define a function called isJollyJumper
and that's going to take in parameter of numbers
which is just going to be an array or list of numbers.
And then down here is going to call isJollyJumper with our array of 1, 4, 3, 2
Let me just double check that that is the right example input that we worked on, sorry it's 1, 4, 2, 3
Cool, so then to actually start implementing our function
Remember, that's the very last thing we checked.
I like to do things backwards. I like to set the thing that we're going to return and then return it
before I actually start working out the logic, so I work backwards into the implementation.
So again we talked about we just need to return if the set length = 0 and
if it is then it is a Jolly Jumper. So first I'll declare a set and make it equal to the empty array and
then I'll return set.length === 0
Which again if 0 true otherwise false
So that should make sense. And now the first part of the solution was we need to create that
set of integers from 1 to n - 1 We know it n is, so we say const n = numbers.length
So we can loop through let i = 1; i <= n - 1; i++
loop through from 1 to n - 1 and
then just go ahead and push that number into the set. So it's going to push 1, 2, 3 into the set in this example.
And I can just go ahead and print out set here so we can visualize that on Line 9 so it pushes 1, 2, 3
Then we're good to go. And then the next step of the algorithm remember is we need to loop through the numbers take the absolute
difference between the numbers and remove them one by one from the set if we found something
So I'll go ahead and just do another loop
So for let i = 0; i < numbers.length - 1;
and remember we don't want to go out of bounds because we're taking we're going to check i
we're also going to check i + 1 so we need to make sure numbers that length - 1 is
our condition so that we don't go out of bounds on the array. So then in this loop
we can say const a = numbers of i
const b = numbers of i + 1
I'll just go ahead and print out a and b here so we can kind of visualize what's going on
So again in the first iteration a = 1
b = 4 const diff = Math.abs(a - b)
print that out, so we get 3, 2, 1
so again take a step back... we get the first number, get the second number, we take the difference, and we take the math of
the absolute value of that difference
and now we just need to remove it from the set if it exists in the set so I can say:
if (set.indexOf(diff) !== -1)
so it does exist in the set
I'm going to say set.splice
set.indexOf(diff)
and then remove that one element from the array.
And if you're not familiar with line 19, that's pretty much how you
given an array, remove a particular number from that array
So now at this point, I can just go ahead print out set again
and we see that it removes the 3 it removes the 2 and it removes the 1
so this is going to return true for us down here
Let's go ahead and remove all these little
annotations and console logs, so we have a clean function to look at
So that should make sense
and then we remove let's say the 3 this should be false because 1 - 4 = 3 and
then 4 - 2 = 2 but we're really looking for 1 and 2 and I'll just go ahead and
again write that out so I can say what is the value of set here and at the end
So the first iteration we get a 3 it tries to remove 3 from the set that doesn't exist because remember we're looping
from 1 to n - 1 and n = 3 in this case
So up here if I were to print out set
The set is 1 and 2 but we get 3 and 2 which means that this is not a Jolly Jumper set
Yeah, so that wraps the whole Jolly Jumper number. I think is 3 1
1 challenge of
There's probably some better ways to do this maybe there's like a reduced function you can use for creating this or just
more concise code
This is my first implementation
So this is basically how you do it off the top of my head
Again if you liked this video give us a like and then be sure to subscribe to FreeCodeCamp below all right
Thanks for watching