Subarreglo más largo con suma no divisible por X

Dado un arreglo arr[] y un entero X , la tarea es imprimir el subarreglo más largo de modo que la suma de sus elementos no sea divisible por X. Si no existe tal subarreglo, imprima «-1» . 
Nota: Si existe más de un subarreglo con la propiedad dada, imprima cualquiera de ellos.
Ejemplos: 
 

Entrada: array[] = {1, 2, 3} X = 3 
Salida: 2 3 
Explicación: 
El subarreglo {2, 3} tiene una suma de elementos 5 , que no es divisible por 3 .
Entrada: arr[] = {2, 6} X = 2 
Salida: -1 
Explicación: 
Todos los subarreglos posibles {1}, {2}, {1, 2} tienen una suma par. 
Por lo tanto, la respuesta es -1. 
 

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles y seguir calculando su suma. Si se encuentra que algún subarreglo tiene una suma no divisible por X , compare la longitud con la longitud máxima obtenida ( maxm ) y actualice maxm en consecuencia y actualice el índice inicial y el índice final del subarreglo. Finalmente, imprima el subarreglo que tiene los índices inicial y final almacenados. Si no existe tal subarreglo, imprima «-1» . 
Complejidad de Tiempo: O(N ² )  
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, encontraremos la suma de array de prefijos y sufijos . Siga los pasos a continuación: 

• Genere la array de suma de prefijos y la array de suma de sufijos .
• Iterar desde [0, N – 1] usando Two Pointers y elegir la suma de prefijos y sufijos del elemento en cada índice que no es divisible por X . Almacene el índice inicial y el índice final del subarreglo.
• Después de completar los pasos anteriores, si existe un subarreglo con una suma no divisible por X , entonces imprima el subarreglo con los índices inicial y final almacenados .
• Si no existe tal subarreglo, imprima «-1» .

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

#include <iostream>
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to print the longest
// subarray with sum of elements
// not divisible by X
void max_length(int N, int x,
                vector<int>& v)
{
    int i, a;
  
    // Pref[] stores the prefix sum
    // Suff[] stores the suffix sum
    vector<int> preff, suff;
    int ct = 0;
  
    for (i = 0; i < N; i++) {
  
        a = v[i];
  
        // If array element is
        // divisibile by x
        if (a % x == 0) {
  
            // Increase count
            ct += 1;
        }
    }
  
    // If all the array elements
    // are divisible by x
    if (ct == N) {
  
        // No subarray possible
        cout << -1 << endl;
        return;
    }
  
    // Reverse v to calculate the
    // suffix sum
    reverse(v.begin(), v.end());
  
    suff.push_back(v[0]);
  
    // Calculate the suffix sum
    for (i = 1; i < N; i++) {
        suff.push_back(v[i]
                       + suff[i - 1]);
    }
  
    // Reverse to original form
    reverse(v.begin(), v.end());
  
    // Reverse the suffix sum array
    reverse(suff.begin(), suff.end());
  
    preff.push_back(v[0]);
  
    // Calculate the prefix sum
    for (i = 1; i < N; i++) {
        preff.push_back(v[i]
                        + preff[i - 1]);
    }
  
    int ans = 0;
  
    // Stores the starting index
    // of required subarray
    int lp = 0;
  
    // Stores the ending index
    // of required subarray
    int rp = N - 1;
  
    for (i = 0; i < N; i++) {
  
        // If suffix sum till i-th
        // index is not divisible by x
        if (suff[i] % x != 0
            && (ans < (N - 1))) {
  
            lp = i;
            rp = N - 1;
  
            // Update the answer
            ans = max(ans, N - i);
        }
  
        // If prefix sum till i-th
        // index is not divisible by x
        if (preff[i] % x != 0
            && (ans < (i + 1))) {
  
            lp = 0;
            rp = i;
  
            // Update the answer
            ans = max(ans, i + 1);
        }
    }
  
    // Print the longest subarray
    for (i = lp; i <= rp; i++) {
        cout << v[i] << " ";
    }
}
  
// Driver Code
int main()
{
    int x = 3;
  
    vector<int> v = { 1, 3, 2, 6 };
    int N = v.size();
  
    max_length(N, x, v);
  
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
  
class GFG{
  
// Function to print the longest
// subarray with sum of elements
// not divisible by X
static void max_length(int N, int x,
                       int []v)
{
    int i, a;
  
    // Pref[] stores the prefix sum
    // Suff[] stores the suffix sum
    List<Integer> preff = new Vector<Integer>();
    List<Integer> suff = new Vector<Integer>();
      
    int ct = 0;
  
    for(i = 0; i < N; i++) 
    {
        a = v[i];
  
        // If array element is
        // divisibile by x
        if (a % x == 0)
        {
              
            // Increase count
            ct += 1;
        }
    }
  
    // If all the array elements
    // are divisible by x
    if (ct == N) 
    {
          
        // No subarray possible
        System.out.print(-1 + "\n");
        return;
    }
  
    // Reverse v to calculate the
    // suffix sum
    v = reverse(v);
  
    suff.add(v[0]);
  
    // Calculate the suffix sum
    for(i = 1; i < N; i++)
    {
        suff.add(v[i] + suff.get(i - 1));
    }
  
    // Reverse to original form
    v = reverse(v);
  
    // Reverse the suffix sum array
    Collections.reverse(suff);
  
    preff.add(v[0]);
  
    // Calculate the prefix sum
    for(i = 1; i < N; i++)
    {
        preff.add(v[i] + preff.get(i - 1));
    }
  
    int ans = 0;
  
    // Stores the starting index
    // of required subarray
    int lp = 0;
  
    // Stores the ending index
    // of required subarray
    int rp = N - 1;
  
    for(i = 0; i < N; i++)
    {
          
        // If suffix sum till i-th
        // index is not divisible by x
        if (suff.get(i) % x != 0 &&
           (ans < (N - 1))) 
        {
            lp = i;
            rp = N - 1;
  
            // Update the answer
            ans = Math.max(ans, N - i);
        }
  
        // If prefix sum till i-th
        // index is not divisible by x
        if (preff.get(i) % x != 0 &&
           (ans < (i + 1)))
        {
            lp = 0;
            rp = i;
  
            // Update the answer
            ans = Math.max(ans, i + 1);
        }
    }
  
    // Print the longest subarray
    for(i = lp; i <= rp; i++)
    {
        System.out.print(v[i] + " ");
    }
}
  
static int[] reverse(int a[]) 
{
    int i, n = a.length, t;
    for(i = 0; i < n / 2; i++)
    {
        t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
    return a;
}
  
// Driver Code
public static void main(String[] args)
{
    int x = 3;
    int []v = { 1, 3, 2, 6 };
    int N = v.length;
  
    max_length(N, x, v);
}
}
  
// This code is contributed by PrinciRaj1992

# Python3 program to implement 
# the above approach 
  
# Function to print the longest 
# subarray with sum of elements 
# not divisible by X 
def max_length(N, x, v):
      
    # Pref[] stores the prefix sum 
    # Suff[] stores the suffix sum 
    preff, suff = [], []
    ct = 0
      
    for i in range(N):
        a = v[i]
          
        # If array element is 
        # divisibile by x 
        if a % x == 0:
              
            # Increase count 
            ct += 1
              
    # If all the array elements 
    # are divisible by x 
    if ct == N:
          
        # No subarray possible 
        print(-1)
        return
      
    # Reverse v to calculate the 
    # suffix sum 
    v.reverse()
      
    suff.append(v[0])
      
    # Calculate the suffix sum 
    for i in range(1, N):
        suff.append(v[i] + suff[i - 1])
          
    # Reverse to original form 
    v.reverse()
      
    # Reverse the suffix sum array
    suff.reverse()
      
    preff.append(v[0])
      
    # Calculate the prefix sum
    for i in range(1, N):
        preff.append(v[i] + preff[i - 1])
          
    ans = 0
      
    # Stores the starting index 
    # of required subarray 
    lp = 0
      
    # Stores the ending index 
    # of required subarray 
    rp = N - 1
      
    for i in range(N):
          
        # If suffix sum till i-th 
        # index is not divisible by x 
        if suff[i] % x != 0 and ans < N - 1:
            lp = i
            rp = N - 1
              
            # Update the answer
            ans = max(ans, N - i)
              
        # If prefix sum till i-th 
        # index is not divisible by x 
        if preff[i] % x != 0 and ans < i + 1:
            lp = 0
            rp = i
              
            # Update the answer
            ans = max(ans, i + 1)
              
    # Print the longest subarray
    for i in range(lp, rp + 1):
        print(v[i], end = " ")
          
# Driver code
x = 3
v = [ 1, 3, 2, 6 ]
N = len(v)
  
max_length(N, x, v)
  
# This code is contributed by Stuti Pathak

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
  
class GFG{
  
// Function to print the longest
// subarray with sum of elements
// not divisible by X
static void max_length(int N, int x,
                       int []v)
{
    int i, a;
  
    // Pref[] stores the prefix sum
    // Suff[] stores the suffix sum
    List<int> preff = new List<int>();
    List<int> suff = new List<int>();
      
    int ct = 0;
  
    for(i = 0; i < N; i++) 
    {
        a = v[i];
  
        // If array element is
        // divisibile by x
        if (a % x == 0)
        {
              
            // Increase count
            ct += 1;
        }
    }
  
    // If all the array elements
    // are divisible by x
    if (ct == N) 
    {
          
        // No subarray possible
        Console.Write(-1 + "\n");
        return;
    }
  
    // Reverse v to calculate the
    // suffix sum
    v = reverse(v);
  
    suff.Add(v[0]);
  
    // Calculate the suffix sum
    for(i = 1; i < N; i++)
    {
        suff.Add(v[i] + suff[i - 1]);
    }
  
    // Reverse to original form
    v = reverse(v);
  
    // Reverse the suffix sum array
    suff.Reverse();
  
    preff.Add(v[0]);
  
    // Calculate the prefix sum
    for(i = 1; i < N; i++)
    {
        preff.Add(v[i] + preff[i - 1]);
    }
  
    int ans = 0;
  
    // Stores the starting index
    // of required subarray
    int lp = 0;
  
    // Stores the ending index
    // of required subarray
    int rp = N - 1;
  
    for(i = 0; i < N; i++)
    {
          
        // If suffix sum till i-th
        // index is not divisible by x
        if (suff[i] % x != 0 &&
               (ans < (N - 1))) 
        {
            lp = i;
            rp = N - 1;
  
            // Update the answer
            ans = Math.Max(ans, N - i);
        }
  
        // If prefix sum till i-th
        // index is not divisible by x
        if (preff[i] % x != 0 &&
                (ans < (i + 1)))
        {
            lp = 0;
            rp = i;
  
            // Update the answer
            ans = Math.Max(ans, i + 1);
        }
    }
  
    // Print the longest subarray
    for(i = lp; i <= rp; i++)
    {
        Console.Write(v[i] + " ");
    }
}
  
static int[] reverse(int []a) 
{
    int i, n = a.Length, t;
    for(i = 0; i < n / 2; i++)
    {
        t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
    return a;
}
  
// Driver Code
public static void Main(String[] args)
{
    int x = 3;
    int []v = { 1, 3, 2, 6 };
    int N = v.Length;
  
    max_length(N, x, v);
}
}
  
// This code is contributed by PrinciRaj1992

3 2 6

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