Dados dos enteros positivos N y K , la tarea es imprimir el K-ésimo factor más grande de N .
Entrada: N = 12, K = 3
Salida: 4
Explicación: Los factores de 12 son {1, 2, 3, 4, 6, 12}. El factor más grande es 12 y el tercer factor más grande es 4.Entrada: N = 30, K = 2
Salida: 15
Explicación: Los factores de 30 son {1, 2, 3, 5, 6, 10, 15, 30} y el segundo factor más grande es 15.
Enfoque: La idea es verificar cada número en el rango [N, 1] e imprimir el K-ésimo número que divide a N por completo.
Iterar a través del ciclo de N a 0 . Ahora, para cada número en este bucle:
- Comprueba si divide a N o no.
- Si N es divisible por el número actual, disminuya el valor de K en 1.
- Cuando K se convierte en 0, esto significa que el número actual es el K-ésimo factor más grande de N.
- Escriba la respuesta de acuerdo con la observación anterior.
A continuación se muestra la implementación del enfoque anterior:
C
// C program for the above approach
#include <stdio.h>
// Function to print Kth largest
// factor of N
int KthLargestFactor(int N, int K)
{
// Check for numbers
// in the range [N, 1]
for (int i = N; i > 0; i--) {
// Check if i is a factor of N
if (N % i == 0)
// If Yes, reduce K by 1
K--;
// If K is 0, it means
// i is the required
// Kth factor of N
if (K == 0) {
return i;
}
}
// When K is more
// than the factors of N
return -1;
}
// Driver Code
int main()
{
int N = 12, K = 3;
printf("%d", KthLargestFactor(N, K));
return 0;
}
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to print Kth largest
// factor of N
int KthLargestFactor(int N, int K)
{
// Check for numbers
// in the range [N, 1]
for (int i = N; i > 0; i--) {
// Check if i is a factor of N
if (N % i == 0)
// If Yes, reduce K by 1
K--;
// If K is 0, it means
// i is the required
// Kth factor of N
if (K == 0) {
return i;
}
}
// When K is more
// than the factors of N
return -1;
}
// Driver Code
int main()
{
int N = 12, K = 3;
cout << KthLargestFactor(N, K);
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to print Kth largest
// factor of N
static int KthLargestFactor(int N, int K)
{
// Check for numbers
// in the range [N, 1]
for (int i = N; i > 0; i--) {
// Check if i is a factor of N
if (N % i == 0)
// If Yes, reduce K by 1
K--;
// If K is 0, it means
// i is the required
// Kth factor of N
if (K == 0) {
return i;
}
}
// When K is more
// than the factors of N
return -1;
}
// Driver Code
public static void main(String[] args)
{
int N = 12, K = 3;
System.out.println(KthLargestFactor(N, K));
}
}
Python
# Python program for the above approach # Function to print Kth largest # factor of N def KthLargestFactor(N, K): for i in range(N, 0, -1): if N % i == 0: K -= 1 if K == 0: return i return -1 # Driver Code N = 12 K = 3 print(KthLargestFactor(N, K))
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print Kth largest
// factor of N
static int KthLargestFactor(int N, int K)
{
// Check for numbers
// in the range [N, 1]
for (int i = N; i > 0; i--) {
// Check if i is a factor of N
if (N % i == 0)
// If Yes, reduce K by 1
K--;
// If K is 0, it means
// i is the required
// Kth factor of N
if (K == 0) {
return i;
}
}
// When K is more
// than the factors of N
return -1;
}
// Driver Code
public static void Main()
{
int N = 12, K = 3;
Console.Write(KthLargestFactor(N, K));
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript program for the above approach
// Function to print Kth largest
// factor of N
function KthLargestFactor(N, K)
{
// Check for numbers
// in the range [N, 1]
for (let i = N; i > 0; i--) {
// Check if i is a factor of N
if (N % i == 0)
// If Yes, reduce K by 1
K--;
// If K is 0, it means
// i is the required
// Kth factor of N
if (K == 0) {
return i;
}
}
// When K is more
// than the factors of N
return -1;
}
// Driver Code
let N = 12, K = 3;
document.write(KthLargestFactor(N, K));
// This code is contributed by shivanisinghss2110
</script>
4
Tiempo Complejidad: 
Espacio Auxiliar: 
Enfoque eficiente: el problema se puede resolver de manera optimizada en complejidad sqrt (n) utilizando el hecho de que los factores de cualquier número permanecen en forma de pares . En otras palabras, si i es un factor del número n , entonces n/i también será un factor de n . Entonces, para encontrar todos los factores del número, debemos verificar los factores hasta sqrt (n) y sus pares correspondientes. En el artículo se utiliza un tipo de enfoque similar: encontrar divisores de números naturales .
Ilustración:
Si n = 80, entonces todos los pares de divisores posibles son: (1,80), (2,40), (4,20), (5,16), (8,10). Por lo tanto, para almacenar todos los factores de 80, iteraremos el ciclo de 1 a √80 ≈ 8 y almacenaremos los factores en el rango (que incluye 1,2,4,5,8 aquí en este caso). Después de esto, ejecutamos un bucle inverso y almacenamos los pares de estos factores anteriores (que darán 10, 16, 20, 40 y 80). Aquí estamos ejecutando un bucle inverso para que podamos obtener los pares en orden creciente. De esta forma, obtendremos todos los factores que incluyen {1, 2, 4, 5, 8, 10, 16, 20, 40 y 80}.
Acercarse:
- Inicialice un vector para almacenar los elementos en orden creciente.
- Primero, itera un ciclo de 1 a sqrt(n) y almacena todos los factores.
- Luego itera el ciclo en orden inverso y para cada factor almacena su par correspondiente. Entonces, si i es el factor, entonces almacene n/i .
- Si el tamaño del vector es mayor o igual a k, devuelva el k-ésimo factor más grande (que será v[v.size()-k] ya que el vector v está en orden creciente).
- Si k elementos no existen, eso significa que no hay k-ésimo factor más grande y, por lo tanto, devuelve -1 .
Manejo de los casos de esquina:
Surgirá un caso de esquina cuando cualquier factor sea exactamente igual a sqrt(n). Por ejemplo, si n=100, entonces en este caso 10 será un factor del número, y también su par correspondiente es 10 como (10*10=100). Entonces, en este caso, 10 se tomará dos veces. Para abordar este caso, usamos una declaración if entre dos bucles y eliminamos el problema al considerar este factor solo una vez.
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 Kth largest
// factor of N
int KthLargestFactor(int n, int k)
{
// vector v to store the factors
// of n in increasing order
vector<int> v;
int i;
// Iterating the loop and checking
// factors till sqrt(n)
for (i = 1; i * i <= n; i++) {
if (n % i == 0)
v.push_back(i);
}
// corner cases
if (i * i == n) {
i--;
}
for (; i >= 1; i--) {
if (n % i == 0)
v.push_back(n / i);
}
// When k is less than the factors
// of n then return the kth
// largest element which will be
// will kth element from the end
// in the vector
if (k <= v.size()) {
return v[v.size() - k];
}
// When k is more
// than the factors of n
else
return -1;
}
// Driver Code
int main()
{
int N = 12, K = 3;
cout << KthLargestFactor(N, K);
}
// This code is contributed by Pushpesh raj
4
Complejidad temporal: O(sqrt(n))
Espacio auxiliar: O(m) donde m es el número total de factores de n.
Publicación traducida automáticamente
Artículo escrito por suchithareddy3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA