Dados dos números N y K , la tarea es encontrar el valor mínimo X tal que N < X*K .
Ejemplos:
Entrada: N = 8, K = 7
Salida: 2
Explicación:
Los números menores que K divisibles por N son 1, 2 y 4.
Entonces, el valor mínimo de X es 2 tal que 8 < 2*7 = 14.
Entrada: N = 999999733, K = 999999732
Salida: 999999733
Explicación:
Dado que 999999733 es un número primo, entonces 999999733 es divisible por 1 y el número mismo. Dado que K es menor que 999999733
, entonces el valor mínimo de X es 999999733 tal que 999999733 < 999999733*999999732.
Enfoque ingenuo: el enunciado del problema dado se puede visualizar como la ecuación K * X = N. En esta ecuación, el objetivo es minimizar X. Entonces tenemos que encontrar el K máximo que divide a N . A continuación se muestran los pasos:
- Iterar sobre [1, K] .
- Comprueba para cada número i tal que (N % i) = 0 . Continúe actualizando la variable max que almacena el divisor máximo de N recorrido hasta i .
- La respuesta requerida es N/max .
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 find the value of X
void findMaxValue(int N, int K)
{
int packages;
int maxi = 1;
// Loop to check all the numbers
// divisible by N that yield
// minimum N/i value
for (int i = 1; i <= K; i++) {
if (N % i == 0)
maxi = max(maxi, i);
}
packages = N / maxi;
// Print the value of packages
cout << packages << endl;
}
// Driver Code
int main()
{
// Given N and K
int N = 8, K = 7;
// Function Call
findMaxValue(N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG{
// Function to find the value of X
static void findMaxValue(int N, int K)
{
int packages;
int maxi = 1;
// Loop to check all the numbers
// divisible by N that yield
// minimum N/i value
for(int i = 1; i <= K; i++)
{
if (N % i == 0)
maxi = Math.max(maxi, i);
}
packages = N / maxi;
// Print the value of packages
System.out.println(packages);
}
// Driver code
public static void main (String[] args)
{
// Given N and K
int N = 8, K = 7;
// Function call
findMaxValue(N, K);
}
}
// This code is contributed by Shubham Prakash
Python3
# Python3 program for the above approach # Function to find the value of X def findMaxValue(N, K): packages = 0; maxi = 1; # Loop to check all the numbers # divisible by N that yield # minimum N/i value for i in range(1, K + 1): if (N % i == 0): maxi = max(maxi, i); packages = N // maxi; # Print value of packages print(packages); # Driver code if __name__ == '__main__': # Given N and K N = 8; K = 7; # Function call findMaxValue(N, K); # This code is contributed by sapnasingh4991
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the value of X
static void findMaxValue(int N, int K)
{
int packages;
int maxi = 1;
// Loop to check all the numbers
// divisible by N that yield
// minimum N/i value
for(int i = 1; i <= K; i++)
{
if (N % i == 0)
maxi = Math.Max(maxi, i);
}
packages = N / maxi;
// Print the value of packages
Console.WriteLine(packages);
}
// Driver code
public static void Main(String[] args)
{
// Given N and K
int N = 8, K = 7;
// Function call
findMaxValue(N, K);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to find the value of X
function findMaxValue(N, K)
{
let packages;
let maxi = 1;
// Loop to check all the numbers
// divisible by N that yield
// minimum N/i value
for (let i = 1; i <= K; i++) {
if (N % i == 0)
maxi = Math.max(maxi, i);
}
packages = parseInt(N / maxi);
// Print the value of packages
document.write(packages);
}
// Driver Code
// Given N and K
let N = 8, K = 7;
// Function Call
findMaxValue(N, K);
// This code is contributed by rishavmahato348.
</script>
Producción:
2
Complejidad temporal: O(K)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, encontraremos el factor utilizando el enfoque eficiente discutido en este artículo. A continuación se muestran los pasos:
- Inicialice la variable ans para almacenar el factor más grande de N .
- Itere sobre [1, sqrt(N)] y haga lo siguiente:
- Comprueba si N es divisible por i o no.
- Si no es así, busque el siguiente número.
- De lo contrario, si i ≤ K y N/i ≤ K , actualice ans al máximo (i, N/i) .
- El valor de X será N/ans.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to find the largest
// factor of N which is less than
// or equal to K
int solve(int n, int k)
{
// Initialise the variable to
// store the largest factor of
// N <= K
int ans = 0;
// Loop to find all factors of N
for (int j = 1;
j * j <= n; j++) {
// Check if j is a
// factor of N or not
if (n % j == 0) {
// Check if j <= K
// If yes, then store
// the larger value between
// ans and j in ans
if (j <= k) {
ans = max(ans, j);
}
// Check if N/j <= K
// If yes, then store
// the larger value between
// ans and j in ans
if (n / j <= k) {
ans = max(ans, n / j);
}
}
}
// Since max value is always
// stored in ans, the maximum
// value divisible by N less than
// or equal to K will be returned.
return ans;
}
// Driver Code
int main()
{
// Given N and K
int N = 8, K = 7;
// Function Call
cout << (N / solve(N, K));
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the largest
// factor of N which is less than
// or equal to K
static int solve(int n, int k)
{
// Initialise the variable to
// store the largest factor of
// N <= K
int ans = 0;
// Loop to find all factors of N
for(int j = 1; j * j <= n; j++)
{
// Check if j is a
// factor of N or not
if (n % j == 0)
{
// Check if j <= K
// If yes, then store
// the larger value between
// ans and j in ans
if (j <= k)
{
ans = Math.max(ans, j);
}
// Check if N/j <= K
// If yes, then store
// the larger value between
// ans and j in ans
if (n / j <= k)
{
ans = Math.max(ans, n / j);
}
}
}
// Since max value is always
// stored in ans, the maximum
// value divisible by N less than
// or equal to K will be returned.
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given N and K
int N = 8, K = 7;
// Function call
System.out.print((N / solve(N, K)));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find the largest # factor of N which is less than # or equal to K def solve(n, k): # Initialise the variable to # store the largest factor of # N <= K ans = 0; # Loop to find all factors of N for j in range(1, n + 1): if (j * j > n): break; # Check if j is a # factor of N or not if (n % j == 0): # Check if j <= K # If yes, then store # the larger value between # ans and j in ans if (j <= k): ans = max(ans, j); # Check if N/j <= K # If yes, then store # the larger value between # ans and j in ans if (n // j <= k): ans = max(ans, n // j); # Since max value is always # stored in ans, the maximum # value divisible by N less than # or equal to K will be returned. return ans; # Driver Code if __name__ == '__main__': # Given N and K N = 8; K = 7; # Function call print((N // solve(N, K))); # This code is contributed by gauravrajput1
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the largest
// factor of N which is less than
// or equal to K
static int solve(int n, int k)
{
// Initialise the variable to
// store the largest factor of
// N <= K
int ans = 0;
// Loop to find all factors of N
for(int j = 1; j * j <= n; j++)
{
// Check if j is a
// factor of N or not
if (n % j == 0)
{
// Check if j <= K
// If yes, then store
// the larger value between
// ans and j in ans
if (j <= k)
{
ans = Math.Max(ans, j);
}
// Check if N/j <= K
// If yes, then store
// the larger value between
// ans and j in ans
if (n / j <= k)
{
ans = Math.Max(ans, n / j);
}
}
}
// Since max value is always
// stored in ans, the maximum
// value divisible by N less than
// or equal to K will be returned.
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given N and K
int N = 8, K = 7;
// Function call
Console.Write((N / solve(N, K)));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program implementation
// of the approach
// Function to find the largest
// factor of N which is less than
// or equal to K
function solve(n, k)
{
// Initialise the variable to
// store the largest factor of
// N <= K
let ans = 0;
// Loop to find all factors of N
for(let j = 1; j * j <= n; j++)
{
// Check if j is a
// factor of N or not
if (n % j == 0)
{
// Check if j <= K
// If yes, then store
// the larger value between
// ans and j in ans
if (j <= k)
{
ans = Math.max(ans, j);
}
// Check if N/j <= K
// If yes, then store
// the larger value between
// ans and j in ans
if (n / j <= k)
{
ans = Math.max(ans, n / j);
}
}
}
// Since max value is always
// stored in ans, the maximum
// value divisible by N less than
// or equal to K will be returned.
return ans;
}
// Driver Code
// Given N and K
let N = 8, K = 7;
// Function call
document.write((N / solve(N, K)));
</script>
Producción:
2
Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por manunemalik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA