N-е кратное в отсортированном списке кратных двух чисел

Опубликовано: 20 Января, 2022

Даны три натуральных числа a, b и n . Рассмотрим список, в котором все кратные «a» и «b». список сортируется, удаляются дубликаты. Задача - найти n-й элемент списка.
Примеры :

 Ввод: a = 3, b = 5, n = 5.
Выход: 10
a = 3 b = 5, кратное 3 равняется 3, 6, 9, 12, 15, ... и 
кратные 5 равны 5, 10, 15, 20, .... 
После удаления повторяющегося элемента и сортировки:
3, 5, 6, 9, 10, 12, 15, 18, 20, .... 
Пятый элемент в последовательности - 10.

Ввод: n = 6, a = 2, b = 3 
Выход: 9

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Method 1: (Brute Force) 
Generate the first ‘n’ multiple of ‘a’. Now, generate first ‘n’ multiple of b such that it do not belong to the first n multiple of ‘a’. This can be done using Binary Search. 
 

C++

// C++ program to find n-th number in the sorted
// list of multiples of two numbers.
#include<bits/stdc++.h>
using namespace std;
 
// Return the n-th number in the sorted
// list of multiples of two numbers.
int nthElement(int a, int b, int n)
{
    vector<int> seq;
 
    // Generating first n multiple of a.
    for (int i = 1; i <= n; i++)
        seq.push_back(a*i);
 
    // Sorting the sequence.
    sort(seq.begin(), seq.end());
 
    // Generating and storing first n multiple of b
    // and storing if not present in the sequence.
    for (int i = 1, k = n; i <= n && k; i++)
    {
        // If not present in the sequence
        if (!binary_search(seq.begin(), seq.end(), b*i))
        {
            // Storing in the sequence.
            seq.push_back(b*i);
 
            sort(seq.begin(), seq.end());
            k--;
        }
    }
 
    return seq[n - 1];
}
 
// Driven Program
int main()
{
    int a = 3, b = 5, n = 5;
    cout << nthElement(a, b, n) << endl;
    return 0;
}

Java

// Java program to find n-th number
// in the sorted list of multiples
// of two numbers.
import java.io.*;
import java.util.*;
class GFG
{
// Return the n-th number in the sorted
// list of multiples of two numbers.
static int nthElement(int a, int b, int n)
{
    ArrayList<Integer> seq = new
              ArrayList<Integer>(n * n + 1);
     
    // Generating first n multiple of a.
    for (int i = 1; i <= n; i++)
        seq.add(a * i);
         
    // Sorting the sequence.
    Collections.sort(seq);
     
    // Generating and storing first n
    // multiple of b and storing if
    // not present in the sequence.
    for (int i = 1, k = n;
             i <= n && k > 0; i++)
    {
        // If not present in the sequence
        if (seq.indexOf(b * i) == -1)
        {
            // Storing in the sequence.
            seq.add(b * i);
            Collections.sort(seq);
            k--;
        }
    }
    return seq.get(n - 1);
}
 
// Driver Code
public static void main(String[] args)
{
    int a = 3, b = 5, n = 5;
    System.out.println(nthElement(a, b, n));
}
}
 
// This code is contributed by mits

Python3

# Python3 program to find n-th
# number in the sorted list of
# multiples of two numbers.
 
# Return the n-th number in the
# sorted list of multiples of
# two numbers.
def nthElement(a, b, n):
    seq = [];
 
    # Generating first n
    # multiple of a.
    for i in range(1, n + 1):
        seq.append(a * i);
 
    # Sorting the sequence.
    seq.sort();
 
    # Generating and storing first
    # n multiple of b and storing
    # if not present in the sequence.
    i = 1;
    k = n;
    while(i <= n and k > 0):
         
        # If not present in the sequence
        try:
            z = seq.index(b * i);
        except ValueError:
             
            # Storing in the sequence.
            seq.append(b * i);
            seq.sort();
            k -= 1;
        i += 1;
 
    return seq[n - 1];
 
# Driver Code
a = 3;
b = 5;
n = 5;
print(nthElement(a, b, n));
 
# This code is contributed by mits

C#

// C# program to find n-th number
// in the sorted list of multiples
// of two numbers.
using System;
using System.Collections;
 
class GFG
{
// Return the n-th number in the sorted
// list of multiples of two numbers.
static int nthElement(int a,
                      int b, int n)
{
    ArrayList seq = new ArrayList();
     
    // Generating first n multiple of a.
    for (int i = 1; i <= n; i++)
        seq.Add(a * i);
 
    // Sorting the sequence.
    seq.Sort();
 
    // Generating and storing first n
    // multiple of b and storing if
    // not present in the sequence.
    for (int i = 1, k = n;
             i <= n && k > 0; i++)
    {
        // If not present in the sequence
        if (!seq.Contains(b * i))
        {
            // Storing in the sequence.
            seq.Add(b * i);
            seq.Sort();
            k--;
        }
    }
 
    return (int)seq[n - 1];
}
 
// Driver Code
static void Main()
{
    int a = 3, b = 5, n = 5;
    Console.WriteLine(nthElement(a, b, n));
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP program to find n-th number
// in the sorted list of multiples
// of two numbers.
 
// Return the n-th number in the sorted
// list of multiples of two numbers.
function nthElement($a, $b, $n)
{
    $seq = array();
 
    // Generating first n multiple of a.
    for ($i = 1; $i <= $n; $i++)
        array_push($seq, $a * $i);
 
    // Sorting the sequence.
    sort($seq);
 
    // Generating and storing first
    // n multiple of b and storing
    // if not present in the sequence.
    for ($i = 1, $k = $n;
         $i <= $n && $k > 0; $i++)
    {
        // If not present in the sequence
        if (array_search($b * $i, $seq) == 0)
        {
            // Storing in the sequence.
            array_push($seq, $b * $i);
  
            sort($seq);
            $k--;
        }
    }
 
    return $seq[$n - 1];
}
 
// Driver Code
$a = 3;
$b = 5;
$n = 5;
echo nthElement($a, $b, $n);
 
// This code is contributed by mits
?>

Выход:

 10

Метод 2: (Эффективный подход)
Идея состоит в том, чтобы использовать тот факт, что общее кратное для a и b удаляется с помощью LCM (a, b). Пусть f (a, b, x) будет функцией, которая вычисляет количество чисел, которые меньше x и кратны a и b. Теперь, используя принцип включения-исключения, мы можем сказать:

f(a, b, x) :  Count of number that are less than x
              and multiples of a and b

f(a, b, x) = (x/a) + (x/b) - (x/lcm(a, b))
where (x/a) define number of multiples of a
(x/b) define number of multiple of b
(x/lcm(a, b)) define the number of common multiples 
of a and b.

Observe, a and b are constant. As x increases, f(a, b, x) will also increase. Therefore we can apply Binary Search to find the minimum value of x such that f(a, b, x) >= n. The lower bound of the function is the required answer.
The upper bound for n-th term would be min(a, b)*n. Note that we get the largest value n-th term when there are no common elements in multiples of a and b.
Below are the implementations of above approach: 
 

C++

// C++ program to find n-th number in thes
// sorted list of multiples of two numbers.
#include<bits/stdc++.h>
using namespace std;
 
// Return the Nth number in the sorted
// list of multiples of two numbers.
int nthElement(int a, int b, int n)
{
    // Finding LCM of a and b.
    int lcm = (a * b)/__gcd(a,b);
 
    // Binary Search.
    int l = 1, r = min(a, b)*n;
    while (l <= r)
    {
        // Finding the middle element.
        int mid = (l + r)>>1;
 
        // count of number that are less than
        // mid and multiples of a and b
        int val = mid/a + mid/b - mid/lcm;
 
        if (val == n)
            return max((mid/a)*a, (mid/b)*b);
 
        if (val < n)
            l = mid + 1;
        else
            r = mid - 1;
    }
}
 
// Driven Program
int main()
{
    int a = 5, b = 3, n = 5;
    cout << nthElement(a, b, n) << endl;
    return 0;
}

Java

// Java program to find n-th number in the
// sorted list of multiples of two numbers.
import java.io.*;
 
public class GFG{
     
// Recursive function to return
// gcd of a and b
static int __gcd(int a, int b)
{
    // Everything divides 0
    if (a == 0 || b == 0)
    return 0;
 
    // base case
    if (a == b)
        return a;
     
    // a is greater
    if (a > b)
        return __gcd(a - b, b);
        return __gcd(a, b - a);
}
 
// Return the Nth number in the sorted
// list of multiples of two numbers.
static int nthElement(int a, int b, int n)
{
    // Finding LCM of a and b.
    int lcm = (a * b) / __gcd(a, b);
 
    // Binary Search.
    int l = 1, r = Math.min(a, b) * n;
    while (l <= r)
    {
        // Finding the middle element.
        int mid = (l + r) >> 1;
 
        // count of number that are less than
        // mid and multiples of a and b
        int val = mid / a + mid / b -
                  mid / lcm;
 
        if (val == n)
            return Math.max((mid / a) * a,
                            (mid / b) * b);
 
        if (val < n)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return 0;
}
 
// Driver Code
static public void main (String[] args)
{
    int a = 5, b = 3, n = 5;
    System.out.println(nthElement(a, b, n));
}
}
 
// This code is contributed by vt_m.

Python 3

# Python 3 program to find n-th number
# in thes sorted list of multiples of
# two numbers.
import math
 
# Return the Nth number in the sorted
# list of multiples of two numbers.
def nthElement(a, b, n):
 
    # Finding LCM of a and b.
    lcm = (a * b) / int(math.gcd(a, b))
 
    # Binary Search.
    l = 1
    r = min(a, b) * n
    while (l <= r):
     
        # Finding the middle element.
        mid = (l + r) >> 1
 
        # count of number that are less
        # than mid and multiples of a
        # and b
        val = (int(mid / a) + int(mid / b)
                         - int(mid / lcm))
 
        if (val == n):
            return int( max(int(mid / a) * a,
                          int(mid / b) * b) )
 
        if (val < n):
            l = mid + 1
        else:
            r = mid - 1
     
# Driven Program
a = 5
b = 3
n = 5
print(nthElement(a, b, n))
 
# This code is contributed by Smitha.

C#

// C# program to find n-th number in thes
// sorted list of multiples of two numbers.
using System;
 
public class GFG{
     
// Recursive function to return
// gcd of a and b
static int __gcd(int a, int b)
{
    // Everything divides 0
    if (a == 0 || b == 0)
    return 0;
 
    // ba

РЕКОМЕНДУЕМЫЕ СТАТЬИ