Dados cuatro enteros a , b , c y N . La tarea es encontrar el N -ésimo término que sea divisible por a , b o c .
Ejemplos:
Entrada: a = 2, b = 3, c = 5, N = 10
Salida: 14
La secuencia es 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16…
Entrada: a = 3, b = 5, c = 7, N = 10
Salida: 18
Enfoque ingenuo: un enfoque simple es atravesar todos los términos comenzando desde 1 hasta que encontremos el N -ésimo término deseado que es divisible por a , b o c . Esta solución tiene una complejidad temporal de O(N).
Enfoque eficiente: la idea es utilizar la búsqueda binaria . Aquí podemos calcular cuántos números del 1 al num son divisibles por a , b o c usando la fórmula: (num / a) + (num / b) + (num / c) – (num / lcm(a, b)) – (núm / mcm(b, c)) – (núm / mcm(a, c)) + (núm / mcm(a, b, c))
La fórmula anterior se deriva utilizando la teoría de conjuntos
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return
// gcd of a and b
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return the lcm of a and b
int lcm(int a, int b)
{
return (a * b) / gcd(a, b);
}
// Function to return the count of numbers
// from 1 to num which are divisible by a, b or c
int divTermCount(int a, int b, int c, int num)
{
// Calculate number of terms divisible by a and
// by b and by c then, remove the terms which is are
// divisible by both a and b, both b and c, both
// c and a and then add which are divisible by a and
// b and c
return ((num / a) + (num / b) + (num / c)
- (num / lcm(a, b))
- (num / lcm(b, c))
- (num / lcm(a, c))
+ (num / lcm(a, lcm(b, c))));
}
// Function to find the nth term
// divisible by a, b or c
// by using binary search
int findNthTerm(int a, int b, int c, int n)
{
// Set low to 1 and high to max (a, b, c) * n
int low = 1, high = INT_MAX, mid;
while (low < high) {
mid = low + (high - low) / 2;
// If the current term is less than
// n then we need to increase low
// to mid + 1
if (divTermCount(a, b, c, mid) < n)
low = mid + 1;
// If current term is greater than equal to
// n then high = mid
else
high = mid;
}
return low;
}
// Driver code
int main()
{
int a = 2, b = 3, c = 5, n = 10;
cout << findNthTerm(a, b, c, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return
// gcd of a and b
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return the lcm of a and b
static int lcm(int a, int b)
{
return (a * b) / gcd(a, b);
}
// Function to return the count of numbers
// from 1 to num which are divisible by a, b or c
static int divTermCount(int a, int b, int c, int num)
{
// Calculate number of terms divisible by a and
// by b and by c then, remove the terms which is are
// divisible by both a and b, both b and c, both
// c and a and then add which are divisible by a and
// b and c
return ((num / a) + (num / b) + (num / c)
- (num / lcm(a, b))
- (num / lcm(b, c))
- (num / lcm(a, c))
+ (num / lcm(a, lcm(b, c))));
}
// Function to find the nth term
// divisible by a, b or c
// by using binary search
static int findNthTerm(int a, int b, int c, int n)
{
// Set low to 1 and high to max (a, b, c) * n
int low = 1, high = Integer.MAX_VALUE, mid;
while (low < high) {
mid = low + (high - low) / 2;
// If the current term is less than
// n then we need to increase low
// to mid + 1
if (divTermCount(a, b, c, mid) < n)
low = mid + 1;
// If current term is greater than equal to
// n then high = mid
else
high = mid;
}
return low;
}
// Driver code
public static void main(String[] args)
{
int a = 2, b = 3, c = 5, n = 10;
System.out.println(findNthTerm(a, b, c, n));
}
}
// This code is contributed by
// Rajnis09
Python
# Python3 implementation of the approach # Function to return # gcd of a and b def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # Function to return the lcm of a and b def lcm(a, b): return ((a * b) // gcd(a, b)) # Function to return the count of numbers # from 1 to num which are divisible by a, b or c def divTermCount(a, b, c, num): # Calculate number of terms divisible by a and # by b and by c then, remove the terms which is are # divisible by both a and b, both b and c, both # c and a and then add which are divisible by a and # b and c return ((num // a) + (num // b) + (num // c) - (num // lcm(a, b)) - (num // lcm(b, c)) - (num // lcm(a, c)) + (num // lcm(a, lcm(b, c)))) # Function to find the nth term # divisible by a, b or c # by using binary search def findNthTerm(a, b, c, n): # Set low to 1 and high to max (a, b, c) * n low = 1 high = 10**9 mid=0 while (low < high): mid = low + (high - low) // 2 # If the current term is less than # n then we need to increase low # to mid + 1 if (divTermCount(a, b, c, mid) < n): low = mid + 1 # If current term is greater than equal to # n then high = mid else: high = mid return low # Driver code a = 2 b = 3 c = 5 n = 10 print(findNthTerm(a, b, c, n)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return
// gcd of a and b
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return the lcm of a and b
static int lcm(int a, int b)
{
return (a * b) / gcd(a, b);
}
// Function to return the count of numbers
// from 1 to num which are divisible by a, b or c
static int divTermCount(int a, int b, int c, int num)
{
// Calculate number of terms divisible by a and
// by b and by c then, remove the terms which is are
// divisible by both a and b, both b and c, both
// c and a and then add which are divisible by a and
// b and c
return ((num / a) + (num / b) + (num / c)
- (num / lcm(a, b))
- (num / lcm(b, c))
- (num / lcm(a, c))
+ (num / lcm(a, lcm(b, c))));
}
// Function to find the nth term
// divisible by a, b or c
// by using binary search
static int findNthTerm(int a, int b, int c, int n)
{
// Set low to 1 and high to max (a, b, c) * n
int low = 1, high = int.MaxValue, mid;
while (low < high) {
mid = low + (high - low) / 2;
// If the current term is less than
// n then we need to increase low
// to mid + 1
if (divTermCount(a, b, c, mid) < n)
low = mid + 1;
// If current term is greater than equal to
// n then high = mid
else
high = mid;
}
return low;
}
// Driver code
public static void Main(String[] args)
{
int a = 2, b = 3, c = 5, n = 10;
Console.WriteLine(findNthTerm(a, b, c, n));
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of the approach
// Function to return
// gcd of a and b
function gcd(a, b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return the lcm of a and b
function lcm(a, b)
{
return parseInt((a * b) / gcd(a, b));
}
// Function to return the count of numbers
// from 1 to num which are divisible by a, b or c
function divTermCount(a, b, c, num)
{
// Calculate number of terms divisible by a and
// by b and by c then, remove the terms which is are
// divisible by both a and b, both b and c, both
// c and a and then add which are divisible by a and
// b and c
return (parseInt(num / a) + parseInt(num / b) +
parseInt(num / c)
- parseInt(num / lcm(a, b))
- parseInt(num / lcm(b, c))
- parseInt(num / lcm(a, c))
+ parseInt(num / lcm(a, lcm(b, c))));
}
// Function to find the nth term
// divisible by a, b or c
// by using binary search
function findNthTerm(a, b, c, n)
{
// Set low to 1 and high to max (a, b, c) * n
let low = 1, high = Number.MAX_VALUE, mid;
while (low < high) {
mid = low + parseInt((high - low) / 2);
// If the current term is less than
// n then we need to increase low
// to mid + 1
if (divTermCount(a, b, c, mid) < n)
low = mid + 1;
// If current term is greater than equal to
// n then high = mid
else
high = mid;
}
return low;
}
// Driver code
let a = 2, b = 3, c = 5, n = 10;
document.write(findNthTerm(a, b, c, n));
</script>
Producción:
14
Complejidad de tiempo: O(log n * log(min(a, b))), donde a y b son dos parámetros para GCD.
Espacio auxiliar: O(log(min(a, b)))
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA