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 2 )
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:
C++
#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
// 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
# 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#
// 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
Producción:
3 2 6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por RishavSinghMehta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA