Consultas para encontrar la longitud del prefijo más largo de una array dada que tiene todos los elementos divisibles por K

Dada una array arr[] que consta de N elementos y una array Q[] , la tarea de cada consulta es encontrar la longitud del prefijo más largo de modo que todos los elementos de este prefijo sean divisibles por K .

Ejemplos:

Entrada: arr[] = {12, 6, 15, 3, 10}, Q[] = {4, 3, 2}
Salida: 1 4 2
Explicación:

• Q[0] = 4: arr[0] (= 12) es divisible por 4 . arr[1] no es divisible por 4 . Por lo tanto, la longitud del prefijo más largo divisible por 4 es 1.
• Q[1] = 3: El prefijo más largo que es divisible por 3 es {12, 6, 15, 3}. Por lo tanto, imprima 4 como la salida requerida.
• Q[2] = 2: El prefijo más largo que es divisible por 2 es {12, 6}.

Entrada: arr[] = {4, 3, 2, 1}, Q[] = {1, 2, 3}
Salida: 4 1 0

Enfoque: La idea es observar que si los primeros i elementos del arreglo son divisibles por el entero K dado , entonces su GCD también será divisible por K. Siga los pasos a continuación para resolver el problema:

1. Antes de encontrar la respuesta a cada consulta, precalcule el mcd de los prefijos del arreglo en otro arreglo g[] tal que g[0] = arr[0] y para el resto de los elementos g[i] = GCD( arr[i], g[i – 1]) .
2. Luego, para cada elemento en la array Q[] , realice una búsqueda binaria en la array g[] y encuentre el último índice de g[] que es divisible por Q[i] .
3. Cabe señalar que todos los elementos de este índice serán divisibles por K , ya que el mcd de todos los elementos hasta este índice es divisible por K.
4. Imprime la longitud del prefijo más largo.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find index of the last
// element which is divisible the given element
int binSearch(int* g, int st, int en, int val)
{
    // Initially assume the
    // index to be -1
    int ind = -1;
    while (st <= en) {
 
        // Find the mid element
        // of the subarray
        int mid = st + (en - st) / 2;
 
        // If the mid element is divisible by
        // given element, then move to right
        // of mid and update ind to mid
        if (g[mid] % val == 0) {
            ind = mid;
            st = mid + 1;
        }
 
        // Otherwise, move to left of mid
        else {
            en = mid - 1;
        }
    }
 
    // Return the length of prefix
    return ind + 1;
}
 
// Function to compute and print for each query
void solveQueries(int* arr, int* queries,
                  int n, int q)
{
    int g[n];
 
    // Pre compute the gcd of the prefixes
    // of the input array in the array g[]
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            g[i] = arr[i];
        }
        else {
            g[i] = __gcd(g[i - 1], arr[i]);
        }
    }
 
    // Perform binary search
    // for each query
    for (int i = 0; i < q; i++) {
        cout << binSearch(g, 0, n - 1,
                          queries[i])
             << " ";
    }
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 12, 6, 15, 3, 10 };
 
    // Size of array
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Given Queries
    int queries[] = { 4, 3, 2 };
 
    // Size of queries
    int q = sizeof(queries) / sizeof(queries[0]);
 
    solveQueries(arr, queries, n, q);
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to find index of the last
// element which is divisible the given element
static int binSearch(int[] g, int st, int en, int val)
{
   
    // Initially assume the
    // index to be -1
    int ind = -1;
    while (st <= en)
    {
 
        // Find the mid element
        // of the subarray
        int mid = st + (en - st) / 2;
 
        // If the mid element is divisible by
        // given element, then move to right
        // of mid and update ind to mid
        if (g[mid] % val == 0)
        {
            ind = mid;
            st = mid + 1;
        }
 
        // Otherwise, move to left of mid
        else
        {
            en = mid - 1;
        }
    }
 
    // Return the length of prefix
    return ind + 1;
}
 
// Function to compute and print for each query
static void solveQueries(int []arr, int []queries,
                  int n, int q)
{
    int []g = new int[n];
 
    // Pre compute the gcd of the prefixes
    // of the input array in the array g[]
    for (int i = 0; i < n; i++)
    {
        if (i == 0) {
            g[i] = arr[i];
        }
        else {
            g[i] = __gcd(g[i - 1], arr[i]);
        }
    }
 
    // Perform binary search
    // for each query
    for (int i = 0; i < q; i++)
    {
        System.out.print(binSearch(g, 0, n - 1,
                          queries[i])
            + " ");
    }
}
static int __gcd(int a, int b) 
{ 
    return b == 0? a:__gcd(b, a % b);    
}
   
// Driver Code
public static void main(String[] args)
{
   
    // Given array
    int arr[] = { 12, 6, 15, 3, 10 };
 
    // Size of array
    int n = arr.length;
 
    // Given Queries
    int queries[] = { 4, 3, 2 };
 
    // Size of queries
    int q = queries.length;
    solveQueries(arr, queries, n, q);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program for the above approach
from math import gcd as __gcd
 
# Function to find index of the last
# element which is divisible the
# given element
def binSearch(g, st, en, val):
     
    # Initially assume the
    # index to be -1
    ind = -1
     
    while (st <= en):
 
        # Find the mid element
        # of the subarray
        mid = st + (en - st) // 2
 
        # If the mid element is divisible by
        # given element, then move to right
        # of mid and update ind to mid
        if (g[mid] % val == 0):
            ind = mid
            st = mid + 1
 
        # Otherwise, move to left of mid
        else:
            en = mid - 1
 
    # Return the length of prefix
    return ind + 1
 
# Function to compute and print for each query
def solveQueries(arr, queries, n, q):
     
    g = [0 for i in range(n)]
 
    # Pre compute the gcd of the prefixes
    # of the input array in the array g[]
    for i in range(n):
        if (i == 0):
            g[i] = arr[i]
        else:
            g[i] = __gcd(g[i - 1], arr[i])
 
    # Perform binary search
    # for each query
    for i in range(q):
        print(binSearch(g, 0, n - 1,
                        queries[i]), end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    # Given array
    arr = [ 12, 6, 15, 3, 10 ]
 
    # Size of array
    n = len(arr)
 
    # Given Queries
    queries = [ 4, 3, 2 ]
 
    # Size of queries
    q = len(queries)
 
    solveQueries(arr, queries, n, q)
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach 
using System;
class GFG
{
  
// Function to find index of the last
// element which is divisible the given element
static int binSearch(int[] g, int st, int en, int val)
{
   
  // Initially assume the
  // index to be -1
  int ind = -1;
  while (st <= en)
  {
 
    // Find the mid element
    // of the subarray
    int mid = st + (en - st) / 2;
 
    // If the mid element is divisible by
    // given element, then move to right
    // of mid and update ind to mid
    if (g[mid] % val == 0)
    {
      ind = mid;
      st = mid + 1;
    }
 
    // Otherwise, move to left of mid
    else
    {
      en = mid - 1;
    }
  }
 
  // Return the length of prefix
  return ind + 1;
}
 
  // 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 to compute and print for each query
  static void solveQueries(int[] arr, int[] queries,
                           int n, int q)
  {
    int[] g = new int[n];
 
    // Pre compute the gcd of the prefixes
    // of the input array in the array g[]
    for (int i = 0; i < n; i++)
    {
      if (i == 0)
      {
        g[i] = arr[i];
      }
      else
      {
        g[i] = gcd(g[i - 1], arr[i]);
      }
    }
 
    // Perform binary search
    // for each query
    for (int i = 0; i < q; i++)
    {
      Console.Write(binSearch(g, 0, n - 1,
                              queries[i]) + " ");
    }
  }
  
// Driver code
public static void Main()
{
   
    // Given array
    int[] arr = { 12, 6, 15, 3, 10 };
  
    // Size of array
    int n = arr.Length;
  
    // Given Queries
    int[] queries = { 4, 3, 2 };
  
    // Size of queries
    int q = queries.Length;
    solveQueries(arr, queries, n, q);
}
}
 
// This code is contributed by susmitakundugoaldanga

<script>
//Javascript program for the above approach
 
//function for GCD
function __gcd( a, b) 
{ 
    return b == 0? a:__gcd(b, a % b);    
}
 
// Function to find index of the last
// element which is divisible the given element
function binSearch(g, st, en, val)
{
    // Initially assume the
    // index to be -1
    var ind = -1;
    while (st <= en) {
 
        // Find the mid element
        // of the subarray
        var mid = st + parseInt((en - st) / 2);
 
        // If the mid element is divisible by
        // given element, then move to right
        // of mid and update ind to mid
        if (g[mid] % val == 0) {
            ind = mid;
            st = mid + 1;
        }
 
        // Otherwise, move to left of mid
        else {
            en = mid - 1;
        }
    }
 
    // Return the length of prefix
    return ind + 1;
}
 
// Function to compute and print for each query
function solveQueries(arr, queries, n, q)
{
    var g = new Array(n);
 
    // Pre compute the gcd of the prefixes
    // of the input array in the array g[]
    for (var i = 0; i < n; i++) {
        if (i == 0) {
            g[i] = arr[i];
        }
        else {
            g[i] = __gcd(g[i - 1], arr[i]);
        }
    }
 
    // Perform binary search
    // for each query
    for (var i = 0; i < q; i++) {
        document.write( binSearch(g, 0, n - 1, queries[i]) + " ");
    }
}
 
var arr = [ 12, 6, 15, 3, 10 ];
 
// Size of array
var n = arr.length;
// Given Queries
var queries = [ 4, 3, 2 ];
// Size of queries
var q = queries.length;
solveQueries(arr, queries, n, q);
 
//This code is contributed by SoumikMondal
</script>

1 4 2

Complejidad de Tiempo: O(NlogN + QlogN)
Espacio Auxiliar: O(N)