Given an integer K and an array arr[] of N integers, each of which is the first term and common difference of an Arithmetic Progression, the task is to find the Kth element of the set S formed by merging the N arithmetic progressions.
Examples:
Input: arr[] = {2, 3}, K = 10
Output: 15
Explanation:
There are 2 arithmetic progressions.
First-term and the common difference of the first A.P is 2. Therefore AP1 = {2, 4, 6, …}
First term and the common difference of the second A.P is 3. Therefore AP2 = {3, 6, 9, …}
Set S contains AP1 and AP2, i.e. { 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20…… }.
Hence 10th term is: 15Input: arr[] = {2, 3, 5, 7, 11}, K = 8
Output: 9
Explanation:
There are 5 arithmetic progressions.
First-term and the common difference of the first A.P is 2. Therefore AP1 = {2, 4, 6, …}
First term and the common difference of the second A.P is 3. Therefore AP2 = {3, 6, 9, …}
First-term and the common difference of the third A.P is 5. Therefore AP3 = {5, 10, 15, …}
First term and the common difference of the fourth A.P is 7. Therefore AP4 = {7, 14, 21, …}
First-term and the common difference of the fifth A.P is 11. Therefore AP5 = {11, 22, 33, …}
Thus set S contains { 2, 3, 4, 5, 6, 7, 8, 9, 10, …. }.
Hence 8th term is: 9
Approach:
Follow the steps below to solve the problem:
- Consider a range of [1, maxm] and compute mid of that range.
- Check if K elements can be obtained by merging the N series’. If the number of terms exceeds K, reduce R to mid. Otherwise, update L to mid. Now, proceed further until we find a mid for which exactly K terms in the series can be obtained.
- To find how many elements will occur before any particular value, we need to apply Inclusion and Exclusion principle to obtain union of all A.P.s.
Below is the implementation of the above approach:
C++
// C++ program to find k-th term of// N merged Arithmetic Progressions#include <bits/stdc++.h>using namespace std;#define maxm 1000000000// Function to count and return the// number of values less than equal// to N present in the setint count(vector<int> v, int n){ int i, odd = 0, even = 0; int j, d, count; int t = (int)1 << v.size(); int size = v.size(); for (i = 1; i < t; i++) { d = 1, count = 0; for (j = 0; j < size; j++) { // Check whether j-th bit // is set bit or not if (i & (1 << j)) { d *= v[j]; count++; } } if (count & 1) odd += n / d; else even += n / d; } return (odd - even);}// Function to implement Binary// Search to find K-th elementint BinarySearch(int l, int r, vector<int> v, int key){ int mid; while (r - l > 1) { // Find middle index of // the array mid = (l + r) / 2; // Search in the left half if (key <= count(v, mid)) { r = mid; } // Search in the right half else { l = mid; } } // If exactly K elements // are present if (key == count(v, l)) return l; else return r;}// Driver Codeint main(){ int N = 2, K = 10; vector<int> v = { 2, 3 }; cout << BinarySearch(1, maxm, v, K) << endl; return 0;} |
Java
// Java program to find k-th term of// N merged Arithmetic Progressionsimport java.util.*;class GFG{static final int maxm = 1000000000;// Function to count and return the// number of values less than equal// to N present in the setstatic int count(int []v, int n){ int i, odd = 0, even = 0; int j, d, count; int t = (int)1 << v.length; int size = v.length; for (i = 1; i < t; i++) { d = 1; count = 0; for (j = 0; j < size; j++) { // Check whether j-th bit // is set bit or not if ((i & (1 << j)) > 0) { d *= v[j]; count++; } } if (count % 2 == 1) odd += n / d; else even += n / d; } return (odd - even);}// Function to implement Binary// Search to find K-th elementstatic int BinarySearch(int l, int r, int []v, int key){ int mid; while (r - l > 1) { // Find middle index of // the array mid = (l + r) / 2; // Search in the left half if (key <= count(v, mid)) { r = mid; } // Search in the right half else { l = mid; } } // If exactly K elements // are present if (key == count(v, l)) return l; else return r;}// Driver Codepublic static void main(String[] args){ int N = 2, K = 10; int []v = { 2, 3 }; System.out.print(BinarySearch(1, maxm, v, K) + "\n");}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to find k-th term of # N merged Arithmetic Progressions maxm = 1000000000# Function to count and return the # number of values less than equal # to N present in the set def count(v, n): odd, even = 0, 0 t = 1 << len(v) size = len(v) for i in range(1, t): d, count = 1, 0 for j in range(0, size): # Check whether j-th bit # is set bit or not if (i & (1 << j)): d *= v[j] count += 1 if (count & 1): odd += n // d else: even += n // d return (odd - even)# Function to implement Binary # Search to find K-th element def BinarySearch(l, r, v, key): while (r - l > 1): # Find middle index of # the array mid = (l + r) // 2 # Search in the left half if (key <= count(v, mid)): r = mid # Search in the right half else: l = mid # If exactly K elements # are present if (key == count(v, l)): return l else: return r # Driver CodeN, K = 2, 10v = [ 2, 3 ] print(BinarySearch(1, maxm, v, K))# This code is contributed by divyeshrabadiya07 |
C#
// C# program to find k-th term of// N merged Arithmetic Progressionsusing System;class GFG{ static readonly int maxm = 1000000000;// Function to count and return the// number of values less than equal// to N present in the setstatic int count(int []v, int n){ int i, odd = 0, even = 0; int j, d, count; int t = (int)1 << v.Length; int size = v.Length; for(i = 1; i < t; i++) { d = 1; count = 0; for(j = 0; j < size; j++) { // Check whether j-th bit // is set bit or not if ((i & (1 << j)) > 0) { d *= v[j]; count++; } } if (count % 2 == 1) odd += n / d; else even += n / d; } return (odd - even);}// Function to implement Binary// Search to find K-th elementstatic int BinarySearch(int l, int r, int []v, int key){ int mid; while (r - l > 1) { // Find middle index of // the array mid = (l + r) / 2; // Search in the left half if (key <= count(v, mid)) { r = mid; } // Search in the right half else { l = mid; } } // If exactly K elements // are present if (key == count(v, l)) return l; else return r;}// Driver Codepublic static void Main(String[] args){ //int N = 2; int K = 10; int []v = { 2, 3 }; Console.Write(BinarySearch( 1, maxm, v, K) + "\n");}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program to find k-th term of// N merged Arithmetic Progressionslet maxm = 1000000000;// Function to count and return the// number of values less than equal// to N present in the setfunction count(v, n){ let i, odd = 0, even = 0; let j, d, count; let t = 1 << v.length; let size = v.length; for (i = 1; i < t; i++) { d = 1; count = 0; for (j = 0; j < size; j++) { // Check whether j-th bit // is set bit or not if ((i & (1 << j)) > 0) { d *= v[j]; count++; } } if (count % 2 == 1) odd += n / d; else even += n / d; } return (odd - even);}// Function to implement Binary// Search to find K-th elementfunction BinarySearch(l, r, v, key){ let mid; while (r - l > 1) { // Find middle index of // the array mid = Math.floor((l + r) / 2); // Search in the left half if (key <= count(v, mid)) { r = mid; } // Search in the right half else { l = mid; } } // If exactly K elements // are present if (key == count(v, l)) return l; else return r;} // Driver Code let N = 2, K = 10; let v = [ 2, 3 ]; document.write(BinarySearch(1, maxm, v, K) + "\n");</script> |
Output:
15
Time Complexity: O(N * 2N)
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!
