Generación de n números con un conjunto dado de factores

Dada una array de k números factor[] , la tarea es imprimir los primeros n números (en orden ascendente) cuyos factores son de la array dada.

Ejemplos: 

Input  : factor[] = {2, 3, 4, 7} 
         n = 8
Output : 2 3 4 6 7 8 9 10

Input  :  factor[] = {3, 5, 7}
          n = 10
Output :  3 5 6 7 9 10 12 14 15 18

Este problema es principalmente una extensión del problema del número feo . Creamos una array auxiliar next[] del mismo tamaño que factor[] para realizar un seguimiento de los próximos múltiplos de factores. En cada iteración, sacamos el elemento mínimo del siguiente, luego lo incrementamos por el factor respectivo. Si el valor mínimo es igual al valor de salida anterior, increméntelo (para evitar duplicados). De lo contrario imprimimos el valor mínimo.

// C++ program to generate n numbers with
// given factors
#include<bits/stdc++.h>
using namespace std;
 
// Generate n numbers with factors in factor[]
void generateNumbers(int factor[], int n, int k)
{
    // array of k to store next multiples of
    // given factors
    int next[k] = {0};
 
    // Prints n numbers 
    int output = 0;  // Next number to print as output
    for (int i=0; i<n; )
    {
        // Find the next smallest multiple
        int toincrement = 0;
        for (int j=0; j<k; j++)
            if (next[j] < next[toincrement])
                toincrement = j;
 
        // Printing minimum in each iteration
        // print the value if output is not equal to
        // current value(to avoid the duplicates)
        if (output != next[toincrement])
        {
            output = next[toincrement];
            printf("%d ",  next[toincrement]);
            i++;
        }
 
        // incrementing the current value by the
        // respective factor
        next[toincrement] += factor[toincrement];
    }
}
 
// Driver code
int main()
{
    int factor[] = {3, 5, 7};
    int n = 10;
    int k = sizeof(factor)/sizeof(factor[0]);
    generateNumbers(factor, n, k);
    return 0;
}

// Java program to generate
// n numbers with given factors
import java.io.*;
 
class GFG
{
     
// Generate n numbers with
// factors in factor[]
static void generateNumbers(int factor[],
                            int n, int k)
{
    // array of k to store
    // next multiples of
    // given factors
    int next[] = new int[k];
 
    // Prints n numbers
    int output = 0; // Next number to
                    // print as output
    for (int i = 0; i < n;)
    {
        // Find the next
        // smallest multiple
        int toincrement = 0;
        for (int j = 0; j < k; j++)
            if (next[j] < next[toincrement])
                toincrement = j;
 
        // Printing minimum in
        // each iteration print
        // the value if output
        // is not equal to current
        // value(to avoid the
        // duplicates)
        if (output != next[toincrement])
        {
            output = next[toincrement];
            System.out.print(
                   next[toincrement] + " ");
            i++;
        }
 
        // incrementing the
        // current value by the
        // respective factor
        next[toincrement] +=
               factor[toincrement];
    }
}
 
// Driver code
public static void main (String[] args)
{
    int factor[] = {3, 5, 7};
    int n = 10;
    int k = factor.length;
    generateNumbers(factor, n, k);
}
}
 
// This code is contributed
// by ajit

# Python3 program to generate n
# numbers with given factors
 
# Generate n numbers with
# factors in factor[]
def generateNumbers(factor, n, k):
     
    # array of k to store next
    # multiples of given factors
    next = [0] * k;
 
    # Prints n numbers
    output = 0; # Next number to
                # print as output
    i = 0;
    while(i < n):
         
        # Find the next smallest
        # multiple
        toincrement = 0;
        for j in range(k):
            if(next[j] < next[toincrement]):
                toincrement = j;
 
        # Printing minimum in each
        # iteration print the value
        # if output is not equal to
        # current value(to avoid the
        # duplicates)
        if(output != next[toincrement]):
            output = next[toincrement];
            print(next[toincrement], end = " ");
            i += 1;
 
        # incrementing the current
        # value by the respective factor
        next[toincrement] += factor[toincrement];
 
# Driver code
factor = [3, 5, 7];
n = 10;
k = len(factor);
generateNumbers(factor, n, k);
     
# This code is contributed by mits

// C# program to generate
// n numbers with given factors
using System;
 
class GFG
{
     
// Generate n numbers with
// factors in factor[]
static void generateNumbers(int []factor,
                            int n, int k)
{
    // array of k to store
    // next multiples of
    // given factors
    int []next = new int[k];
 
    // Prints n numbers
    int output = 0; // Next number to
                    // print as output
    for (int i = 0; i < n;)
    {
        // Find the next
        // smallest multiple
        int toincrement = 0;
        for (int j = 0; j < k; j++)
            if (next[j] < next[toincrement])
                toincrement = j;
 
        // Printing minimum in
        // each iteration print
        // the value if output
        // is not equal to current
        // value(to avoid the
        // duplicates)
        if (output != next[toincrement])
        {
            output = next[toincrement];
            Console.Write(
                next[toincrement] + " ");
            i++;
        }
 
        // incrementing the
        // current value by the
        // respective factor
        next[toincrement] +=
            factor[toincrement];
    }
}
 
// Driver code
static public void Main ()
{
    int []factor = {3, 5, 7};
    int n = 10;
    int k = factor.Length;
    generateNumbers(factor, n, k);
}
}
 
// This code is contributed
// by akt_mit

<?php
// PHP program to generate n numbers
// with given factors
 
// Generate n numbers with factors
// in factor[]
function generateNumbers($factor, $n, $k)
{
    // array of k to store next
    // multiples of given factors
    $next = array_fill(0, $k, 0);
 
    // Prints n numbers
    $output = 0; // Next number to print
                 // as output
    for ($i = 0; $i < $n; )
    {
        // Find the next smallest multiple
        $toincrement = 0;
        for ($j = 0; $j < $k; $j++)
            if ($next[$j] < $next[$toincrement])
                $toincrement = $j;
 
        // Printing minimum in each iteration
        // print the value if output is not
        // equal to current value(to avoid
        // the duplicates)
        if ($output != $next[$toincrement])
        {
            $output = $next[$toincrement];
            echo $next[$toincrement] . " ";
            $i++;
        }
 
        // incrementing the current value
        // by the respective factor
        $next[$toincrement] += $factor[$toincrement];
    }
}
 
// Driver code
$factor = array(3, 5, 7);
$n = 10;
$k = count($factor);
generateNumbers($factor, $n, $k);
 
// This code is contributed by mits
?>

<script>
 
// Javascript program to generate
// n numbers with given factors
 
// Generate n numbers with
// factors in factor[]
function generateNumbers(factor, n, k)
{
     
    // Array of k to store
    // next multiples of
    // given factors
    let next = new Array(k);
    next.fill(0);
 
    // Prints n numbers
    let output = 0; // Next number to
                    // print as output
                     
    for(let i = 0; i < n;)
    {
         
        // Find the next
        // smallest multiple
        let toincrement = 0;
        for(let j = 0; j < k; j++)
            if (next[j] < next[toincrement])
                toincrement = j;
 
        // Printing minimum in
        // each iteration print
        // the value if output
        // is not equal to current
        // value(to avoid the
        // duplicates)
        if (output != next[toincrement])
        {
            output = next[toincrement];
            document.write(next[toincrement] + " ");
            i++;
        }
 
        // Incrementing the
        // current value by the
        // respective factor
        next[toincrement] += factor[toincrement];
    }
}
 
// Driver code
let factor = [ 3, 5, 7 ];
let n = 10;
let k = factor.length;
 
generateNumbers(factor, n, k);
 
// This code is contributed by divyesh072019
 
</script>

Producción : 

3 5 6 7 9 10 12 14 15 18 

Complejidad del tiempo – O(n * k) 
Espacio auxiliar – O(k)

Este artículo es una contribución de Niteesh kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.