Dada una array arr[] y tres enteros D , A y B . Comienza con el número D y en cualquier momento puede sumar o restar A o B al número actual. Eso significa que puede hacer las siguientes cuatro operaciones cualquier número de veces:
- Agregue A al número actual.
- Resta A del número actual.
- Sume B al número actual.
- Resta B del número actual.
La tarea es encontrar el recuento de enteros de la array dada que se puede alcanzar después de realizar las operaciones anteriores.
Ejemplos:
Entrada: arr[] = {4, 5, 6, 7, 8, 9}, D = 4, A = 4, B = 6
Salida: 3
Los números accesibles son:
4 = 4
6 = 4 + 6 – 4
8 = 4 + 4
Entrada: arr[] = {24, 53, 126, 547, 48, 97}, D = 2, A = 5, B = 8
Salida: 6
Enfoque: Este problema se puede resolver usando una propiedad de las ecuaciones diofánticas
Sea x el número entero al que queremos llegar desde la array . Si comenzamos con D y podemos sumar/restar A o B cualquier número de veces, eso significa que debemos encontrar si la siguiente ecuación tiene una solución entera o no.
D + p * A + q * B = x
Si tiene soluciones enteras en p y q , significa que podemos alcanzar el número entero x desde D , de lo contrario no.
Reordenar esta ecuación para
p * A + q * B = x – D
Esta ecuación tiene una solución entera si y solo si (x – D) % MCD(A, B) = 0 .
Ahora itere sobre los enteros en la array y verifique si esta ecuación tiene una solución o no para la x actual .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the GCD
// of a and b
int GCD(int a, int b)
{
if (b == 0)
return a;
return GCD(b, a % b);
}
// Function to return the count of reachable
// integers from the given array
int findReachable(int arr[], int D, int A,
int B, int n)
{
// GCD of A and B
int gcd_AB = GCD(A, B);
// To store the count of reachable integers
int count = 0;
for (int i = 0; i < n; i++) {
// If current element can be reached
if ((arr[i] - D) % gcd_AB == 0)
count++;
}
// Return the count
return count;
}
// Driver code
int main()
{
int arr[] = { 4, 5, 6, 7, 8, 9 };
int n = sizeof(arr) / sizeof(int);
int D = 4, A = 4, B = 6;
cout << findReachable(arr, D, A, B, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the GCD
// of a and b
static int GCD(int a, int b)
{
if (b == 0)
return a;
return GCD(b, a % b);
}
// Function to return the count of reachable
// integers from the given array
static int findReachable(int[] arr, int D, int A,
int B, int n)
{
// GCD of A and B
int gcd_AB = GCD(A, B);
// To store the count of reachable integers
int count = 0;
for (int i = 0; i < n; i++)
{
// If current element can be reached
if ((arr[i] - D) % gcd_AB == 0)
count++;
}
// Return the count
return count;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 5, 6, 7, 8, 9 };
int n = arr.length;
int D = 4, A = 4, B = 6;
System.out.println(findReachable(arr, D, A, B, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python implementation of the approach # Function to return the GCD # of a and b def GCD(a, b): if (b == 0): return a; return GCD(b, a % b); # Function to return the count of reachable # integers from the given array def findReachable(arr, D, A, B, n): # GCD of A and B gcd_AB = GCD(A, B); # To store the count of reachable integers count = 0; for i in range(n): # If current element can be reached if ((arr[i] - D) % gcd_AB == 0): count+=1; # Return the count return count; # Driver code arr = [ 4, 5, 6, 7, 8, 9 ]; n = len(arr); D = 4; A = 4; B = 6; print(findReachable(arr, D, A, B, n)); # This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the GCD
// of a and b
static int GCD(int a, int b)
{
if (b == 0)
return a;
return GCD(b, a % b);
}
// Function to return the count of reachable
// integers from the given array
static int findReachable(int[] arr, int D, int A,
int B, int n)
{
// GCD of A and B
int gcd_AB = GCD(A, B);
// To store the count of reachable integers
int count = 0;
for (int i = 0; i < n; i++)
{
// If current element can be reached
if ((arr[i] - D) % gcd_AB == 0)
count++;
}
// Return the count
return count;
}
// Driver code
public static void Main()
{
int []arr = { 4, 5, 6, 7, 8, 9 };
int n = arr.Length;
int D = 4, A = 4, B = 6;
Console.WriteLine(findReachable(arr, D, A, B, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript implementation of the approach
// Function to return the GCD
// of a and b
function GCD(a , b) {
if (b == 0)
return a;
return GCD(b, a % b);
}
// Function to return the count of reachable
// integers from the given array
function findReachable(arr, D, A, B, n)
{
// GCD of A and B
var gcd_AB = GCD(A, B);
// To store the count of reachable integers
var count = 0;
for (i = 0; i < n; i++)
{
// If current element can be reached
if ((arr[i] - D) % gcd_AB == 0)
count++;
}
// Return the count
return count;
}
// Driver code
var arr = [ 4, 5, 6, 7, 8, 9 ];
var n = arr.length;
var D = 4, A = 4, B = 6;
document.write(findReachable(arr, D, A, B, n));
// This code is contributed by aashish1995
</script>
3
Complejidad de tiempo: O(n * log(min(a, b))), donde a y b son dos parámetros para GCD.
Espacio auxiliar: O(log(min(a, b)))
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA