Recuento de subarreglos de tamaño K que tienen al menos un par con diferencia absoluta divisible por K-1

Dado un arr[] que consta de N elementos, la tarea es contar todos los subarreglos de tamaño K que tengan al menos un par cuya diferencia absoluta sea divisible por K – 1 .
Ejemplos: 
 

Entrada: arr[] = {1, 5, 3, 2, 17, 18}, K = 4 
Salida: 3 
Explicación: 
Los tres subarreglos de tamaño 4 son: 
{1, 5, 3, 2}: par {5, 2} tienen diferencia divisible por 3 
{5, 3, 2, 17}: Pares {5, 2}, {5, 17}, {2, 17} tienen diferencia divisible por 3 
{3, 2, 17, 18}: Los pares {3, 18}, {2, 17} tienen diferencia divisible por 3 
Entrada: arr[] = {1, 2, 3, 4, 5}, K = 5 
Salida: 1 
Explicación: 
{1, 2, 3, 4, 5}: el par {1, 5} es divisible por 4 
 

Enfoque ingenuo: 
el enfoque más simple para resolver el problema es iterar sobre todos los subarreglos de tamaño K y verificar si existe algún par cuya diferencia sea divisible por K – 1 . 
Complejidad de tiempo: O(N * K * K)
Enfoque eficiente: El enfoque anterior se puede optimizar utilizando el principio Pigeonhole . Siga los pasos a continuación para resolver el problema: 
 

• Considere cajas K-1 etiquetadas 0, 1, 2, …, K-2 respectivamente. Representan los restos cuando cualquier número x de la array se divide por K-1 , lo que significa que las cajas almacenan el módulo K-1 de los elementos de la array. 
   
• Ahora, en un subarreglo de tamaño K , de acuerdo con el Principio de Pigeonhole , debe haber al menos un par de cajas con los mismos residuos. Significa que hay al menos un par cuya diferencia o incluso la suma será divisible por K . 
   
• De este teorema podemos concluir que todo subarreglo de tamaño K , siempre tendrá al menos un par cuya diferencia es divisible por K-1 . 
   
• Entonces, la respuesta será igual al número de subarreglos de tamaño K posibles del arreglo dado, que es igual a N – K + 1 . 
   

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

// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the required
// number of subarrays
int findSubarrays(int arr[],
                  int N,
                  int K)
{
    // Return number of possible
    // subarrays of length K
    return N - K + 1;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 5, 3, 2, 17, 18 };
    int K = 4;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << findSubarrays(arr, N, K);
 
    return 0;
}

// Java implementation of the
// above approach
class GFG{
 
// Function to return the required
// number of subarrays
static int findSubarrays(int arr[], int N,
                                    int K)
{
     
    // Return number of possible
    // subarrays of length K
    return N - K + 1;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 5, 3, 2, 17, 18 };
    int K = 4;
    int N = arr.length;
 
    System.out.print(findSubarrays(arr, N, K));
}
}
 
// This code is contributed by shivanisinghss2110

# Python3 implementation of the
# above approach
 
# Function to return the required
# number of subarrays
def findSubarrays(arr, N, K):
     
    # Return number of possible
    # subarrays of length K
    return N - K + 1;
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 5, 3, 2, 17, 18 ];
    K = 4;
    N = len(arr);
 
    print(findSubarrays(arr, N, K));
 
# This code is contributed by Rohit_ranjan

// C# implementation of the
// above approach
using System;
 
class GFG{
 
// Function to return the required
// number of subarrays
static int findSubarrays(int []arr, int N,
                                    int K)
{
     
    // Return number of possible
    // subarrays of length K
    return N - K + 1;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 5, 3, 2, 17, 18 };
    int K = 4;
    int N = arr.Length;
 
    Console.Write(findSubarrays(arr, N, K));
}
}
 
// This code is contributed by Amit Katiyar

<script>
// Javascript implementation for the above approach
 
// Function to return the required
// number of subarrays
function findSubarrays(arr, N, K)
{
     
    // Return number of possible
    // subarrays of length K
    return N - K + 1;
}
 
    // Driver Code
     
    let arr = [ 1, 5, 3, 2, 17, 18 ];
    let K = 4;
    let N = arr.length;
 
    document.write(findSubarrays(arr, N, K));
 
</script>

3

Complejidad temporal: O(1) 
Espacio auxiliar: O(1)