Todos los valores posibles de piso (N/K) para todos los valores de K

Dada una función f(K) = piso(N/K) ( N>0 y K>0 ), la tarea es encontrar todos los valores posibles de f(K) para un N dado donde K toma todos los valores en el rango [ 1, Inf.] .
Ejemplos: 
 

Entrada: N = 5 
Salida: 0 1 2 5 
Explicación: 
5 divide 1 = 5 
5 divide 2 = 2 
5 divide 3 = 1 
5 divide 4 = 1 
5 divide 5 = 1 
5 divide 6 = 0 
5 divide 7 = 0 
Así que todo posibles valores distintos de f(k) son {0, 1, 2, 5}.
Entrada: N = 11 
Salida: 0 1 2 3 5 11 
Explicación: 
11 dividir 1 = 11 
11 dividir 2 = 5 
11 dividir 3 = 3 
11 dividir 4 = 2 
11 dividir 5 = 2 
11 dividir 6 = 1 
11 dividir 7 = 1 
… 
… 
11 dividido 11 = 1 11 dividido 
12 = 0 
Así que todos los posibles valores distintos de f(k) son {0, 1, 2, 3, 5, 11}. 
 

Enfoque ingenuo: 
el enfoque más simple para iterar sobre [1, N+1] y almacenar en un conjunto , todos los valores de (N/i) (1 ? i ? N + 1) para evitar la duplicación. 
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 print all
// possible values of
// floor(N/K)
void allQuotients(int N)
{
    set<int> s;
 
    // loop from 1 to N+1
    for (int k = 1; k <= N + 1; k++) {
        s.insert(N / k);
    }
 
    for (auto it : s)
        cout << it << " ";
}
 
int main()
{
    int N = 5;
    allQuotients(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to print all
// possible values of
// Math.floor(N/K)
static void allQuotients(int N)
{
    HashSet<Integer> s = new HashSet<Integer>();
 
    // loop from 1 to N+1
    for(int k = 1; k <= N + 1; k++)
    {
        s.add(N / k);
    }
     
    for(int it : s)
        System.out.print(it + " ");
}
 
// Driver code
public static void main(String[] args)
{
    int N = 5;
     
    allQuotients(N);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach
 
# Function to print all possible
# values of floor(N/K)
def allQuotients(N):
 
    s = set()
 
    # Iterate from 1 to N+1
    for k in range(1, N + 2):
        s.add(N // k)
 
    for it in s:
        print(it, end = ' ')
 
# Driver code
if __name__ == '__main__':
 
    N = 5
     
    allQuotients(N)
 
# This code is contributed by himanshu77

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to print all possible
// values of Math.floor(N/K)
static void allQuotients(int N)
{
    SortedSet<int> s = new SortedSet<int>();
     
    // Loop from 1 to N+1
    for(int k = 1; k <= N + 1; k++)
    {
        s.Add(N / k);
    }
     
    foreach(int it in s)
    {
        Console.Write(it + " ");
    }
}
 
// Driver code
static void Main()
{
    int N = 5;
     
    allQuotients(N);
}
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
// Javascript Program for the
// above approach
 
// Function to print all
// possible values of
// floor(N/K)
function allQuotients(N)
{
    var s = new Set();
 
    // loop from 1 to N+1
    for (var k = 1; k <= N + 1; k++) {
        s.add(parseInt(N / k));
    }
     
    var ls = Array.from(s).reverse();
    ls.forEach(v => document.write(v+ " "))
}
 
var N = 5;
allQuotients(N);
 
 
</script>
Producción: 

0 1 2 5

 

Complejidad de tiempo: O (nlogn)

Espacio auxiliar: O(n)
Enfoque eficiente: 
una solución optimizada es iterar sobre [1, ?N] e insertar valores K y (N/K) en el conjunto.
 

C++

// C++ Program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print all
// possible values of
// floor(N/K)
void allQuotients(int N)
{
    set<int> s;
    s.insert(0);
 
    for (int k = 1; k <= sqrt(N); k++) {
        s.insert(k);
        s.insert(N / k);
    }
 
    for (auto it : s)
        cout << it << " ";
}
 
int main()
{
    int N = 5;
    allQuotients(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to print all
// possible values of
// Math.floor(N/K)
static void allQuotients(int N)
{
    HashSet<Integer> s = new HashSet<Integer>();
    s.add(0);
     
    // loop from 1 to N+1
    for(int k = 1; k <= Math.sqrt(N); k++)
    {
        s.add(k);
        s.add(N / k);
    }
     
    for(int it : s)
        System.out.print(it + " ");
}
 
// Driver code
public static void main(String[] args)
{
    int N = 5;
     
    allQuotients(N);
}
}
 
// This code is contributed by rock_cool

Python3

# Python3 program for the above approach
from math import *
 
# Function to print all possible
# values of floor(N/K)
def allQuotients(N):
 
    s = set()
    s.add(0)
 
    for k in range(1, int(sqrt(N)) + 1):
        s.add(k)
        s.add(N // k)
 
    for it in s:
        print(it, end = ' ')
 
# Driver code
if __name__ == '__main__':
 
    N = 5
     
    allQuotients(N)
 
# This code is contributed by himanshu77

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to print all possible
// values of Math.floor(N/K)
static void allQuotients(int N)
{
    SortedSet<int> s = new SortedSet<int>();
    s.Add(0);
     
    // loop from 1 to N+1
    for(int k = 1; k <= Math.Sqrt(N); k++)
    {
        s.Add(k);
        s.Add(N / k);
    }
     
    foreach(int it in s)
    {
        Console.Write(it + " ");
    }
}
 
// Driver code   
static void Main()
{
    int N = 5;
     
    allQuotients(N);
}
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
 
// Javascript Program for the
// above approach
 
// Function to print all
// possible values of
// floor(N/K)
function allQuotients(N)
{
    var s = new Set();
    s.add(0);
 
    for (var k = 1; k <= parseInt(Math.sqrt(N)); k++) {
        s.add(k);
        s.add(parseInt(N / k));
    }
    var tmp = [...s];
    tmp.sort((a,b)=>a-b)
     
    tmp.forEach(it => {
        document.write( it + " ");
    });
}
 
var N = 5;
allQuotients(N);
 
// This code is contributed by noob2000.
</script>
Producción: 

0 1 2 5

 

Complejidad de tiempo: O(sqrt(n)*logn)

Espacio Auxiliar: O(n)
 

Publicación traducida automáticamente

Artículo escrito por yash2040 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *