Jolly Jumper-Sequenz
Eine Folge von n Zahlen (n < 3000) heißt Jolly Jumper , wenn die Absolutwerte der Differenzen zwischen den aufeinanderfolgenden Elementen alle möglichen Werte von 1 bis n-1 annehmen. Die Definition impliziert, dass jede Folge einer einzelnen Ganzzahl ein lustiger Jumper ist.
Beispiele:
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
Die Idee ist, ein boolesches Array zu verwalten, um eine Menge absoluter Differenzen aufeinanderfolgender Elemente zu speichern.
a) Wenn die absolute Differenz zwischen zwei Elementen größer als n-1 oder 0 ist, gebe false zurück.
b) Wiederholt sich eine absolute Differenz, dann können nicht alle absoluten Differenzen von 1 bis n-1 vorhanden sein ( Pigeon Hole Principle ), gebe false zurück.
Unten ist die Implementierung basierend auf der obigen Idee.
C++
// Program for Jolly Jumper Sequence
#include<bits/stdc++.h>
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>
Ausgabe:
Yes
Zeitkomplexität: O(n)
Referenzen:
http://users.csc.calpoly.edu/~jdalbey/301/Labs/JollyJumpers.html
Dieser Artikel wurde von Rahul Agrawal beigesteuert . Wenn Ihnen GeeksforGeeks gefällt und Sie etwas beitragen möchten, können Sie auch einen Artikel über write.geeksforgeeks.org schreiben oder Ihren Artikel per E-Mail an review-team@geeksforgeeks.org senden. Sehen Sie, wie Ihr Artikel auf der Hauptseite von GeeksforGeeks erscheint, und helfen Sie anderen Geeks.
Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben diskutierten Thema teilen möchten.
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .