Count of Distinct Integers Belonging to First ‘N’ Terms of at least one of Given Geometric Progression Series(GPs)

Approach 

The above problem can be solved by generating the first ‘N’ terms of both the GPs and then removing the duplicate terms. The next term of a GP can be calculated by multiplying ‘R’ with ‘A’ where ‘R’ is the common ratio of GP, and ‘A’ is the previous term. 

Algorithm

• Define a function distinctIntegerCount():
  • Function details:
    • Takes ‘ A1’,’ R1’,’ A2’,’ R2’,’ N’ as a parameter.
    • This function returns the count of distinct integers.
  • Working: 
    • Declare a hash set of integers ‘S’ to store the first ‘N’ elements of both GPs.
    • Declare i = 0.
    • S.INSERT(A1).
    • S.INSERT(A2).
    • while(i != N):
      • Declare NEXT_TERMG1 = A1 * R1.
      • A1= NEXT_TERMG1.
      • S.INSERT(NEXT_TERMG1).
      • Declare NEXT_TERMG2 = A2 * R2.
      • A2 = NEXT_TERMG2.
      • S.INSERT(NEXT_TERMG2).
      • i++.
    • Create ‘ANS’ and store the size of ‘S’ in it.
    • Return ‘ANS’.
  • Call the function distinctIntegerCount() and pass ‘ A1’ , ‘ A2’ ,’ R1’ ,’ R2’ ,’ N’ in the function.

Program

#include <iostream>
#include <unordered_set>
using namespace std;

// Function definition.
int distinctIntegerCount(int a1, int r1, int a2, int r2, int n)
{

    // Create set to insert first 'N' elements of the sequence.
    unordered_set<int> s;
    int i = 1;

    // Insert 1st element of 1st series.
    s.insert(a1);

    // Insert 1st element of 2nd series.
    s.insert(a2);
    while (i != n)
    {

        // Inserting next term of first series.
        int nextTermG1 = a1 * r1;
        a1 = nextTermG1;
        s.insert(nextTermG1);

        // Inserting next term of second series.
        int nextTermG2 = a2 * r2;
        a2 = nextTermG2;
        s.insert(nextTermG2);
        i++;
    }

    int ans = s.size();
    return ans;
}
int main()
{

    // Taking input.
    int a1, a2, r1, r2, n;
    cin >> a1 >> r1 >> a2 >> r2 >> n;

    // Create variable 'ANS' to store the answer.
    int ans;

    // Function call.
    ans = distinctIntegerCount(a1, r1, a2, r2, n);
    cout << ans;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

2 3 3 2 2

Output

3

Time Complexity

O(N), where ‘N’ is the number of terms.

Generating the first ‘N’ elements of a GPs takes O(N).

Space Complexity

O(N), where ‘N’ is the number of terms.

Creating a set takes O(N) space.

Key Takeaways

In this blog, we learned about an interesting problem, namely the count of distinct integers belonging to first ‘N’ terms of at least one of the given geometric progression series. We solved the problem by generating all the ‘N’ terms of both the string and then inserting them in the set to remove the duplicates. Here, we have learned how to generate the whole GP series from starting term.

Therefore learning never stops, and there is a lot more to learn.
Check out this problem - Maximum Product Subarray

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!