Alcanza los números haciendo saltos de dos longitudes dadas

Dados los enteros k , d1 , d2 y una array de enteros arr[] . A partir del número k , puede realizar saltos de tamaño d1 y d2 , es decir, todos los movimientos posibles desde k son: 
 

• k + d1 y k – d1
• k + d2 y k – d2

La tarea es encontrar cuáles de los números de la array son accesibles desde k haciendo cualquier número de saltos y cualquier salto dado es de tamaño d1 o d2 . Para cada número, imprima 1 si es accesible, de lo contrario, imprima 0 .
Ejemplos: 
 

Entrada: k = 10, d1 = 4, d2 = 6, arr[] = {10, 15, 20} 
Salida: 1 0 1 
10 se puede alcanzar desde k sin movimiento adicional. 
Se puede llegar a 20 con k + d1 + d2 = 10 + 4 + 6 = 20
Entrada: k = 8, d1 = 3, d2 = 2, arr[] = {9, 4} 
Salida: 1 1 
 

Enfoque: Cualquier número x que sea alcanzable desde k con saltos d1 o d2 será de la forma x = k + (i * d1) + (j * d2) donde i y j son números enteros. Sea
el MCD de d1 y d2 mcd . Dado que mcd divide tanto a d1 como a d2 . Por tanto podemos escribir d1 = m1 * mcd y d2 = m2 * mcd donde m1 y m2 son números enteros 
Y x = k + mcd * (i * m1 + j * m2) = k + M * mcd. 
Entonces, cualquier número x al que se pueda llegar desde k debe satisfacer (x – k) % mcd = 0 .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <algorithm>
#include <iostream>
using namespace std;
 
// Function that returns the vector containing the
// result for the reachability of the required numbers
void reachTheNums(int nums[], int k, int d1, int d2, int n)
{
    int i, ans[n] = { 0 };
    int gcd = __gcd(d1, d2);
 
    for (i = 0; i < n; i++) {
        int x = nums[i] - k;
 
        // If distance x is coverable
        if (x % gcd == 0)
            ans[i] = 1;
        else
            ans[i] = 0;
    }
 
    for (i = 0; i < n; i++)
        cout << ans[i] << " ";
}
 
// Driver code
int main()
{
    // Numbers to be checked for reachability
    int nums[] = { 9, 4 };
    int n = sizeof(nums) / sizeof(nums[0]);
    // Starting number K
    int k = 8;
 
    // Sizes of jumps d1 and d2
    int d1 = 3, d2 = 2;
 
    reachTheNums(nums, k, d1, d2, n);
 
    return 0;
}

// Java implementation of the approach
 
import java.io.*;
class GFG {
// Recursive function to return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0 
        if (a == 0)
          return b;
        if (b == 0)
          return a;
        
        // base case
        if (a == b)
            return a;
        
        // a is greater
        if (a > b)
            return __gcd(a-b, b);
        return __gcd(a, b-a);
    }
 
 
     
 
// Function that returns the vector containing the
// result for the reachability of the required numbers
static void reachTheNums(int nums[], int k, int d1, int d2, int n)
{
    int i;
    int ans[] = new int[n];
    int gcd = __gcd(d1, d2);
 
    for (i = 0; i < n; i++) {
        int x = nums[i] - k;
 
        // If distance x is coverable
        if (x % gcd == 0)
            ans[i] = 1;
        else
            ans[i] = 0;
    }
 
    for (i = 0; i < n; i++)
        System.out.print(ans[i] + " ");
}
 
// Driver code
 
 
    public static void main (String[] args) {
        // Numbers to be checked for reachability
    int nums[] = { 9, 4 };
    int n =nums.length;
    // Starting number K
    int k = 8;
 
    // Sizes of jumps d1 and d2
    int d1 = 3, d2 = 2;
 
    reachTheNums(nums, k, d1, d2, n);
    }
}
 
// This code is contributed by inder_verma..

# Python3 implementation of the approach
import math as mt
 
# Function that returns the vector
# containing the result for the reachability
# of the required numbers
def reachTheNums(nums, k, d1, d2, n):
 
    ans = [0 for i in range(n)]
 
    gcd = mt.gcd(d1, d2)
 
    for i in range(n):
        x = nums[i] - k
 
        # If distance x is coverable
        if (x % gcd == 0):
            ans[i] = 1
        else:
            ans[i] = 0
 
    for i in range(n):
        print(ans[i], end = " ")
 
# Driver code
 
# Numbers to be checked for
# reachability
nums = [9, 4]
n = len(nums)
 
# Starting number K
k = 8
 
# Sizes of jumps d1 and d2
d1, d2 = 3, 2
 
reachTheNums(nums, k, d1, d2, n)
 
# This code is contributed
# by mohit kumar 29

// C# implementation of the above approach
 
using System ;
 
class GFG {
     
    // Recursive function to return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
        return b;
        if (b == 0)
        return a;
         
        // base case
        if (a == b)
            return a;
         
        // a is greater
        if (a > b)
            return __gcd(a-b, b);
             
        return __gcd(a, b-a);
    }
 
 
     
 
    // Function that returns the vector containing the
    // result for the reachability of the required numbers
    static void reachTheNums(int []nums, int k, int d1, int d2, int n)
    {
        int i;
        int []ans = new int[n];
        int gcd = __gcd(d1, d2);
     
        for (i = 0; i < n; i++) {
            int x = nums[i] - k;
     
            // If distance x is coverable
            if (x % gcd == 0)
                ans[i] = 1;
            else
                ans[i] = 0;
        }
     
        for (i = 0; i < n; i++)
            Console.Write(ans[i] + " ");
    }
 
    // Driver code
    public static void Main () {
        // Numbers to be checked for reachability
    int []nums = { 9, 4 };
    int n =nums.Length;
    // Starting number K
    int k = 8;
 
    // Sizes of jumps d1 and d2
    int d1 = 3, d2 = 2;
 
    reachTheNums(nums, k, d1, d2, n);
    }
    // This code is contributed by Ryuga
}

<?php
// PHP implementation of the approach
// gcd function
function GCD($a, $b)
{
    if ($b == 0)
        return $a;
    return GCD($b, $a % $b);
}
 
// Function that returns the vector
// containing the result for the
// reachability of the required numbers
function reachTheNums($nums, $k, $d1,
                             $d2, $n)
{
    $i = 0; $ans = array(0, 0);
    $gcd = GCD($d1, $d2);
 
    for ($i = 0; $i < $n; $i++)
    {
        $x = $nums[$i] - $k;
 
        // if distance x is coverable
        if ($x % $gcd == 0)
            $ans[$i] = 1;
        else
            $ans[$i] = 0;
    }
 
    for ($i = 0; $i < $n; $i++)
    echo $ans[$i] . " ";
}
 
// Driver Code
 
// Numbers to be checked for reachability
$nums = array(9, 4);
$n = 2;
 
// Starting number $K
$k = 8;
 
// Sizes of jumps $d1 and $d2
$d1 = 3; $d2 = 2;
 
reachTheNums($nums, $k, $d1, $d2, $n);
     
// This code is contributed by Adesh Singh1
?>

<script>
// javascript implementation of the approach
 
    // Recursive function to return gcd of a and b
    function __gcd(a , b)
    {
     
        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
 
        // base case
        if (a == b)
            return a;
 
        // a is greater
        if (a > b)
            return __gcd(a - b, b);
        return __gcd(a, b - a);
    }
 
    // Function that returns the vector containing the
    // result for the reachability of the required numbers
    function reachTheNums(nums , k , d1 , d2 , n)
    {
        var i;
        var ans = Array(n).fill(0);
        var gcd = __gcd(d1, d2);
 
        for (let i = 0; i < n; i++)
        {
            var x = nums[i] - k;
 
            // If distance x is coverable
            if (x % gcd == 0)
                ans[i] = 1;
            else
                ans[i] = 0;
        }
 
        for (let i = 0; i < n; i++)
            document.write(ans[i] + " ");
    }
 
    // Driver code
     
    // Numbers to be checked for reachability
    var nums = [ 9, 4 ];
    var n = nums.length;
     
    // Starting number K
    var k = 8;
 
    // Sizes of jumps d1 and d2
    var d1 = 3, d2 = 2;
 
    reachTheNums(nums, k, d1, d2, n);
 
// This code is contributed by aashish1995.
</script>

1 1

Complejidad Temporal: O(N), ya que allí corre un bucle de 0 a (n – 1).
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.