Given an array, arr[] consisting of N integers representing coordinates on a number line and an integer S. Find the maximum size of jump required to visit all the coordinates at least once if the starting position is S. Also, Jumping in both directions is permitted.
Example:
Input: arr[]={1, 7, 3, 9, 5, 11}, S=3
Output: 2
Explanation: Jumps of size 2 is able to visit all the coordinates on the line, in the following way:
Jump -2: Reach 1 from 3.
Jump +2: Reach 3 from 1.
Jump +2: Reach 5 from 3.
Jump +2: Reach 7 from 5.
Jump +2: Reach 9 from 7.
Jump +2: Reach 11 from 9.Input: arr[]={33, 105, 57}, S=81
Output: 24
Approach: An observation can be made after reading the problem, that the greatest common divisor of all the differences between two adjacent points on the line is the maximum size of Jump needed to visit all points. So, to solve this problem, follow the below steps:
- Insert S, in the array arr, then sort it.
- Find the gcd between the differences of all adjacent pairs in the array arr.
- Return the final gcd as the answer to this problem.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum size of jump// to reach all the coordinatesint minJumpSize(vector<int>& arr, int S){ // Pushing S into the line arr.push_back(S); // Sorting arr, to get coordinates in // a sorted way sort(arr.begin(), arr.end()); // Finding gcd between the differences of // all adjacent pairs int gcd = arr[1] - arr[0]; for (int i = 1; i < arr.size(); i++) { gcd = __gcd(gcd, __gcd(gcd, arr[i] - arr[i - 1])); } return gcd;}// Driver Codeint main(){ vector<int> arr = { 1, 7, 3, 9, 5, 11 }; int S = 3; cout << minJumpSize(arr, S);} |
Java
// Java program for the above approachimport java.util.ArrayList;import java.util.Collections;class GFG { public static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to find the maximum size of jump // to reach all the coordinates public static int minJumpSize(int[] t_arr, int S) { ArrayList<Integer> arr = new ArrayList<Integer>(); for (int x : t_arr) { arr.add(x); } // Pushing S into the line arr.add(S); // Sorting arr, to get coordinates in // a sorted way Collections.sort(arr); // Finding gcd between the differences of // all adjacent pairs int gcd = arr.get(1) - arr.get(0); for (int i = 1; i < arr.size(); i++) { gcd = __gcd(gcd, __gcd(gcd, arr.get(i) - arr.get(i - 1))); } return gcd; } // Driver Code public static void main(String args[]) { int[] arr = { 1, 7, 3, 9, 5, 11 }; int S = 3; System.out.println(minJumpSize(arr, S)); }}// This code is contributed by saurabh_jaiswal. |
Python3
# python program for the above approachimport math# Function to find the maximum size of jump# to reach all the coordinatesdef minJumpSize(arr, S): # Pushing S into the line arr.append(S) # Sorting arr, to get coordinates in # a sorted way arr.sort() # Finding gcd between the differences of # all adjacent pairs gcd = arr[1] - arr[0] for i in range(1, len(arr)): gcd = math.gcd(gcd, math.gcd(gcd, arr[i] - arr[i - 1])) return gcd# Driver Codeif __name__ == "__main__": arr = [1, 7, 3, 9, 5, 11] S = 3 print(minJumpSize(arr, S))# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ public static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to find the maximum size of jump // to reach all the coordinates public static int minJumpSize(int[] t_arr, int S) { List<int> arr = new List<int>(); foreach (int x in t_arr) { arr.Add(x); } // Pushing S into the line arr.Add(S); // Sorting arr, to get coordinates in // a sorted way arr.Sort(); // Finding gcd between the differences of // all adjacent pairs int gcd = arr[1] - arr[0]; for (int i = 1; i < arr.Count; i++) { gcd = __gcd(gcd, __gcd(gcd, arr[(i)] - arr[(i - 1)])); } return gcd; }// Driver Codepublic static void Main(){ int[] arr = { 1, 7, 3, 9, 5, 11 }; int S = 3; Console.WriteLine(minJumpSize(arr, S));}}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript Program to implement // the above approach function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to find the maximum size of jump // to reach all the coordinates function minJumpSize(arr, S) { // Pushing S into the line arr.push(S); // Sorting arr, to get coordinates in // a sorted way arr.sort(function (a, b) { return a - b }) // Finding gcd between the differences of // all adjacent pairs let gcd = arr[1] - arr[0]; for (let i = 1; i < arr.length; i++) { gcd = __gcd(gcd, __gcd(gcd, arr[i] - arr[i - 1])); } return gcd; } // Driver Code let arr = [1, 7, 3, 9, 5, 11]; let S = 3; document.write(minJumpSize(arr, S))// This code is contributed by Potta Lokesh </script> |
Output:
2
Time Complexity: O(NlogN)
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
