Dadas dos Progresiones Geométricas (a1, r1) y (a2, r2) donde (x, y) representa GP con término inicial x y razón común y y un entero N , la tarea es encontrar el conteo de los distintos enteros que pertenecen a los primeros N términos de al menos una de las progresiones geométricas dadas.
Ejemplos:
Entrada: N = 5, a1 = 3, r1 = 2, a2 = 6, r2 = 2
Salida: 6
Explicación: Los primeros 5 términos de las progresiones geométricas dadas son {3, 6, 12, 24, 48} y {6 , 12, 24, 48, 96} respectivamente. Por lo tanto, el recuento total de enteros distintos en el GP es 6.Entrada: N = 5, a1 = 3, r1 = 2, a2 = 2, r2 = 3
Salida: 9
Explicación: Los primeros 5 términos de las progresiones geométricas dadas son {3, 6, 12, 24, 48} y {2 , 6, 18, 54, 162} respectivamente. Por lo tanto, el recuento total de enteros distintos en el GP es 9.
Enfoque: El problema dado se puede resolver mediante la observación de que el recuento total de enteros distintos se puede calcular generando los primeros N términos de ambas Progresiones geométricas y eliminando los términos duplicados. Esto se puede lograr mediante el uso de la estructura de datos establecida . En primer lugar, genere todos los N términos del 1er GP e inserte los términos en un conjunto S. De manera similar, inserte los términos del 2do GP en el conjunto S. El tamaño del conjunto S es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
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>
9
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA