Dados dos enteros N y K , la tarea es encontrar el K -ésimo número que no sea divisible por N.
Nota: El valor de N es mayor que 1, porque todo número es divisible por 1.
Ejemplos:
Entrada: N = 3, K = 6
Salida: 8
Explicación:
Números que no son divisibles por N = 3 – {1, 2, 4, 5, 7, 8, 10}
El sexto número no divisible por 3 es 8.Entrada: N = 7, K = 97
Salida: 113
Explicación:
Números que no son divisibles por N = 7 – {1, 2, 4, 5, 6, ….}
El número 97 no divisible por 7 es 113.
Enfoque ingenuo: una solución simple es iterar en un bucle para encontrar el K – ésimo número no divisible por N. A continuación se muestran los pasos para encontrar el K -ésimo número:
- Inicialice el conteo de números no divisibles y el número actual a 0.
- Iterar usando un ciclo while hasta que el conteo del número no divisible no sea igual a K.
- Incrementa el conteo del número no divisible por 1, si el número actual no es divisible por N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find
// the K'th non divisible
// number by N
#include <bits/stdc++.h>
using namespace std;
// Function to find
// the K'th non divisible
// number by N
int kthNonDivisible(int N, int K)
{
int find = 0;
int j = 0;
// Loop to find the K non
// divisible number by N
while (find != K) {
j++;
if (j % N != 0)
find++;
}
return j;
}
// Driver Code
int main()
{
int N = 3;
int K = 6;
cout << kthNonDivisible(N, K);
return 0;
}
Java
// Java implementation to find
// the K'th non divisible
// number by N
class GFG{
// Function to find
// the K'th non divisible
// number by N
static int kthNonDivisible(int N, int K)
{
int find = 0;
int j = 0;
// Loop to find the K non
// divisible number by N
while (find != K)
{
j++;
if (j % N != 0)
find++;
}
return j;
}
// Driver code
public static void main(String[] args)
{
int N = 3;
int K = 6;
System.out.print(kthNonDivisible(N, K));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 implementation to find # the K'th non divisible # number of N import math # Function to find the Kth # not divisible by N def kthNonDivisible(n, K): find = 0 j = 0 # Loop to find the K non # divisible number by N while find != K: j = j + 1 if j % N != 0: find = find + 1 return j # Driver Code N = 3 K = 6 # Function Call print(kthNonDivisible(N, K)) # This code is contributed by ishayadav181
C#
// C# implementation to find the
// K'th non-divisible number by N
using System;
class GFG {
// Function to find the K'th
// non divisible number by N
static int kthNonDivisible(int N, int K)
{
int find = 0;
int j = 0;
// Loop to find the K non
// divisible number by N
while (find != K)
{
j++;
if (j % N != 0)
find++;
}
return j;
}
// Driver code
public static void Main(String[] args)
{
int N = 3;
int K = 6;
Console.Write(kthNonDivisible(N, K));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript implementation to find the
// K'th non-divisible number by N
// Function to find the K'th
// non divisible number by N
function kthNonDivisible(N, K)
{
let find = 0;
let j = 0;
// Loop to find the K non
// divisible number by N
while (find != K)
{
j++;
if (j % N != 0)
find++;
}
return j;
}
let N = 3;
let K = 6;
document.write(kthNonDivisible(N, K));
// This code is contributed by decode2207.
</script>
Producción
8
Otro enfoque: usar la búsqueda binaria La idea es usar la búsqueda binaria para resolver este problema. El espacio de búsqueda para este problema será desde 1 hasta el valor entero máximo y el valor medio se calcula como la diferencia de la mitad del espacio de búsqueda y los múltiplos de N.
- Si el valor medio es mayor que K, actualice el valor de H como medio-1.
- De lo contrario, si el valor medio es mayor que K, actualice el valor de L como medio – 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the Kth
// not divisible by N
void kthNonDivisible(int N, int K)
{
// Lowest possible value
int L = 1;
// Highest possible value
int H = INT_MAX;
// To store the Kth non
// divisible number of N
int ans = 0;
// Using binary search
while (L <= H)
{
// Calculating mid value
int mid = (L + H) / 2;
// Sol would have the value
// by subtracting all
// multiples of n till mid
int sol = mid - mid / N;
// Check if sol is greater than k
if (sol > K)
{
// H should be reduced to find
// minimum possible value
H = mid - 1;
}
// Check if sol is less than k
// then L will be mid+1
else if (sol < K)
{
L = mid + 1;
}
// Check if sol is equal to k
else
{
// ans will be mid
ans = mid;
// H would be reduced to find any
// more possible value
H = mid - 1;
}
}
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
int N = 3;
int K = 7;
// Function Call
kthNonDivisible(N, K);
return 0;
}
Java
// Java implementation for
// above approach
class GFG{
// Function to find the Kth
// not divisible by N
public static void kthNonDivisible(int N,
int K)
{
// Lowest possible value
int L = 1;
// Highest possible value
int H = Integer.MAX_VALUE;
// To store the Kth non
// divisible number of N
int ans = 0;
// Using binary search
while (L <= H)
{
// Calculating mid value
int mid = (L + H) / 2;
// Sol would have the value
// by subtracting all
// multiples of n till mid
int sol = mid - mid / N;
// Check if sol is greater than k
if (sol > K)
{
// H should be reduced to find
// minimum possible value
H = mid - 1;
}
// Check if sol is less than k
// then L will be mid+1
else if (sol < K)
{
L = mid + 1;
}
// Check if sol is equal to k
else
{
// ans will be mid
ans = mid;
// H would be reduced to find any
// more possible value
H = mid - 1;
}
}
// Print the answer
System.out.print(ans);
}
// Driver code
public static void main(String[] args)
{
int N = 3;
int K = 7;
// Function Call
kthNonDivisible(N, K);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation for # above approach import sys # Function to find the Kth # not divisible by N def kthNonDivisible(N, K): # Lowest possible value L = 1 # Highest possible value H = sys.maxsize # To store the Kth non # divisible number of N ans = 0 # Using binary search while (L <= H): # Calculating mid value mid = (L + H) // 2 # Sol would have the value # by subtracting all # multiples of n till mid sol = mid - mid // N # Check if sol is greater than k if (sol > K): # H should be reduced to find # minimum possible value H = mid - 1 # Check if sol is less than k # then L will be mid+1 elif (sol < K): L = mid + 1 # Check if sol is equal to k else: # ans will be mid ans = mid # H would be reduced to find any # more possible value H = mid - 1 # Print the answer print(ans) # Driver Code N = 3 K = 7 # Function call kthNonDivisible(N, K) # This code is contributed by ANKITKUMAR34
C#
// C# implementation for
// above approach
using System;
class GFG{
// Function to find the Kth
// not divisible by N
static void kthNonDivisible(int N, int K)
{
// Lowest possible value
int L = 1;
// Highest possible value
int H = Int32.MaxValue;
// To store the Kth non
// divisible number of N
int ans = 0;
// Using binary search
while (L <= H)
{
// Calculating mid value
int mid = (L + H) / 2;
// Sol would have the value
// by subtracting all
// multiples of n till mid
int sol = mid - mid / N;
// Check if sol is greater than k
if (sol > K)
{
// H should be reduced to find
// minimum possible value
H = mid - 1;
}
// Check if sol is less than k
// then L will be mid+1
else if (sol < K)
{
L = mid + 1;
}
// Check if sol is equal to k
else
{
// ans will be mid
ans = mid;
// H would be reduced to find
// any more possible value
H = mid - 1;
}
}
// Print the answer
Console.Write(ans);
}
// Driver code
static void Main()
{
int N = 3;
int K = 7;
// Function Call
kthNonDivisible(N, K);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript implementation for above approach
// Function to find the Kth
// not divisible by N
function kthNonDivisible(N, K)
{
// Lowest possible value
let L = 1;
// Highest possible value
let H = 2147483647;
// To store the Kth non
// divisible number of N
let ans = 0;
// Using binary search
while (L <= H)
{
// Calculating mid value
let mid = parseInt((L + H) / 2, 10);
// Sol would have the value
// by subtracting all
// multiples of n till mid
let sol = mid - parseInt(mid / N, 10);
// Check if sol is greater than k
if (sol > K)
{
// H should be reduced to find
// minimum possible value
H = mid - 1;
}
// Check if sol is less than k
// then L will be mid+1
else if (sol < K)
{
L = mid + 1;
}
// Check if sol is equal to k
else
{
// ans will be mid
ans = mid;
// H would be reduced to find
// any more possible value
H = mid - 1;
}
}
// Print the answer
document.write(ans);
}
let N = 3;
let K = 7;
// Function Call
kthNonDivisible(N, K);
// This code is contributed by mukesh07.
</script>
Producción
10
Complejidad de tiempo: O (logN)
Enfoque eficiente: La observación clave en el problema es que todo número del 1 al N-1 no es divisible por N y luego De manera similar, N + 1 a 2*N – 1 tampoco es divisible por N. Teniendo esto en cuenta, el El número K no divisible por N será:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find
// the K'th non-divisible
// number of N
#include <bits/stdc++.h>
using namespace std;
// Function to find the Kth
// not divisible by N
int kthNonDivisible(int N, int K)
{
return K + floor((K - 1) / (N - 1));
}
// Driver Code
int main()
{
int N = 3;
int K = 6;
// Function Call
cout << kthNonDivisible(N, K);
return 0;
}
Java
// Java implementation to find the
// K'th non-divisible number of N
class GFG{
// Function to find the Kth
// not divisible by N
static int kthNonDivisible(int N, int K)
{
return (int) (K + Math.floor((K - 1) / (N - 1)));
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
int K = 6;
// Function Call
System.out.print(kthNonDivisible(N, K));
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 implementation to find # the K'th non-divisible # number of N import math # Function to find the Kth # not divisible by N def kthNonDivisible(N, K): return K + math.floor((K - 1) / (N - 1)) # Driver Code N = 3 K = 6 # Function Call print(kthNonDivisible(N, K)) # This code is contributed by ishayadav181
C#
// C# implementation to find the
// K'th non-divisible number of N
using System;
class GFG{
// Function to find the Kth
// not divisible by N
static int kthNonDivisible(int N, int K)
{
return (int) (K + Math.Floor((double)(K - 1) /
(N - 1)));
}
// Driver Code
public static void Main(String[] args)
{
int N = 3;
int K = 6;
// Function Call
Console.Write(kthNonDivisible(N, K));
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript implementation to find
// the K'th non-divisible
// number of N
// Function to find the Kth
// not divisible by N
function kthNonDivisible(N, K)
{
return K + parseInt(
Math.floor((K - 1) / (N - 1)), 10);
}
// Driver code
let N = 3;
let K = 6;
// Function Call
document.write(kthNonDivisible(N, K));
// This code is contributed by suresh07
</script>
Producción
8
Publicación traducida automáticamente
Artículo escrito por mayur_patil y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA