Dado un entero K y una array arr[] de N enteros, cada uno de los cuales es el primer término y la diferencia común de una Progresión aritmética , la tarea es encontrar el K -ésimo elemento del conjunto S formado al fusionar las N progresiones aritméticas.
Ejemplos:
Entrada: arr[] = {2, 3}, K = 10
Salida: 15
Explicación:
Hay 2 progresiones aritméticas.
Primer término y diferencia común del primer AP es 2. Por lo tanto AP1 = {2, 4, 6, …}
Primer término y diferencia común del segundo AP es 3. Por lo tanto AP2 = {3, 6, 9, … }
El conjunto S contiene AP1 y AP2, es decir, { 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20…… }.
Por lo tanto, el décimo término es: 15Entrada: arr[] = {2, 3, 5, 7, 11}, K = 8
Salida: 9
Explicación:
Hay 5 progresiones aritméticas.
Primer término y diferencia común del primer AP es 2. Por lo tanto AP1 = {2, 4, 6, …}
Primer término y diferencia común del segundo AP es 3. Por lo tanto AP2 = {3, 6, 9, … }
Primer término y diferencia común del tercer AP es 5. Por lo tanto AP3 = {5, 10, 15, …}
Primer término y diferencia común del cuarto AP es 7. Por lo tanto AP4 = {7, 14, 21, …}
Primer término y la diferencia común del quinto AP es 11. Por lo tanto AP5 = {11, 22, 33, …}
Así el conjunto S contiene { 2, 3, 4, 5, 6, 7, 8, 9, 10 , …. }.
Por lo tanto, el octavo término es: 9
Enfoque:
siga los pasos a continuación para resolver el problema:
- Considere un rango de [1, maxm] y calcule la mitad de ese rango.
- Compruebe si se pueden obtener elementos K fusionando la serie N. Si el número de términos excede K , reduzca R a la mitad . De lo contrario, actualice L a mid . Ahora, continúe hasta que encontremos un medio para el cual se puedan obtener exactamente K términos en la serie.
- Para encontrar cuántos elementos ocurrirán antes de cualquier valor en particular, debemos aplicar el principio de inclusión y exclusión para obtener la unión de todos los AP.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find k-th term of
// N merged Arithmetic Progressions
#include <bits/stdc++.h>
using namespace std;
#define maxm 1000000000
// Function to count and return the
// number of values less than equal
// to N present in the set
int count(vector<int> v, int n)
{
int i, odd = 0, even = 0;
int j, d, count;
int t = (int)1 << v.size();
int size = v.size();
for (i = 1; i < t; i++) {
d = 1, count = 0;
for (j = 0; j < size; j++) {
// Check whether j-th bit
// is set bit or not
if (i & (1 << j)) {
d *= v[j];
count++;
}
}
if (count & 1)
odd += n / d;
else
even += n / d;
}
return (odd - even);
}
// Function to implement Binary
// Search to find K-th element
int BinarySearch(int l, int r,
vector<int> v,
int key)
{
int mid;
while (r - l > 1) {
// Find middle index of
// the array
mid = (l + r) / 2;
// Search in the left half
if (key <= count(v, mid)) {
r = mid;
}
// Search in the right half
else {
l = mid;
}
}
// If exactly K elements
// are present
if (key == count(v, l))
return l;
else
return r;
}
// Driver Code
int main()
{
int N = 2, K = 10;
vector<int> v = { 2, 3 };
cout << BinarySearch(1, maxm, v, K)
<< endl;
return 0;
}
Java
// Java program to find k-th term of
// N merged Arithmetic Progressions
import java.util.*;
class GFG{
static final int maxm = 1000000000;
// Function to count and return the
// number of values less than equal
// to N present in the set
static int count(int []v, int n)
{
int i, odd = 0, even = 0;
int j, d, count;
int t = (int)1 << v.length;
int size = v.length;
for (i = 1; i < t; i++)
{
d = 1;
count = 0;
for (j = 0; j < size; j++)
{
// Check whether j-th bit
// is set bit or not
if ((i & (1 << j)) > 0)
{
d *= v[j];
count++;
}
}
if (count % 2 == 1)
odd += n / d;
else
even += n / d;
}
return (odd - even);
}
// Function to implement Binary
// Search to find K-th element
static int BinarySearch(int l, int r,
int []v,
int key)
{
int mid;
while (r - l > 1)
{
// Find middle index of
// the array
mid = (l + r) / 2;
// Search in the left half
if (key <= count(v, mid))
{
r = mid;
}
// Search in the right half
else
{
l = mid;
}
}
// If exactly K elements
// are present
if (key == count(v, l))
return l;
else
return r;
}
// Driver Code
public static void main(String[] args)
{
int N = 2, K = 10;
int []v = { 2, 3 };
System.out.print(BinarySearch(1, maxm, v, K) + "\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find k-th term of # N merged Arithmetic Progressions maxm = 1000000000 # Function to count and return the # number of values less than equal # to N present in the set def count(v, n): odd, even = 0, 0 t = 1 << len(v) size = len(v) for i in range(1, t): d, count = 1, 0 for j in range(0, size): # Check whether j-th bit # is set bit or not if (i & (1 << j)): d *= v[j] count += 1 if (count & 1): odd += n // d else: even += n // d return (odd - even) # Function to implement Binary # Search to find K-th element def BinarySearch(l, r, v, key): while (r - l > 1): # Find middle index of # the array mid = (l + r) // 2 # Search in the left half if (key <= count(v, mid)): r = mid # Search in the right half else: l = mid # If exactly K elements # are present if (key == count(v, l)): return l else: return r # Driver Code N, K = 2, 10 v = [ 2, 3 ] print(BinarySearch(1, maxm, v, K)) # This code is contributed by divyeshrabadiya07
C#
// C# program to find k-th term of
// N merged Arithmetic Progressions
using System;
class GFG{
static readonly int maxm = 1000000000;
// Function to count and return the
// number of values less than equal
// to N present in the set
static int count(int []v, int n)
{
int i, odd = 0, even = 0;
int j, d, count;
int t = (int)1 << v.Length;
int size = v.Length;
for(i = 1; i < t; i++)
{
d = 1;
count = 0;
for(j = 0; j < size; j++)
{
// Check whether j-th bit
// is set bit or not
if ((i & (1 << j)) > 0)
{
d *= v[j];
count++;
}
}
if (count % 2 == 1)
odd += n / d;
else
even += n / d;
}
return (odd - even);
}
// Function to implement Binary
// Search to find K-th element
static int BinarySearch(int l, int r,
int []v, int key)
{
int mid;
while (r - l > 1)
{
// Find middle index of
// the array
mid = (l + r) / 2;
// Search in the left half
if (key <= count(v, mid))
{
r = mid;
}
// Search in the right half
else
{
l = mid;
}
}
// If exactly K elements
// are present
if (key == count(v, l))
return l;
else
return r;
}
// Driver Code
public static void Main(String[] args)
{
//int N = 2;
int K = 10;
int []v = { 2, 3 };
Console.Write(BinarySearch(
1, maxm, v, K) + "\n");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to find k-th term of
// N merged Arithmetic Progressions
let maxm = 1000000000;
// Function to count and return the
// number of values less than equal
// to N present in the set
function count(v, n)
{
let i, odd = 0, even = 0;
let j, d, count;
let t = 1 << v.length;
let size = v.length;
for (i = 1; i < t; i++)
{
d = 1;
count = 0;
for (j = 0; j < size; j++)
{
// Check whether j-th bit
// is set bit or not
if ((i & (1 << j)) > 0)
{
d *= v[j];
count++;
}
}
if (count % 2 == 1)
odd += n / d;
else
even += n / d;
}
return (odd - even);
}
// Function to implement Binary
// Search to find K-th element
function BinarySearch(l, r,
v, key)
{
let mid;
while (r - l > 1)
{
// Find middle index of
// the array
mid = Math.floor((l + r) / 2);
// Search in the left half
if (key <= count(v, mid))
{
r = mid;
}
// Search in the right half
else
{
l = mid;
}
}
// If exactly K elements
// are present
if (key == count(v, l))
return l;
else
return r;
}
// Driver Code
let N = 2, K = 10;
let v = [ 2, 3 ];
document.write(BinarySearch(1, maxm, v, K) + "\n");
</script>
15
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por KrishnaHare y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA