Counting elements with GCD in range of A, modified to B
Given two arrays A and B with lengths N and M respectively, the problem is to count the number of elements in array B that are equal to the greatest common divisor (gcd) of a specific range in array A, where the range is defined by two indices L and R. You are allowed to change one element in the range to make the gcd equal to an element in B. However, this change is only applied to that specific element in B and you can perform another operation for a different element in B if required.
Examples:
Input: N = 2, L = 1, R = 2, A = [2, 2], M = 2, B = [2, 2]
Output: 2
Explanation: The gcd of the range is (L, R) 1-based indexing is 2 and all the elements of the array B are equal to 2. So every B[i]=gcd.
So the answer is 2.Input:- N = 3, L = 1, R = 3, A = [3, 2, 3], M = 3, B = [3, 1, 3]
Output:- 3
Explanation:- For B[0] and B[2] we will change element A[1] to 3 then the range will look like this [3, 3, 3] and the gcd of the range will become 3 same as B[0] and B[2] and for B[1] which is 1 there is no need to change an element as gcd is already equal to 1.
Hence the answer is 3.
Approach: To solve the problem follow the below idea:
We will use a greedy approach to calculate the gcd of the range (L, R) in decreasing manner. So we will start traversing the range from the maximum element to the minimum element so our gcd will be in decreasing order.
Illustration:
Let’s understand this also with an example.
- Say A = [3, 2, 3] after putting them in priority_queue(Max heap) they will be pop in the manner 3->3->2 and side by side we will calculate gcd with each element and this into an array temp which will look like this [3, 3, 1] means first three is the gcd of 3 and second 3 is the gcd of (3, 3) and third 1 is the gcd of (3, 3, 2).
- So take array B = [3]. In this case the complete gcd of the series is 1 which is lesser than 3 but we can make gcd to 3 by changing A[1]->3 that is making A = [3, 3, 3]
- So it means we can make B[i] = gcd by changing at most one element and how do we come to know that we can do this because if we look into our array temp = [3, 3, 1] the second smallest element is equal to B[i] that is why we can do this. I hope the third case is now clear.
Steps that were to follow the above approach:
- Here, we will use priority_queue(max heap) which will give us elements in decreasing order and we will store our gcd after each element in an array temp.
- We will take an ans variable ans=0 which will store our answer.
- After this, we will traverse the given array B and there can be three possibilities between the gcd of the range and element B[i] which are given below:
- First Case: gcd equal to B[i], then we will increment our answer.
- Second Case: gcd is greater than B[i] then we will look if gcd%B[i]==0, If so then we will increase our answer and why this will work suppose we have an array A like [6, 12, 30] and L=1, R=3. So the gcd of the range will be 6 and suppose there is only one element in array B = [3] then gcd%B[0]==0 that is 6 is divisible by 3 so it means that we can make our gcd of the array to 3 by changing only one element to 3.
- Third Case:
gcd is lower than B[i] so in this case we will look into the second smallest gcd of the array as we have taken the gcd’s in an array in step 4, So if it equals B[i] it means that the element which is making gcd<B[i] we can change it to another element and gcd will become gcd = B[i].
Below is the code to implement the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // function to get Answer int maximumElements( int n, int l, int r, int m, vector< int >& a, vector< int >& b) { // Taking Max Heap priority_queue< int > pq; // Putting element of range (L, R) // into pq for ( int i = l - 1; i < r; i++) { pq.push(a[i]); } // Array to store gcd at each point // as explained in approach vector< int > temp; // Taking g to store gcd of range int g = pq.top(); pq.pop(); temp.push_back(g); // Calculating gcd in decreasing // manner while (pq.size() != 0) { // Taking gcd of each element // with current gcd g = __gcd(g, pq.top()); // Storing gcd into array temp.push_back(g); pq.pop(); } // Variable to store total // elements count int ans = 0; // Iterating array B for ( int i = 0; i < m; i++) { // First Case if (b[i] == g) ans++; // Second Case else if (b[i] < g) { if (g % b[i] == 0) ans++; } // Third Case else { if (temp[temp.size() - 2] == b[i]) ans++; } } return ans; } // Drivers code int main() { // Intital values int n = 3, l = 1, r = 3, m = 3; // Array A vector< int > a = { 3, 2, 3 }; // Array B vector< int > b = { 3, 1, 3 }; // Calling function and printing // result cout << maximumElements(n, l, r, m, a, b) << endl; return 0; } |
Java
import java.util.*; public class Main { // function to get Answer public static int maximumElements( int n, int l, int r, int m, List<Integer> a, List<Integer> b) { // Taking Max Heap PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // Putting element of range (L, R) into pq for ( int i = l - 1 ; i < r; i++) { pq.offer(a.get(i)); } // Array to store gcd at each point as explained in approach List<Integer> temp = new ArrayList<>(); // Taking g to store gcd of range int g = pq.poll(); temp.add(g); // Calculating gcd in decreasing manner while (!pq.isEmpty()) { // Taking gcd of each element with current gcd g = gcd(g, pq.poll()); // Storing gcd into array temp.add(g); } // Variable to store total elements count int ans = 0 ; // Iterating array B for ( int i = 0 ; i < m; i++) { // First Case if (b.get(i) == g) { ans++; } // Second Case else if (b.get(i) < g) { if (g % b.get(i) == 0 ) { ans++; } } // Third Case else { if (temp.get(temp.size() - 2 ) == b.get(i)) { ans++; } } } return ans; } // utility function to find gcd public static int gcd( int a, int b) { if (b == 0 ) { return a; } return gcd(b, a % b); } // Drivers code public static void main(String[] args) { // Intital values int n = 3 , l = 1 , r = 3 , m = 3 ; // Array A List<Integer> a = new ArrayList<>(Arrays.asList( 3 , 2 , 3 )); // Array B List<Integer> b = new ArrayList<>(Arrays.asList( 3 , 1 , 3 )); // Calling function and printing result System.out.println(maximumElements(n, l, r, m, a, b)); } } // This code is contributed by Prajwal Kandekar |
Python3
import heapq import math def maximumElements(n, l, r, m, a, b): # Taking Max Heap pq = [] for i in range (l - 1 , r): heapq.heappush(pq, - a[i]) # Array to store gcd at each point # as explained in approach temp = [] # Taking g to store gcd of range g = - heapq.heappop(pq) temp.append(g) # Calculating gcd in decreasing # manner while len (pq) ! = 0 : # Taking gcd of each element # with current gcd g = math.gcd(g, - heapq.heappop(pq)) # Storing gcd into array temp.append(g) # Variable to store total # elements count ans = 0 # Iterating array B for i in range (m): # First Case if b[i] = = g: ans + = 1 # Second Case elif b[i] < g: if g % b[i] = = 0 : ans + = 1 # Third Case else : if temp[ - 2 ] = = b[i]: ans + = 1 return ans # Driver code n = 3 l = 1 r = 3 m = 3 a = [ 3 , 2 , 3 ] b = [ 3 , 1 , 3 ] print (maximumElements(n, l, r, m, a, b)) |
C#
using System; using System.Collections.Generic; public class GFG { // Function to get Answer public static int MaximumElements( int n, int l, int r, int m, List< int > a, List< int > b) { // HashSet to store unique values from the range (L, R) HashSet< int > uniqueValues = new HashSet< int >(); // Putting element of range (L, R) into HashSet for ( int i = l - 1; i < r; i++) { uniqueValues.Add(a[i]); } // Variable to store the total elements count int ans = 0; // Iterating array B foreach ( int num in b) { // First Case if (uniqueValues.Contains(num)) { ans++; } // Second Case else if (num < a[l - 1] && a[l - 1] % num == 0) { ans++; } } return ans; } // Driver code public static void Main( string [] args) { // Initial values int n = 3, l = 1, r = 3, m = 3; // Array A List< int > a = new List< int > { 3, 2, 3 }; // Array B List< int > b = new List< int > { 3, 1, 3 }; // Calling function and printing result Console.WriteLine(MaximumElements(n, l, r, m, a, b)); } } |
Javascript
// Javascript code for the above approach // Implementation of Priority Queue class PriorityQueue { constructor() { this .queue = []; } enqueue(item, priority) { this .queue.push({ item, priority }); this .queue.sort((a, b) => a.priority - b.priority); } dequeue() { if ( this .isEmpty()) { return null ; } return this .queue.shift().item; } peek() { if ( this .isEmpty()) { return null ; } return this .queue[0].item; } isEmpty() { return this .queue.length === 0; } size() { return this .queue.length; } } // Function to get Answer function maximumElements(n, l, r, m, a, b) { // Taking Max Heap var pq = new PriorityQueue({ comparator: function (a, b) { return b - a; } }); // Putting element of range (L, R) // into pq for ( var i = l - 1; i < r; i++) { pq.enqueue(a[i]); } // Array to store gcd at each point // as explained in approach var temp = []; // Taking g to store gcd of range var g = pq.peek(); pq.dequeue(); temp.push(g); // Calculating gcd in decreasing // manner while (pq.isEmpty()) { // Taking gcd of each element // with current gcd g = gcd(g, pq.peek()); // Storing gcd into array temp.push(g); pq.dequeue(); } // Variable to store total // elements count var ans = 0; // Iterating array B for ( var i = 0; i < m; i++) { // First Case if (b[i] == g) ans++; // Second Case else if (b[i] < g) { if (g % b[i] == 0) ans++; } // Third Case else { if (temp[temp.length - 2] == b[i]) ans++; } } return ans; } // Function to calculate gcd function gcd(a, b) { if (b == 0) return a; return gcd(b, a % b); } // Drivers code // Intital values var n = 3, l = 1, r = 3, m = 3; // Array A var a = [3, 2, 3]; // Array B var b = [3, 1, 3]; // Calling function and printing // result console.log(maximumElements(n, l, r, m, a, b)); // This code is contributed by Tapesh(tapeshdua420) |
3
Time Complexity: O( max( NlogN, M ) ), where N*logN is due to the pushing and popping of elements of array A, from priority_queue, and M is due to traversing of elements from array B.
Auxiliary Space: O(N)