# Count of distinct integers belonging to first N terms of at least one of given GPs

Given two Geometric Progressions** (a1, r1)** and **(a2, r2)** where **(x, y) **represents **GP** with initial term **x ** and common ratio **y **and an integer **N**, the task is to find the count of the distinct integers that belong to the first **N** terms of at least one of the given geometric progressions.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 5, a1 = 3, r1 = 2, a2 = 6, r2 = 2Output:6Explanation:The first 5 terms of the given geometric progressions are {3, 6, 12, 24, 48} and {6, 12, 24, 48, 96} respectively. Hence, the total count of distinct integers in the GP is 6.

Input:N = 5, a1 = 3, r1 = 2, a2 = 2, r2 = 3Output:9Explanation:The first 5 terms of the given geometric progressions are {3, 6, 12, 24, 48} and {2, 6, 18, 54, 162} respectively. Hence, the total count of distinct integers in the GP is 9.

**Approach:** The given problem can be solved by the observation that the total count of distinct integers can be calculated by generating the first N terms of both the Geometric Progressions and removing the duplicates terms. This can be achieved by the use of the set data structure. Firstly, generate all the N terms of the 1^{st} GP and insert the terms into a set **S**. Similarly, insert the terms of the 2^{nd} GP into the set **S**. The size of the set **S** is the required answer.

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 count of distinct` `// integers that belong to the first N` `// terms of at least one of them is GP` `int` `UniqueGeometricTerms(` `int` `N, ` `int` `a1,` ` ` `int` `r1, ` `int` `a2,` ` ` `int` `r2)` `{` ` ` `// Stores the integers that occur in` ` ` `// GPs in a set data-structure` ` ` `set<` `int` `> S;` ` ` `// Stores the current integer of` ` ` `// the first GP` ` ` `long` `long` `p1 = a1;` ` ` `// Iterate first N terms of first GP` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Insert the ith term of GP in S` ` ` `S.insert(p1);` ` ` `p1 = (` `long` `long` `)(p1 * r1);` ` ` `}` ` ` `// Stores the current integer` ` ` `// of the second GP` ` ` `long` `long` `p2 = a2;` ` ` `// Iterate first N terms of second GP` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `S.insert(p2);` ` ` `p2 = (` `long` `long` `)(p2 * r2);` ` ` `}` ` ` `// Return Answer` ` ` `return` `S.size();` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 5;` ` ` `int` `a1 = 3, r1 = 2, a2 = 2, r2 = 3;` ` ` `cout << UniqueGeometricTerms(` ` ` `N, a1, r1, a2, r2);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG` `{` `// Function to find the count of distinct` `// integers that belong to the first N` `// terms of at least one of them is GP` `static` `int` `UniqueGeometricTerms(` `int` `N, ` `int` `a1,` ` ` `int` `r1, ` `int` `a2,` ` ` `int` `r2)` `{` ` ` `// Stores the integers that occur in` ` ` `// GPs in a set data-structure` ` ` `HashSet<Integer> S=` `new` `HashSet<Integer>();` ` ` `// Stores the current integer of` ` ` `// the first GP` ` ` `int` `p1 = a1;` ` ` `// Iterate first N terms of first GP` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `// Insert the ith term of GP in S` ` ` `S.add(p1);` ` ` `p1 = (p1 * r1);` ` ` `}` ` ` `// Stores the current integer` ` ` `// of the second GP` ` ` `int` `p2 = a2;` ` ` `// Iterate first N terms of second GP` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `S.add(p2);` ` ` `p2 = (p2 * r2);` ` ` `}` ` ` `// Return Answer` ` ` `return` `S.size();` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `5` `;` ` ` `int` `a1 = ` `3` `, r1 = ` `2` `, a2 = ` `2` `, r2 = ` `3` `;` ` ` `System.out.print(UniqueGeometricTerms(` ` ` `N, a1, r1, a2, r2));` `}` `}` `// This code is contributed by shikhasingrajput` |

## Python3

`# Python 3 program for the above approach` `# Function to find the count of distinct` `# integers that belong to the first N` `# terms of at least one of them is GP` `def` `UniqueGeometricTerms(N, a1, r1, a2, r2):` ` ` ` ` `# Stores the integers that occur in` ` ` `# GPs in a set data-structure` ` ` `S ` `=` `set` `()` ` ` `# Stores the current integer of` ` ` `# the first GP` ` ` `p1 ` `=` `a1` ` ` `# Iterate first N terms of first GP` ` ` `for` `i ` `in` `range` `(N):` ` ` ` ` `# Insert the ith term of GP in S` ` ` `S.add(p1)` ` ` `p1 ` `=` `(p1 ` `*` `r1)` ` ` `# Stores the current integer` ` ` `# of the second GP` ` ` `p2 ` `=` `a2` ` ` `# Iterate first N terms of second GP` ` ` `for` `i ` `in` `range` `(N):` ` ` `S.add(p2)` ` ` `p2 ` `=` `(p2 ` `*` `r2)` ` ` `# Return Answer` ` ` `return` `len` `(S)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `N ` `=` `5` ` ` `a1 ` `=` `3` ` ` `r1 ` `=` `2` ` ` `a2 ` `=` `2` ` ` `r2 ` `=` `3` ` ` `print` `(UniqueGeometricTerms(N, a1, r1, a2, r2))` ` ` `# This code is contributed by SURENDRA_GANGWAR.` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections.Generic;` `public` `class` `GFG` `{` `// Function to find the count of distinct` `// integers that belong to the first N` `// terms of at least one of them is GP` `static` `int` `UniqueGeometricTerms(` `int` `N, ` `int` `a1,` ` ` `int` `r1, ` `int` `a2,` ` ` `int` `r2)` `{` ` ` `// Stores the integers that occur in` ` ` `// GPs in a set data-structure` ` ` `HashSet<` `int` `> S=` `new` `HashSet<` `int` `>();` ` ` `// Stores the current integer of` ` ` `// the first GP` ` ` `int` `p1 = a1;` ` ` `// Iterate first N terms of first GP` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Insert the ith term of GP in S` ` ` `S.Add(p1);` ` ` `p1 = (p1 * r1);` ` ` `}` ` ` `// Stores the current integer` ` ` `// of the second GP` ` ` `int` `p2 = a2;` ` ` `// Iterate first N terms of second GP` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `S.Add(p2);` ` ` `p2 = (p2 * r2);` ` ` `}` ` ` `// Return Answer` ` ` `return` `S.Count;` `}` `// Driver Code` `public` `static` `void` `Main(` `string` `[] args)` `{` ` ` `int` `N = 5;` ` ` `int` `a1 = 3, r1 = 2, a2 = 2, r2 = 3;` ` ` `Console.Write(UniqueGeometricTerms(` ` ` `N, a1, r1, a2, r2));` `}` `}` `// This code is contributed by AnkThon` |

## Javascript

`<script>` ` ` `// JavaScript Program to implement` ` ` `// the above approach` ` ` `// Function to find the count of distinct` ` ` `// integers that belong to the first N` ` ` `// terms of at least one of them is GP` ` ` `function` `UniqueGeometricTerms(N, a1,` ` ` `r1, a2,` ` ` `r2)` ` ` `{` ` ` ` ` `// Stores the integers that occur in` ` ` `// GPs in a set data-structure` ` ` `let S = ` `new` `Set();` ` ` ` ` `// Stores the current integer of` ` ` `// the first GP` ` ` `let p1 = a1;` ` ` `// Iterate first N terms of first GP` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `// Insert the ith term of GP in S` ` ` `S.add(p1);` ` ` `p1 = (p1 * r1);` ` ` `}` ` ` `// Stores the current integer` ` ` `// of the second GP` ` ` `let p2 = a2;` ` ` `// Iterate first N terms of second GP` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `S.add(p2);` ` ` `p2 = (p2 * r2);` ` ` `}` ` ` `// Return Answer` ` ` `return` `S.size;` ` ` `}` ` ` `// Driver Code` ` ` `let N = 5;` ` ` `let a1 = 3, r1 = 2, a2 = 2, r2 = 3;` ` ` `document.write(UniqueGeometricTerms(` ` ` `N, a1, r1, a2, r2));` ` ` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output:**

9

**Time Complexity:** O(N*log N)**Auxiliary Space:** O(N)