Mixed Problem solving Series for beginners Part 1
Jolly Jumpers – Online Judge (Uva) - 10038 Problem Tutorial and Solution.
Problem Link Online Judge (Uva) 10038
You are given a sequence of size n. So, there are n-1 absolute differences of adjacent values. If all the numbers from 1 to n-1 are present in the absolute differences of adjacent values, the sequence is Jolly Jumper otherwise it is not. We have to check if the given sequence is jolly jumper or not.
Before go through the solution please try to solve this by yourself.
Solution:
Time Limit - 3 seconds.
Maximum size of the sequence n <= 3000.We can find the absolute differences of the adjacent values by iterating the sequence once. But how can we check if all the values from 1 to n-1 are present in the absolute differences? Please observe, the value of n can be maximum 3000. We can use an extra array to mark if the values from 1 to n-1 are present as absolute differences. Can we solve this by ourselves now? Please try to solve this by yourself now. If you can’t solve this after trying enough only then go for the next part.
Let’s have a boolean array named “marker” of size 3001. For each test cases let’s make the values of each index 0. And we will take the input in an array named “ar”. Let’s, val = absolute difference of two adjacent values. Now, every time we find the value of valm let’s make marker [ val ] = 1. But we have to be careful not to mark the index when the val is greater than n-1. Because then it will give us a runtime error if we try to mark an index greater than the size of marker array. So we can code this as following.
for ( int i = 2 ; i <= n; i++ ) { int val = abs( ar [ i ] - ar [ i - 1 ] ); if( val < n )marker [ val ] = 1; }
Now we have to check if all the indexes from 1 to n-1 in the marker array equal to 1. If not, it’s not a jolly jumper sequence.
int temp = 0; for ( int i = 1 ; i < n ; i++ ) { if ( !marker [ i ] ) { temp = 1; break; } } if ( !temp )cout<<"Jolly\n"; else cout<<"Not jolly\n";
Full Code with C++
Can you solve this whole problems using a single loop? I mean can you solve this whole problem within the loop that is used for taking input?
Think!