Given an array, arr[] of size N, Given M queries and each query consisting of a number X, the task is to subtract X from every element of arr[] for each query and print the Greatest Common Divisor of all elements of arr[].
Examples:
Input: arr[] = {9, 13, 17, 25}, Q[] = {1, 3, 5, 9}
Output: 4 2 4 4
Explanation: First Query: GCD(9 – 1, 13 -1, 17 – 1, 25 – 1) = GCD(8, 12, 16, 24) = 4
Second Query: GCD(9 – 3, 13 – 3, 17 – 3, 25 – 3) = GCD(6, 10, 14, 22) = 2
Third Query: GCD(9 – 5, 13 – 5, 17 – 5, 25 – 5) = GCD(4, 8, 12, 20) = 4
Fourth Query: GCD(9 – 9, 13 – 9, 17 – 9, 25 – 9) = GCD(0, 4, 8,, 16) = 4Input: arr[] = {1 25 121 169}, Q[] = {1 2 7 23}
Output: 24 1 6 2
Naive approach: The basic way to solve the problem is as follows:
For each query Iterate through every element of arr[] and keep track of GCD.
Time Complexity: O(N * M * logD) where D is the maximum value of the array
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved based on the following idea:
Property of Euclidean Algorithm for finding GCD can be used which is GCD(a, b) = GCD(a, b – a). For multiple numbers idea can be generalized as GCD(a, b, c, …) = GCD(a, b – a, c – a, …).
Follow the steps below to solve the problem:
- To calculate GCD(arr[0] – X, arr[1] – X, arr[2] – X, . . ., arr[N – 1] – X), subtract arr[0] – X from other Numbers.
- Then, GCD (arr[0] – X, arr[1] – X, arr[2] – X, . . ., arr[N – 1] – X) = GCD(arr[0] – X, arr[1] – arr[0], arr[2] – arr[0], . . ., arr[N – 1] – arr[0]).
- Find T = GCD( arr[1] – arr[0], arr[2] – arr[0], . . ., arr[N – 1] – arr[0]), then gcd for every query can be calculated to be GCD(arr[0] – X, T).
- For each query print the absolute of GCD(X, T) (print absolute since the answer can be negative after subtraction).
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to Calculate GCD for each queryvector<int> findGCDBySubtractingX(int arr[], int Q[], int N, int M){ int T = 0; vector<int> res; // Find GCD of arr[1] - arr[0], arr[2] - arr[0], // . . ., arr[N - 1] - arr[0] for (int i = 1; i < N; i++) { T = __gcd(T, arr[i] - arr[0]); } // Iterating for each of M Queries for (int j = 0; j < M; j++) { int X = Q[j]; // Finding GCD for each query with // their absolute since subtraction // can be negative res.push_back(abs(__gcd(T, arr[0] - X))); } return res;}// Driver Codeint main(){ // Input int arr[] = { 9, 13, 17, 25 }, Q[] = { 1, 3, 5, 9 }; int N = sizeof(arr) / sizeof(arr[0]); int M = sizeof(Q) / sizeof(Q[0]); // Function Call vector<int> ans = findGCDBySubtractingX(arr, Q, N, M); for (int x : ans) cout << x << " "; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to Calculate GCD for each query public static List<Integer> findGCDBySubtractingX(int[] arr, int[] Q, int N, int M) { int T = 0; List<Integer> res = new ArrayList<>(); // Find GCD of arr[1] - arr[0], arr[2] - arr[0], // . . ., arr[N - 1] - arr[0] for (int i = 1; i < N; i++) { T = gcd(T, arr[i] - arr[0]); } // Iterating for each of M Queries for (int j = 0; j < M; j++) { int X = Q[j]; // Finding GCD for each query with // their absolute since subtraction // can be negative res.add(Math.abs(gcd(T, arr[0] - X))); } return res; } // Driver Code public static void main(String[] args) { // Input int[] arr = { 9, 13, 17, 25 }; int[] Q = { 1, 3, 5, 9 }; int N = arr.length; int M = Q.length; // Function Call List<Integer> ans = findGCDBySubtractingX(arr, Q, N, M); for (int x : ans) System.out.print(x + " "); }}// This code is contributed by lokeshmvs21. |
Python3
import mathdef findGCDBySubtractingX(arr, q, n, m): t = 0 res = [] # find the gcd of arr[1]-arr[0] # .... arr[n-1]-arr[0] for i in range(1, n): t = math.gcd(t, arr[i]-arr[0]) # Iterating for each of m queries for j in range(m): x = q[j] # finding the gcd for each query with # their absolute since subtraction # can be negative res.append(abs(math.gcd(t, arr[0]-x))) return resarr = [9, 13, 17, 25]q = [1, 3, 5, 9]n = len(arr)m = len(q)ans = findGCDBySubtractingX(arr, q, n, m)for x in ans: print(x, end=" ") |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to Calculate GCD for each query public static List<int> findGCDBySubtractingX(int[] arr, int[] Q, int N, int M) { int T = 0; List<int> res = new List<int>(); // Find GCD of arr[1] - arr[0], arr[2] - arr[0], // . . ., arr[N - 1] - arr[0] for (int i = 1; i < N; i++) { T = gcd(T, arr[i] - arr[0]); } // Iterating for each of M Queries for (int j = 0; j < M; j++) { int X = Q[j]; // Finding GCD for each query with // their absolute since subtraction // can be negative res.Add(Math.Abs(gcd(T, arr[0] - X))); } return res; } static public void Main() { // Input int[] arr = { 9, 13, 17, 25 }; int[] Q = { 1, 3, 5, 9 }; int N = arr.Length; int M = Q.Length; // Function Call List<int> ans = findGCDBySubtractingX(arr, Q, N, M); foreach(int x in ans) Console.Write(x + " "); }}// This code is contributed by lokesh. |
Javascript
// JavaScript code to implement the approach// function to find gcd function __gcd(a, b){ if(b==0) return a; else return __gcd(b, a%b);}// Function to Calculate GCD for each queryfunction findGCDBySubtractingX(arr, Q, N, M){ let T = 0; let res=[]; // Find GCD of arr[1] - arr[0], arr[2] - arr[0], // . . ., arr[N - 1] - arr[0] for (let i = 1; i < N; i++) { T = __gcd(T, arr[i] - arr[0]); } // Iterating for each of M Queries for (let j = 0; j < M; j++) { let X = Q[j]; // Finding GCD for each query with // their absolute since subtraction // can be negative res.push(Math.abs(__gcd(T, arr[0] - X))); } return res;}// Driver Code // Input let arr = [ 9, 13, 17, 25 ], Q = [ 1, 3, 5, 9 ]; let N = arr.length; let M = Q.length; // Function Call let ans = findGCDBySubtractingX(arr, Q, N, M); for (let x of ans) console.log(x + " "); // This code is contributed by poojaagarwal2. |
4 2 4 4
Time Complexity: O(N * logD + M * logD) where D is the maximum element in the array
Auxiliary Space: O(1)
Related Articles:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
