Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The Problem Statement
2.1.
Geometric Progression
2.2.
Example
3.
Approach 
3.1.
Algorithm
3.2.
Program
3.3.
Input
3.4.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Ujjawal Gupta
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

One day, ninja's teacher gave him the assignment to calculate the count of distinct integers belonging to first ‘N’ terms of at least one of the two given Geometric Progression Series. Help ninja to pass the assignment.

The above problem is the common number series coding problem. Number series based-coding problems are widely asked in coding contests and various coding interviews.

In this blog, we will solve the above problem.

The Problem Statement

You are given integers, ‘A1’, ‘A2’,’ R1’,’ R2’ and ‘N’ where ‘A1’ and ‘A2’ represent the first term of both GPs and ‘R1’‘R2’ represents the common ratio of the GPs respectively. Your task is to calculate the count of all distinct integers which belong to the first ‘N’ terms of at least one GP.

Geometric Progression

A Geometric Progression(GP) is a sequence of numbers that differ from each other by a common ratio.

Example

Suppose, A1 = 2, A2 = 3, R1 = 3, R2 = 2, N = 2.  

2,6 belongs to the first GP, whereas 3,6 belongs to the second GP. Hence the distinct integers are 2,3,6. Therefore the total count of distinct integers that belongs to the first two terms of at least one GP is 3.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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!

 

Previous article
Cycle and cord
Next article
Connect Chords
Live masterclass