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

// 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.