A geometric progression is a sequence of integers b1, b2, b3, …, where for each i > 1, the respective term satisfies the condition bi = bi-1 * q, where q is called the common ratio of the progression.
Given geometric progression b defined by two integers b1 and q, and m “bad” integers a1, a2, .., am, and an integer l, write all progression terms one by one (including repetitive) while the condition |bi| <= l is satisfied (|x| means the absolute value of x).
Calculate how many numbers there will be in our sequence, or print “inf” if there are infinitely many integers.
Note: If a term equals one of the “bad” integers, skip it and move forward to the next term.
Examples:
Input : b1 = 3, q = 2, l = 30,
m = 4
6 14 25 48
Output : 3
The progression will be 3 12 24.
6 will also be there but because
it is a bad integer we won't include it
Input : b1 = 123, q = 1, l = 2143435
m = 4
123 11 -5453 141245
Output : 0
As value of q is 1, progression will
always be 123 and would become infinity
but because it is a bad integer we
won't include it and hence our value
will become 0
Input : b1 = 123, q = 1, l = 2143435
m = 4
5234 11 -5453 141245
Output : inf
In this case, value will be infinity
because series will always be 123 as
q is 1 and 123 is not a bad integer.
Approach:
We can divide our solution into different cases:
Case 1: If the starting value of a series is greater than the given limit, output is 0.
Case 2: If the starting value of a series q is 0, there are three more cases:
Case 2.a: If 0 is not given as a bad integer, the answer will become inf.
Case 2.b: If b1 != 0 but q is 0 and b1 is also not a bad integer, the answer will be 1.
Case 2.c: If 0 is given as a bad integer and b1 = 0, the answer will be 0.
Case 3: If q = 1, we will check if b1 is given as a bad integer or not. If it is, then the answer will be 0, else the answer will be inf.
Case 4: If q = -1, check if b1 and -b1 are present or not. If they are present, our answer will be 0, else our answer will be inf.
Case 5: If none of the above cases hold, simply run a loop from b1 to l and calculate the number of elements.
Below is the implementation of the above approach:
C++
// CPP program to find number of terms // in Geometric Series#include <bits/stdc++.h>using namespace std;// A map to keep track of the bad integersmap<int, bool> mapp; // Function to calculate No. of elements// in our seriesvoid progression(int b1, int q, int l, int m, int bad[]){ // Updating value of our map for (int i = 0; i < m; i++) mapp[bad[i]] = 1; // if starting value is greater // than our given limit if (abs(b1) > l) cout << "0"; // if q or starting value is 0 else if (q == 0 || b1 == 0) { // if 0 is not a bad integer, // answer becomes inf if (mapp[0] != 1) cout << "inf"; // if q is 0 and b1 is not and b1 // is not a bad integer, answer becomes 1 else if (mapp[0] == 1 && mapp[b1] != 1) cout << "1"; else // else if 0 is bad integer and // b1 is also a bad integer, // answer becomes 0 cout << "0"; } else if (q == 1) // if q is 1 { // and b1 is not a bad integer, // answer becomes inf if (mapp[b1] != 1) cout << "inf"; else // else answer is 0 cout << "0"; } else if (q == -1) // if q is -1 { // and either b1 or -b1 is not // present answer becomes inf if (mapp[b1] != 1 || mapp[-1 * b1] != 1) cout << "inf"; else // else answer becomes 0 cout << "0"; } else // if none of the above case is true, // simply calculate the number of // elements in our series { int co = 0; while (abs(b1) <= l) { if (mapp[b1] != 1) co++; b1 *= 1LL * q; } cout << co; }}// driver codeint main(){ // starting value of series, // number to be multiplied, // limit within which our series, // No. of bad integers given int b1 = 3, q = 2, l = 30, m = 4; // Bad integers int bad[4] = { 6, 14, 25, 48 }; progression(b1, q, l, m, bad); return 0;} |
Java
// Java program to find number of terms // in Geometric Seriesimport java.util.*;class GFG { // A map to keep track of the bad integers static HashMap<Integer, Boolean> map = new HashMap<>(); // Function to calculate No. of elements // in our series static void progression(int b1, int q, int l, int m, int[] bad) { // Updating value of our map for (int i = 0; i < m; i++) map.put(bad[i], true); // if starting value is greater // than our given limit if (Math.abs(b1) > l) System.out.print("0"); // if q or starting value is 0 else if (q == 0 || b1 == 0) { // if 0 is not a bad integer, // answer becomes inf if (!map.containsKey(0)) System.out.print("inf"); // if q is 0 and b1 is not and b1 // is not a bad integer, answer becomes 1 else if (map.get(0) == true && !map.containsKey(b1)) System.out.print("1"); // else if 0 is bad integer and // b1 is also a bad integer, // answer becomes 0 else System.out.print("0"); } // if q is 1 else if (q == 1) { // and b1 is not a bad integer, // answer becomes inf if (!map.containsKey(b1)) System.out.print("inf"); // else answer is 0 else System.out.print("0"); } // if q is -1 else if (q == -1) { // and either b1 or -b1 is not // present answer becomes inf if (!map.containsKey(b1) || !map.containsKey(-1 * b1)) System.out.print("inf"); // else answer becomes 0 else System.out.print("0"); } // if none of the above case is true, // simply calculate the number of // elements in our series else { int co = 0; while (Math.abs(b1) <= l) { if (!map.containsKey(b1)) co++; b1 *= q; } System.out.print(co); } } // Driver Code public static void main(String[] args) { // starting value of series, // number to be multiplied, // limit within which our series, // No. of bad integers given int b1 = 3, q = 2, l = 30, m = 4; // Bad integers int[] bad = { 6, 14, 25, 48 }; progression(b1, q, l, m, bad); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 program to find number of terms# in Geometric Series# A map to keep track of the bad integersmpp=dict()# Function to calculate No. of elements# in our seriesdef progression(b1, q, l, m, bad): # Updating value of our map for i in range(m): mpp[bad[i]] = 1 # if starting value is greater # than our given limit if (abs(b1) > l): print("0",end="") # if q or starting value is 0 elif (q == 0 or b1 == 0) : # if 0 is not a bad integer, # answer becomes inf if (0 not in mpp.keys()): print("inf",end="") # if q is 0 and b1 is not and b1 # is not a bad integer, answer becomes 1 elif (mpp[0] == 1 and b1 not in mpp.keys()) : print("1",end="") else: # b1 is also a bad integer, # answer becomes 0 print("0",end="") elif (q == 1): # if q is 1 # and b1 is not a bad integer, # answer becomes inf if (b1 not in mpp.keys()) : print("inf",end="") else: # else answer is 0 print("0",end="") elif (q == -1): # if q is -1 # and either b1 or -b1 is not # present answer becomes inf if (b1 not in mpp.keys() or -1 * b1 not in mpp.keys()) : print("inf",end="") else :# else answer becomes 0 print("0",end="") else :# if none of the above case is true, # simply calculate the number of # elements in our series co = 0 while (abs(b1) <= l): if (b1 not in mpp.keys()): co+=1 b1 *= q print(co,end="")# Driver code# starting value of series,# number to be multiplied,# limit within which our series,# No. of bad integers givenb1 = 3q = 2l = 30m = 4# Bad integersbad=[6, 14, 25, 48]progression(b1, q, l, m, bad)# This code is contributed by mohit kumar 29 |
C#
// C# program to find number of terms // in Geometric Seriesusing System;using System.Collections.Generic;class GFG { // A map to keep track of the bad integers static Dictionary<int, bool> map = new Dictionary<int, bool>(); // Function to calculate No. of elements // in our series static void progression(int b1, int q, int l, int m, int[] bad) { // Updating value of our map for (int i = 0; i < m; i++) if(!map.ContainsKey(bad[i])) map.Add(bad[i], true); // if starting value is greater // than our given limit if (Math.Abs(b1) > l) Console.Write("0"); // if q or starting value is 0 else if (q == 0 || b1 == 0) { // if 0 is not a bad integer, // answer becomes inf if (!map.ContainsKey(0)) Console.Write("inf"); // if q is 0 and b1 is not and b1 // is not a bad integer, answer becomes 1 else if (map[0] == true && !map.ContainsKey(b1)) Console.Write("1"); // else if 0 is bad integer and // b1 is also a bad integer, // answer becomes 0 else Console.Write("0"); } // if q is 1 else if (q == 1) { // and b1 is not a bad integer, // answer becomes inf if (!map.ContainsKey(b1)) Console.Write("inf"); // else answer is 0 else Console.Write("0"); } // if q is -1 else if (q == -1) { // and either b1 or -b1 is not // present answer becomes inf if (!map.ContainsKey(b1) || !map.ContainsKey(-1 * b1)) Console.Write("inf"); // else answer becomes 0 else Console.Write("0"); } // if none of the above case is true, // simply calculate the number of // elements in our series else { int co = 0; while (Math.Abs(b1) <= l) { if (!map.ContainsKey(b1)) co++; b1 *= q; } Console.Write(co); } } // Driver Code public static void Main(String[] args) { // starting value of series, // number to be multiplied, // limit within which our series, // No. of bad integers given int b1 = 3, q = 2, l = 30, m = 4; // Bad integers int[] bad = { 6, 14, 25, 48 }; progression(b1, q, l, m, bad); }}// This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to find number of terms // in Geometric Series // A map to keep track of the bad integers let map = new Map(); // Function to calculate No. of elements // in our series function progression(b1,q,l,m,bad) { // Updating value of our map for (let i = 0; i < m; i++) map.set(bad[i], true); // if starting value is greater // than our given limit if (Math.abs(b1) > l) document.write("0"); // if q or starting value is 0 else if (q == 0 || b1 == 0) { // if 0 is not a bad integer, // answer becomes inf if (!map.has(0)) document.write("inf"); // if q is 0 and b1 is not and b1 // is not a bad integer, answer becomes 1 else if (map[0] == true && !map.has(b1)) document.write("1"); // else if 0 is bad integer and // b1 is also a bad integer, // answer becomes 0 else document.write("0"); } // if q is 1 else if (q == 1) { // and b1 is not a bad integer, // answer becomes inf if (!map.has(b1)) document.write("inf"); // else answer is 0 else document.write("0"); } // if q is -1 else if (q == -1) { // and either b1 or -b1 is not // present answer becomes inf if (!map.has(b1) || !map.has(-1 * b1)) document.write("inf"); // else answer becomes 0 else document.write("0"); } // if none of the above case is true, // simply calculate the number of // elements in our series else { let co = 0; while (Math.abs(b1) <= l) { if (!map.has(b1)) co++; b1 *= q; } document.write(co); } } // Driver Code // starting value of series, // number to be multiplied, // limit within which our series, // No. of bad integers given let b1 = 3, q = 2, l = 30, m = 4; // Bad integers let bad = [ 6, 14, 25, 48 ]; progression(b1, q, l, m, bad); // This code is contributed by patel2127</script> |
Output:
3
Time Complexity: O(m+logq(l))
Auxiliary Space: O(m)
If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.uk or mail your article to review-team@neveropen.co.uk. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
