GCD de todos los subarreglos de tamaño K

Dada una array , arr[] de tamaño N , la tarea es imprimir el MCD de todos los subarreglos de tamaño K.

Ejemplos:

Entrada: arr[] = {2, 4, 3, 9, 14, 20, 25, 17}, K = 2
Salida: 2 1 3 1 2 5 1
Explicación:
mcd(2, 4}) = 2
mcd(4 , 3) = 1
mcd(3, 9) = 3
mcd(9, 14) = 1
mcd(14, 20) = 2
mcd(20, 25) = 5
mcd(25, 17) = 1
Por lo tanto, la salida requerida es {2, 1, 3, 1, 2, 5, 1}

Entrada: arr[] = {2, 4, 8, 24, 14, 20, 25, 35, 7, 49, 7}, K = 3
Salida: 2 4 2 2 1 5 1 7 7

Enfoque: La idea es generar todos los subarreglos de tamaño K e imprimir el GCD de cada subarreglo . Para calcular eficientemente el GCD de cada subarreglo, la idea es usar la siguiente propiedad de GCD.

MCD(A ₁ , A ₂ , A ₃ , …, A _K ) = MCD(A ₁ , MCD(A ₂ , A ₃ , A ₄ , …., A _K ))

Siga los pasos a continuación para resolver el problema:

1. Inicialice una variable, digamos gcd , para almacenar el GCD del subarreglo actual.
2. Genere subarreglos de longitud K a partir del arreglo dado.
3. Aplicando la propiedad anterior de GCD, calcule el GCD de cada subarreglo e imprima el resultado obtenido.

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the gcd
// of each subarray of length K
void printSub(int arr[], int N,
              int K)
{
    for (int i = 0; i <= N - K; i++) {
 
        // Store GCD of subarray
        int gcd = arr[i];
 
        for (int j = i + 1; j < i + K;
             j++) {
 
            // Update GCD of subarray
            gcd = __gcd(gcd, arr[j]);
        }
 
        // Print GCD of subarray
        cout << gcd << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 4, 3, 9, 14,
                  20, 25, 17 };
    int K = 2;
    int N = sizeof(arr)
            / sizeof(arr[0]);
 
    printSub(arr, N, K);
}

// Java program to implement
// the above approach
class GFG{
 
static int __gcd(int a, int b)
{
  if (b == 0)
    return a;
  return __gcd(b, a % b);
}
   
// Function to print the gcd
// of each subarray of length K
static void printSub(int arr[],
                     int N, int K)
{
  for (int i = 0; i <= N - K; i++)
  {
    // Store GCD of subarray
    int gcd = arr[i];
 
    for (int j = i + 1; j < i + K; j++)
    {
      // Update GCD of subarray
      gcd = __gcd(gcd, arr[j]);
    }
 
    // Print GCD of subarray
    System.out.print(gcd + " ");
  }
}
 
// Driver Code
public static void main(String[] args)
{
  int arr[] = {2, 4, 3, 9,
               14, 20, 25, 17};
  int K = 2;
  int N = arr.length;
  printSub(arr, N, K);
}
}
 
// This code is contributed by Chitranayal

# Python3 program to implement
# the above approach
from math import gcd
 
# Function to print the gcd
# of each subarray of length K
def printSub(arr, N, K):
     
    for i in range(N - K + 1):
 
        # Store GCD of subarray
        g = arr[i]
 
        for j in range(i + 1, i + K):
             
            # Update GCD of subarray
            g = gcd(g, arr[j])
 
        # Print GCD of subarray
        print(g, end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 2, 4, 3, 9, 14,
            20, 25, 17 ]
    K = 2
    N = len(arr)
 
    printSub(arr, N, K)
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach
using System;
class GFG{
 
static int __gcd(int a, int b)
{
  if (b == 0)
    return a;
  return __gcd(b, a % b);
}
   
// Function to print the gcd
// of each subarray of length K
static void printSub(int []arr,
                     int N, int K)
{
  for (int i = 0; i <= N - K; i++)
  {
    // Store GCD of subarray
    int gcd = arr[i];
 
    for (int j = i + 1; j < i + K; j++)
    {
      // Update GCD of subarray
      gcd = __gcd(gcd, arr[j]);
    }
 
    // Print GCD of subarray
    Console.Write(gcd + " ");
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  int []arr = {2, 4, 3, 9,
               14, 20, 25, 17};
  int K = 2;
  int N = arr.Length;
  printSub(arr, N, K);
}
}
 
 
// This code is contributed by Princi Singh

<script>
 
// Javascript program to implement
// the above approach
   
function __gcd(a, b)
{
  if (b == 0)
    return a;
  return __gcd(b, a % b);
}
    
// Function to print the gcd
// of each subarray of length K
function prletSub(arr, N, K)
{
  for (let i = 0; i <= N - K; i++)
  {
    // Store GCD of subarray
    let gcd = arr[i];
  
    for (let j = i + 1; j < i + K; j++)
    {
      // Update GCD of subarray
      gcd = __gcd(gcd, arr[j]);
    }
  
    // Print GCD of subarray
    document.write(gcd + " ");
  }
}
 
 
// Driver Code
 
    let arr = [2, 4, 3, 9,
               14, 20, 25, 17];
  let K = 2;
  let N = arr.length;
  prletSub(arr, N, K);
 
// This code is contributed by avijitmondal1998.
</script>

2 1 3 1 2 5 1

Complejidad temporal: O((N – K + 1) * K)
Espacio auxiliar: O(1)