Número de elementos de array derivables de D después de realizar ciertas operaciones

Posted on by Rudeus Greyrat

Dada una array de N enteros y 3 enteros D, A y B. La tarea es encontrar el número de elementos de la array en los que podemos convertir D realizando las siguientes operaciones en D: 
 

  • Añadir A (+A)
  • Restar A (-A)
  • Añadir B (+B)
  • Restar B (-B)

Nota : Está permitido realizar cualquier número de operaciones de cualquier tipo.
Ejemplos: 
 

Input :  arr = {1, 2, 3}, D = 6, A = 3, B = 2 
Output :  3
Explanation: 
We can derive 1 from D by performing (6 - 3(A) - 2(B))
We can derive 2 from D by performing (6 - 2(A) - 2(A))
We can derive 3 from D by performing (6 - 3(A))
Thus, All array elements can be derived from D.
 
Input :  arr = {1, 2, 3}, D = 7, A = 4, B = 2 
Output :  2
Explanation: 
We can derive 1 from D by performing (7 - 4(A) - 2(B))
We can derive 3 from D by performing (7 - 4(A))
Thus, we can derive {1, 3}

Digamos que queremos verificar si el elemento a i puede derivarse de D:
supongamos que realizamos: 
 

  • La operación de type1 (ie Add A) P veces.
  • La operación de tipo 2 (es decir, Restar A) Q veces.
  • La operación de tipo 3 (es decir, Agregar B) R veces.
  • La operación de tipo 4 (es decir, Restar B) S veces.

Sea X el valor que obtenemos después de realizar estas operaciones, entonces, 
-> X = P*A – Q*A + R*B – S*B 
-> X = (P – Q) * A + (R – S) * B
Supongamos que derivamos con éxito A i de D, es decir, X = |A i – D|, 
-> |A i – D| = (P – Q) * A + (R – S) * B
Sea (P – Q) = alguna constante, digamos, U 
y de manera similar sea (R – S) una constante, V
-> |A i – D| = U * A + V * B
Esto tiene la forma de la Ecuación Diofántica Lineal y la solución existe solo cuando |A i – D| es divisible por mcd(A, B). 
 

Por lo tanto, ahora podemos simplemente iterar sobre la array y contar todos los A i para los que |A i – D| es divisible por mcd(a, b).
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// CPP program to find the number of array elements
// which can be derived by perming (+A, -A, +B, -B)
// operations on D
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to return
// gcd of a and b
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
/* Function to Return the number of elements
   of arr[] which can be derived from D by
   performing (+A, -A, +B, -B) */
int findPossibleDerivables(int arr[], int n, int D,
                                      int A, int B)
{
    // find the gcd of A and B
    int gcdAB = gcd(A, B);
 
    // counter stores the number of
    // array elements which
    // can be derived from D
    int counter = 0;
 
    for (int i = 0; i < n; i++) {
        // arr[i] can be derived from D only if
        // |arr[i] - D| is divisible by gcd of A and B
        if ((abs(arr[i] - D) % gcdAB) == 0) {
            counter++;
        }
    }
 
    return counter;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 7, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int D = 5, A = 4, B = 2;
    cout << findPossibleDerivables(arr, n, D, A, B) <<"\n";
 
    int a[] = { 1, 2, 3 };
    n = sizeof(a) / sizeof(a[0]);
    D = 6, A = 3, B = 2;
    cout << findPossibleDerivables(a, n, D, A, B) <<"\n";
 
    return 0;
}

Java

// Java  program to find the number of array elements
// which can be derived by perming (+A, -A, +B, -B)
// operations on D
 
import java.io.*;
 
class GFG {
     
 
 
// Function to return
// gcd of a and b
 static int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
/* Function to Return the number of elements
of arr[] which can be derived from D by
performing (+A, -A, +B, -B) */
static int findPossibleDerivables(int arr[], int n, int D,
                                    int A, int B)
{
    // find the gcd of A and B
    int gcdAB = gcd(A, B);
 
    // counter stores the number of
    // array elements which
    // can be derived from D
    int counter = 0;
 
    for (int i = 0; i < n; i++) {
        // arr[i] can be derived from D only if
        // |arr[i] - D| is divisible by gcd of A and B
        if ((Math.abs(arr[i] - D) % gcdAB) == 0) {
            counter++;
        }
    }
 
    return counter;
}
 
// Driver Code
 
    public static void main (String[] args) {
            int arr[] = { 1, 2, 3, 4, 7, 13 };
    int n = arr.length;
    int D = 5, A = 4, B = 2;
    System.out.println( findPossibleDerivables(arr, n, D, A, B));
 
    int a[] = { 1, 2, 3 };
    n = a.length;
    D = 6;
    A = 3;
    B = 2;
    System.out.println( findPossibleDerivables(a, n, D, A, B));
    }
}
// This code is contributed by anuj_67..

Python3

# Python3 program to find the number of array
# elements which can be derived by perming
# (+A, -A, +B, -B) operations on D
 
# Function to return gcd of a and b
def gcd(a, b) :
     
    if (a == 0) :
        return b
         
    return gcd(b % a, a);
 
""" Function to Return the number of elements
of arr[] which can be derived from D by
performing (+A, -A, +B, -B) """
def findPossibleDerivables(arr, n, D, A, B) :
 
    # find the gcd of A and B
    gcdAB = gcd(A, B)
     
    # counter stores the number of
    # array elements which
    # can be derived from D
    counter = 0
 
    for i in range(n) :
         
        # arr[i] can be derived from D only
        # if |arr[i] - D| is divisible by
        # gcd of A and B
        if ((abs(arr[i] - D) % gcdAB) == 0) :
            counter += 1
 
    return counter
 
# Driver Code
if __name__ == "__main__" :
     
    arr = [ 1, 2, 3, 4, 7, 13 ]
    n = len(arr)
    D, A, B = 5, 4, 2
     
    print(findPossibleDerivables(arr, n, D, A, B))
 
    a = [ 1, 2, 3 ]
    n = len(a)
    D, A, B = 6, 3, 2
     
    print(findPossibleDerivables(a, n, D, A, B))
 
# This code is contributed by Ryuga

C#

// C# program to find the number of array elements
// which can be derived by perming (+A, -A, +B, -B)
// operations on D
using System;   
public class GFG {
 
    // Function to return
    // gcd of a and b
     static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
 
    /* Function to Return the number of elements
    of arr[] which can be derived from D by
    performing (+A, -A, +B, -B) */
    static int findPossibleDerivables(int []arr, int n, int D,
                                        int A, int B)
    {
        // find the gcd of A and B
        int gcdAB = gcd(A, B);
 
        // counter stores the number of
        // array elements which
        // can be derived from D
        int counter = 0;
 
        for (int i = 0; i < n; i++) {
            // arr[i] can be derived from D only if
            // |arr[i] - D| is divisible by gcd of A and B
            if ((Math.Abs(arr[i] - D) % gcdAB) == 0) {
                counter++;
            }
        }
 
        return counter;
    }
 
    // Driver Code
  
    public static void Main () {
            int []arr = { 1, 2, 3, 4, 7, 13 };
    int n = arr.Length;
    int D = 5, A = 4, B = 2;
    Console.WriteLine( findPossibleDerivables(arr, n, D, A, B));
  
    int []a = { 1, 2, 3 };
    n = a.Length;
    D = 6;
    A = 3;
    B = 2;
    Console.WriteLine( findPossibleDerivables(a, n, D, A, B));
    }
}
// This code is contributed by 29AjayKumar

PHP

<?php
// PHP program to find the number of
// array elements which can be derived by
// perming (+A, -A, +B, -B) operations on D
 
// Function to return gcd of a and b
function gcd($a, $b)
{
    if ($a == 0)
        return $b;
    return gcd($b % $a, $a);
}
 
/* Function to Return the number of elements
of arr[] which can be derived from D by
performing (+A, -A, +B, -B) */
 
function findPossibleDerivables($arr, $n,
                                $D, $A, $B)
{
    // find the gcd of A and B
    $gcdAB = gcd($A, $B);
 
    // counter stores the number of
    // array elements which
    // can be derived from D
    $counter = 0;
 
    for ($i = 0; $i < $n; $i++)
    {
        // arr[i] can be derived from D only
        // if |arr[i] - D| is divisible by
        // gcd of A and B
        if ((abs($arr[$i] - $D) % $gcdAB) == 0)
        {
            $counter++;
        }
    }
 
    return $counter;
}
 
// Driver Code
$arr = array( 1, 2, 3, 4, 7, 13 );
$n = sizeof($arr);
$D = 5;
$A = 4;
$B = 2;
echo findPossibleDerivables($arr, $n,
                            $D, $A, $B), "\n";
 
$a = array( 1, 2, 3 );
$n = sizeof($a);
$D = 6;
$A = 3;
$B = 2;
echo findPossibleDerivables($arr, $n,
                            $D, $A, $B), "\n";
 
// This code is contributed by ajit.
?>

Javascript

<script>
// javascript  program to find the number of array elements
// which can be derived by perming (+A, -A, +B, -B)
// operations on D   
 
// Function to return
    // gcd of a and b
    function gcd(a , b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
 
    /*
     * Function to Return the number of elements of arr which can be derived from
     * D by performing (+A, -A, +B, -B)
     */
    function findPossibleDerivables(arr , n , D , A , B) {
        // find the gcd of A and B
        var gcdAB = gcd(A, B);
 
        // counter stores the number of
        // array elements which
        // can be derived from D
        var counter = 0;
 
        for (i = 0; i < n; i++)
        {
         
            // arr[i] can be derived from D only if
            // |arr[i] - D| is divisible by gcd of A and B
            if ((Math.abs(arr[i] - D) % gcdAB) == 0) {
                counter++;
            }
        }
 
        return counter;
    }
 
    // Driver Code
        var arr = [ 1, 2, 3, 4, 7, 13 ];
        var n = arr.length;
        var D = 5, A = 4, B = 2;
        document.write(findPossibleDerivables(arr, n, D, A, B)+"<br/>");
 
        var a = [ 1, 2, 3 ];
        n = a.length;
        D = 6;
        A = 3;
        B = 2;
        document.write(findPossibleDerivables(a, n, D, A, B));
 
// This code is contributed by todaysgaurav.
</script>
Producción: 

4
3

 

Complejidad de tiempo: O(log(max(A, B) + N), donde N es el número de elementos de la array y A & B representa el valor de los números enteros dados.
Espacio auxiliar : O(log(max(A, B)) debido al espacio recursivo de la pila.  

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *