Encuentra el número N en una secuencia que no es un múltiplo de un número dado

Dados cuatro enteros A , N , L y R , la tarea es encontrar el número N en una secuencia de enteros consecutivos de L a R que no sea un múltiplo de A . Se da que la sucesión contiene al menos N números que no son divisibles por A y el entero A siempre es mayor que 1.

Ejemplos:

Entrada: A = 2, N = 3, L = 1, R = 10
Salida: 5
Explicación:
La secuencia es 1 , 2, 3 , 4, 5 , 6, 7 , 8, 9 y 10. Aquí 5 es el tercero número que no es un múltiplo de 2 en la secuencia.

Entrada: A = 3, N = 6, L = 4, R = 20
Salida: 11
Explicación:
11 es el sexto número que no es un múltiplo de 3 en la secuencia.

Enfoque ingenuo: el enfoque ingenuo es iterar sobre el rango [L, R] en un bucle para encontrar el ^número N. Los pasos son:

Inicialice el conteo de números no múltiples y el número actual a 0.
Iterar sobre el rango [L, R] hasta que el recuento del número no múltiplo no sea igual a N .
Incrementa el conteo del número no múltiplo en 1, si el número actual no es divisible por A.

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 Nth number not a
// multiple of A in the range [L, R]
void count_no (int A, int N, int L, int R)
{
     
    // To store the count
    int count = 0;
    int i = 0;
 
    // To check all the nos in range
    for(i = L; i < R + 1; i++)
    {
    if (i % A != 0)
        count += 1;
         
    if (count == N)
        break;
    }
    cout << i;
}
 
// Driver code
int main()
{
     
    // Given values of A, N, L, R
    int A = 3, N = 6, L = 4, R = 20;
     
    // Function Call
    count_no (A, N, L, R);
    return 0;
}
 
// This code is contributed by mohit kumar 29

Java

// Java program for the above approach
import java.util.*;
import java.io.*;
 
class GFG{
     
// Function to find Nth number not a
// multiple of A in the range [L, R]
static void count_no (int A, int N,
                      int L, int R)
{
 
    // To store the count
    int count = 0;
    int i = 0;
 
    // To check all the nos in range
    for(i = L; i < R + 1; i++)
    {
        if (i % A != 0)
            count += 1;
     
        if (count == N)
            break;
    }
    System.out.println(i);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given values of A, N, L, R
    int A = 3, N = 6, L = 4, R = 20;
 
    // Function call
    count_no (A, N, L, R);
}
}
 
// This code is contributed by sanjoy_62

Python3

# Python3 program for the above approach
 
# Function to find Nth number not a
# multiple of A in the range [L, R]
def count_no (A, N, L, R):
 
    # To store the count
    count = 0
 
    # To check all the nos in range
    for i in range ( L, R + 1 ):
        if ( i % A != 0 ):
            count += 1
 
        if ( count == N ):
            break
    print ( i )
     
# Given values of A, N, L, R
A, N, L, R = 3, 6, 4, 20
 
# Function Call
count_no (A, N, L, R)

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find Nth number not a
// multiple of A in the range [L, R]
static void count_no (int A, int N,
                      int L, int R)
{
     
    // To store the count
    int count = 0;
    int i = 0;
 
    // To check all the nos in range
    for(i = L; i < R + 1; i++)
    {
        if (i % A != 0)
            count += 1;
     
        if (count == N)
            break;
    }
    Console.WriteLine(i);
}
 
// Driver code
public static void Main()
{
     
    // Given values of A, N, L, R
    int A = 3, N = 6, L = 4, R = 20;
 
    // Function call
    count_no (A, N, L, R);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to find Nth number not a
// multiple of A in the range [L, R]
function count_no (A, N, L, R)
{
  
    // To store the count
    let count = 0;
    let i = 0;
  
    // To check all the nos in range
    for(i = L; i < R + 1; i++)
    {
        if (i % A != 0)
            count += 1;
      
        if (count == N)
            break;
    }
   document.write(i);
}
 
// Driver Code
 
    // Given values of A, N, L, R
    let A = 3, N = 6, L = 4, R = 20;
  
    // Function call
    count_no (A, N, L, R);
     
    // This code is contributed by chinmoy1997pal.
</script>

Producción:

Complejidad temporal: O(R – L)
Espacio auxiliar: O(1)

Enfoque eficiente:
la observación clave es que hay números A – 1 que no son divisibles por A en el rango [1, A – 1] . De manera similar, hay números A – 1 no divisibles por A en el rango [A + 1, 2 * A – 1], [2 * A + 1, 3 * A – 1] y así sucesivamente.
Con la ayuda de esta observación, el N ^número que no es divisible por A será:

$N + \left \lfloor \frac{N - 1}{A - 1} \right \rfloor$

Para encontrar el valor en el rango [ L, R ], necesitamos cambiar el origen de ‘0’ a ‘L – 1’, por lo que podemos decir que el número N que no es ^divisible por A en el rango será :

$(L - 1) + \left \lfloor \frac{N - 1}{A - 1} \right \rfloor$

Sin embargo, hay un caso extremo, cuando el valor de ( L – 1 ) + N + piso ( ( N – 1 ) / ( A – 1 ) ) en sí mismo resulta ser múltiplo de ‘A’ , en ese caso N número estarán :

$(L - 1) + \left \lfloor \frac{N - 1}{A - 1} \right \rfloor + 1$

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 Nth number
// not a multiple of A in range [L, R]
void countNo(int A, int N, int L, int R)
{
     
    // Calculate the Nth no
    int ans = L - 1 + N + floor((N - 1) /
                                (A - 1));
     
    // Check for the edge case
    if (ans % A == 0)
    {
        ans = ans + 1;
    }
    cout << ans << endl;
}
 
// Driver Code
int main()
{
     
    // Input parameters
    int A = 5, N = 10, L = 4, R = 20;
     
    // Function Call
    countNo(A, N, L, R);
     
    return 0;
}
 
// This code is contributed by avanitrachhadiya2155

Java

// Java program for the above approach
import java.io.*;
 
class GFG
{
 
  // Function to find Nth number
  // not a multiple of A in range [L, R]
  static void countNo(int A, int N, int L, int R)
  {
 
    // Calculate the Nth no
    int ans = L - 1 + N + (int)Math.floor((N - 1) / (A - 1));
 
    // Check for the edge case
    if (ans % A == 0)
    {
      ans = ans + 1;
    }
    System.out.println(ans);   
  }
 
  // Driver Code
  public static void main (String[] args)
  {
 
    // Input parameters
    int A = 5, N = 10, L = 4, R = 20;
 
    // Function Call
    countNo(A, N, L, R);   
  }
}
 
//  This code is contributed by rag2127

Python3

# Python3 program for the above approach
import math
 
# Function to find Nth number
# not a multiple of A in range [L, R]
def countNo (A, N, L, R):
 
    # Calculate the Nth no
    ans = L - 1 + N \
          + math.floor( ( N - 1 ) / ( A - 1 ) )
     
    # Check for the edge case
    if ans % A == 0:
        ans = ans + 1;
    print(ans)
 
# Input parameters
A, N, L, R = 5, 10, 4, 20
 
# Function Call
countNo(A, N, L, R)

C#

// C# program for the above approach
using System;
class GFG {
 
  // Function to find Nth number
  // not a multiple of A in range [L, R]
  static void countNo(int A, int N, int L, int R)
  {
 
    // Calculate the Nth no
    int ans = L - 1 + N + ((N - 1) / (A - 1));
 
    // Check for the edge case
    if (ans % A == 0)
    {
      ans = ans + 1;
    }
    Console.WriteLine(ans);
  }
 
  // Driver code
  static void Main()
  {
 
    // Input parameters
    int A = 5, N = 10, L = 4, R = 20;
 
    // Function Call
    countNo(A, N, L, R);
  }
}
 
// This code is contributed by divyesh072019.

Javascript

<script>
 
// Javascript program for
// the above approach
 
// Function to find Nth number
// not a multiple of A in range [L, R]
function countNo(A, N, L, R)
{
 
    // Calculate the Nth no
    var ans = L - 1 + N +
      Math.floor((N - 1) / (A - 1));
     
    // Check for the edge case
    if (ans % A == 0)
    {
        ans = ans + 1;
    }
    document.write(ans);   
}
 
// Driver code
 
// Input parameters
var A = 5, N = 10, L = 4, R = 20;
 
// Function Call
countNo(A, N, L, R); 
 
// This code is contributed by Khushboogoyal499
    
</script>

Producción:

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta