Given an integer K and an array arr[] of N integers, the task is to find the maximum number that can be added or subtracted any number of times from K to get all the array elements.
Examples:
Input: K = 5, N = 3, arr = {3, 7, 13}
Output: 2
Explanation: As currently K is 5 we can subtract 2 to get 3 now K become 3.
After this we will add two times 2 in 3 to form 7. Now K is 7.
After this we will add 2 three times to form 13.Input: K = 6, N = 3, arr = {11, 6, 2}
Output: 1
Approach: The problem can be solved based on the following observation:
To get the maximum value, we must select the highest value which is a factor of the differences of K with all the array elements, i.e., the GCD of the differences of all the array elements with K.
Follow the below steps to solve this problem:
- Store the difference of all the array elements from K in an array (say temp[]).
- Iterate over the array arr[]:
- Store the absolute difference between K and the current array element in temp[].
- Initialize a variable (say ans = 0) to store the answer.
- Iterate over temp[]:
- Update answer with the GCD of ans and the current element’s value of temp[].
- Return the value of ans as the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to get the maximum valueint getMaxNum(int K, int N, vector<int>& arr){ // Vector to store the differences vector<int> temp; // Getting the difference of K and first number temp.push_back(abs(K - arr[0])); // Getting the difference between other numbers int i, j; for (i = 0; i < N - 1; i++) { temp.push_back(abs(arr[i] - arr[i + 1])); } int ans = 0; // Loop to calculate the required value for (int i = 0; i < N; i++) ans = __gcd(ans, temp[i]); // Return the answer return ans;}// Driver codeint main(){ int K = 6, N = 3; vector<int> arr = { 11, 6, 2 }; // Function call int ans = getMaxNum(K, N, arr); cout << ans; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { // Java code to implement the approachstatic int __gcd(int a,int b) { if (b == 0) return a; return __gcd(b, a % b);}// Function to get the maximum valuestatic int getMaxNum(int K, int N, int[] arr){ // Vector to store the differences ArrayList<Integer> temp = new ArrayList<>(); // Getting the difference of K and first number temp.add(Math.abs(K - arr[0])); // Getting the difference between other numbers int i, j; for (i = 0; i < N - 1; i++) { temp.add(Math.abs(arr[i] - arr[i + 1])); } int ans = 0; // Loop to calculate the required value for (i = 0; i < N; i++) ans = __gcd(ans, temp.get(i)); // Return the answer return ans;}// Driver Codepublic static void main(String args[]){ int K = 6, N = 3; int[] arr = { 11, 6, 2 }; // Function call int ans = getMaxNum(K, N, arr); System.out.println(ans);}}// This code is contributed by shinjanpatra |
Python3
# Python3 code to implement the approachfrom math import gcd# Function to get the maximum valuedef getMaxNum(K, N, arr) : # Vector to store the differences temp = []; # Getting the difference of K and first number temp.append(abs(K - arr[0])); # Getting the difference between other numbers for i in range(N-1) : temp.append(abs(arr[i] - arr[i + 1])); ans = 0; # Loop to calculate the required value for i in range(N) : ans = gcd(ans, temp[i]); # Return the answer return ans;# Driver codeif __name__ == "__main__" : K = 6; N = 3; arr = [ 11, 6, 2]; # Function call ans = getMaxNum(K, N, arr); print(ans); # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to get the maximum value static int getMaxNum(int K, int N, int[] arr) { // Vector to store the differences List<int> temp = new List<int>(); // Getting the difference of K and first number temp.Add(Math.Abs(K - arr[0])); // Getting the difference between other numbers int i; for (i = 0; i < N - 1; i++) { temp.Add(Math.Abs(arr[i] - arr[i + 1])); } int ans = 0; // Loop to calculate the required value for (i = 0; i < N; i++) ans = __gcd(ans, temp[i]); // Return the answer return ans; } // Driver Code public static void Main() { int K = 6, N = 3; int[] arr = { 11, 6, 2 }; // Function call int ans = getMaxNum(K, N, arr); Console.Write(ans); }}// This code is contributed by gfgking |
Javascript
<script> // JavaScript code for the above approach function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to get the maximum value function getMaxNum(K, N, arr) { // Vector to store the differences let temp = []; // Getting the difference of K and first number temp.push(Math.abs(K - arr[0])); // Getting the difference between other numbers let i, j; for (i = 0; i < N - 1; i++) { temp.push(Math.abs(arr[i] - arr[i + 1])); } let ans = 0; // Loop to calculate the required value for (let i = 0; i < N; i++) ans = __gcd(ans, temp[i]); // Return the answer return ans; } // Driver code let K = 6, N = 3; let arr = [11, 6, 2]; // Function call let ans = getMaxNum(K, N, arr); document.write(ans) // This code is contributed by Potta Lokesh </script> |
Output
1
Time Complexity: O(N * logD) where D is the maximum difference of an array element with K
Auxiliary Space: O(N)
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!
