Subconjuntos de tamaño K con producto igual a la diferencia de dos cuadrados perfectos

Dada una array distinta de enteros arr[] de tamaño N y un entero K , la tarea es contar el número de subconjuntos de tamaño K de la array cuyo producto de elementos se puede representar como a ² – b ² . Ejemplos:

Entrada: arr[] = {1, 2, 3} K = 2 Salida: 2 Explicación: Todos los subconjuntos posibles de longitud 2 con sus productos se dan a continuación: {1, 2} = 2 {2, 3} = 6 {1 , 3} = 3 Dado que solo 3 se puede expresar como (2 ² – 1 ² , por lo tanto, solo existe uno de esos subconjuntos. Entrada: arr[] = {2, 5, 6} K = 2 Salida: 2 Explicación: Todas las posibles subsecuencias contiguas con sus productos dados a continuación: {2, 5} = 10 {2, 6} = 12 {5, 6} = 30 Dado que solo 12 se puede expresar como (4 ² – 2 ² ), solo uno de esos subconjunto existe.

Acercarse:

1. Genere todos los subconjuntos de tamaño K .
2. Calcular los productos de todos los subconjuntos .
3. Un número puede representarse como la diferencia de cuadrados de dos números solo si es impar o divisible por 4 .
4. Por lo tanto, cuente todos los subconjuntos con un producto que satisfaga esta condición.

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

# Python3 implementation of the approach
 
import itertools
 
# Function to return the
# Count of required sub-sequences
def count_seq(arr, n, k):
 
    # ans is Count variable
    ans = 0
 
    for seq in itertools.combinations(arr, k):
 
        # product of seq
        pro = 1
     
        for ele in seq:
            pro *= ele
     
        # checking form of a2-b2
        if ((pro % 4) != 2):
            ans += 1
    return ans
 
# Driver code
if __name__ == "__main__":
    arr = [2, 5, 6]
    n = len(arr)
    k = 2
    print(count_seq(arr, n, k))

1