Jolly Jumper Sequence
En sekvens af n tal (n < 3000) is called Jolly Jumper hvis de absolutte værdier af forskellene mellem de successive elementer antager alle mulige værdier fra 1 til n-1. Definitionen indebærer, at enhver sekvens af et enkelt heltal er en jolly jumper.
Eksempler:
Input: 1 4 2 3 Output: True This sequence 1 4 2 3 is Jolly Jumper because the absolute differences are 3 2 and 1. Input: 1 4 2 -1 6 Output: False The absolute differences are 3 2 3 7. This does not contain all the values from 1 through n-1. So this sequence is not Jolly. Input: 11 7 4 2 1 6 Output: True
Ideen er at vedligeholde et boolesk array til at gemme sæt af absolut forskel af successive elementer.
- Hvis den absolutte forskel mellem to elementer er mere end n-1 eller 0 returneres falsk.
- Hvis en absolut forskel gentages, kan alle absolutte forskelle fra 1 til n-1 ikke være til stede ( Duehulsprincip ) returner falsk.
Nedenfor er implementeringen baseret på ovenstående idé.
C++ // Program for Jolly Jumper Sequence #include using namespace std ; // Function to check whether given sequence is // Jolly Jumper or not 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 ; } // Driver Code int main () { int a [] = { 11 7 4 2 1 6 }; int n = sizeof ( a ) / sizeof ( a [ 0 ]); isJolly ( a n ) ? cout < < 'Yes' : cout < < 'No' ; return 0 ; }
Java // Program for Jolly Jumper Sequence import java.util.* ; class GFG { // Function to check whether given sequence // is Jolly Jumper or not static boolean isJolly ( int a [] int n ) { // Boolean vector to diffSet set of differences. // The vector is initialized as false. boolean [] diffSet = new boolean [ n ] ; // Traverse all array elements for ( int i = 0 ; i < n - 1 ; i ++ ) { // Find absolute difference // between current two int d = Math . 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 ; } // Driver Code public static void main ( String [] args ) { int a [] = { 11 7 4 2 1 6 }; int n = a . length ; if ( isJolly ( a n )) System . out . println ( 'Yes' ); else System . out . println ( 'No' ); } } // This code is contributed by Rajput-Ji
Python3 # Python3 Program for Jolly Jumper # Sequence # Function to check whether given # sequence is Jolly Jumper or not def isJolly ( a n ): # Boolean vector to diffSet set # of differences. The vector is # initialized as false. diffSet = [ False ] * n # Traverse all array elements for i in range ( 0 n - 1 ): # Find absolute difference between # current two d = abs ( a [ i ] - a [ i + 1 ]) # If difference is out of range or # repeated return false. if ( d == 0 or d > n - 1 or diffSet [ d ] == True ): return False # Set presence of d in set. diffSet [ d ] = True return True # Driver Code a = [ 11 7 4 2 1 6 ] n = len ( a ) print ( 'Yes' ) if isJolly ( a n ) else print ( 'No' ) # This code is contributed by # Smitha Dinesh Semwal
C# // Program for Jolly Jumper Sequence using System ; class GFG { // Function to check whether given sequence // is Jolly Jumper or not static Boolean isJolly ( int [] a int n ) { // Boolean vector to diffSet set of differences. // The vector is initialized as false. Boolean [] diffSet = new Boolean [ n ]; // Traverse all array elements for ( int i = 0 ; i < n - 1 ; i ++ ) { // Find absolute difference // between current two int d = Math . 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 ; } // Driver Code public static void Main ( String [] args ) { int [] a = { 11 7 4 2 1 6 }; int n = a . Length ; if ( isJolly ( a n )) Console . WriteLine ( 'Yes' ); else Console . WriteLine ( 'No' ); } } // This code is contributed by PrinciRaj1992
JavaScript < script > // Javascript program for Jolly Jumper Sequence // Function to check whether given sequence is // Jolly Jumper or not function isJolly ( a n ) { // Boolean vector to diffSet set of // differences. The vector is // initialized as false. let diffSet = new Array ( n ). fill ( false ); // Traverse all array elements for ( let i = 0 ; i < n - 1 ; i ++ ) { // Find absolute difference between // current two let d = Math . 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 ; } // Driver Code let a = [ 11 7 4 2 1 6 ]; let n = a . length ; isJolly ( a n ) ? document . write ( 'Yes' ) : document . write ( 'No' ); // This code is contributed by _saurabh_jaiswal < /script>
Produktion:
Yes
Tidskompleksitet: På)
Hjælpeplads :O(n) da vi brugte vektor af størrelse n.
