Dado un arreglo de enteros arr[] y un entero positivo K , la tarea es encontrar el conteo de los subarreglos más largos posibles con la suma de sus elementos no divisible por K .
Ejemplos:
Entrada: arr[] = {2, 3, 4, 6}, K = 3
Salida: 1
Explicación: Solo hay un subarreglo más largo posible de tamaño 3, es decir, {3, 4, 6} que tiene una suma de 13, que no es divisible por K = 3.Entrada: arr[] = {2, 4, 3, 5, 1}, K = 3
Salida: 2
Explicación: Hay 2 subarreglos más largos posibles de tamaño 4, es decir, {2, 4, 3, 5} y {4, 3 , 5, 1} que suman 14 y 13 respectivamente, que no es divisible por K = 3.
Acercarse:
- Comprueba si la suma de todos los elementos de la array es divisible por K
- Si la suma no es divisible por K, devuelva 1 ya que el subarreglo más largo sería de tamaño N.
- Más
- Encuentre el índice del primer número no divisible por K. Sea L .
- Encuentre el índice del último número que no es divisible por K. Sea R .
- Retire los elementos hasta el índice L y encuentre el tamaño del subarreglo. Elimine los elementos más allá de R y encuentre también el tamaño de este subarreglo. Cualquiera que sea la longitud mayor, ese será el tamaño del subarreglo más largo no divisible por K.
- Usando esta longitud como el tamaño de la ventana, aplique la técnica de la ventana deslizante en el arr[] para averiguar el número de subarreglos del tamaño obtenido arriba que no son divisibles por K.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above problem
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of
// longest subarrays with sum not
// divisible by K
int CountLongestSubarrays(
int arr[], int n, int k)
{
// Sum of all elements in
// an array
int i, s = 0;
for (i = 0; i < n; ++i) {
s += arr[i];
}
// If overall sum is not
// divisible then return
// 1, as only one subarray
// of size n is possible
if (s % k) {
return 1;
}
else {
int ini = 0;
// Index of the first number
// not divisible by K
while (ini < n
&& arr[ini] % k == 0) {
++ini;
}
int final = n - 1;
// Index of the last number
// not divisible by K
while (final >= 0
&& arr[final] % k == 0) {
--final;
}
int len, sum = 0, count = 0;
// Subarray doesn't exist
if (ini == n) {
return -1;
}
else {
len = max(n - 1 - ini,
final);
}
// Sum of the window
for (i = 0; i < len; i++) {
sum += arr[i];
}
if (sum % k != 0) {
count++;
}
// Calculate the sum of rest of
// the windows of size len
for (i = len; i < n; i++) {
sum = sum + arr[i];
sum = sum - arr[i - len];
if (sum % k != 0) {
count++;
}
}
return count;
}
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 2, 2, 3 };
int n = sizeof(arr)
/ sizeof(arr[0]);
int k = 3;
cout << CountLongestSubarrays(arr, n, k);
return 0;
}
Java
// Java program for the above problem
import java.util.*;
class GFG{
// Function to find the count of
// longest subarrays with sum not
// divisible by K
static int CountLongestSubarrays(int arr[],
int n, int k)
{
// Sum of all elements in
// an array
int i, s = 0;
for(i = 0; i < n; ++i)
{
s += arr[i];
}
// If overall sum is not
// divisible then return
// 1, as only one subarray
// of size n is possible
if ((s % k) != 0)
{
return 1;
}
else
{
int ini = 0;
// Index of the first number
// not divisible by K
while (ini < n && arr[ini] % k == 0)
{
++ini;
}
int fin = n - 1;
// Index of the last number
// not divisible by K
while (fin >= 0 && arr[fin] % k == 0)
{
--fin;
}
int len, sum = 0, count = 0;
// Subarray doesn't exist
if (ini == n)
{
return -1;
}
else
{
len = Math.max(n - 1 - ini, fin);
}
// Sum of the window
for(i = 0; i < len; i++)
{
sum += arr[i];
}
if (sum % k != 0)
{
count++;
}
// Calculate the sum of rest of
// the windows of size len
for(i = len; i < n; i++)
{
sum = sum + arr[i];
sum = sum - arr[i - len];
if (sum % k != 0)
{
count++;
}
}
return count;
}
}
// Driver Code
public static void main (String []args)
{
int arr[] = { 3, 2, 2, 2, 3 };
int n = arr.length;
int k = 3;
System.out.print(CountLongestSubarrays(
arr, n, k));
}
}
// This code is contributed by chitranayal
Python3
# Python3 program for the above problem # Function to find the count of # longest subarrays with sum not # divisible by K def CountLongestSubarrays(arr, n, k): # Sum of all elements in # an array s = 0 for i in range(n): s += arr[i] # If overall sum is not # divisible then return # 1, as only one subarray # of size n is possible if(s % k): return 1 else: ini = 0 # Index of the first number # not divisible by K while (ini < n and arr[ini] % k == 0): ini += 1 final = n - 1 # Index of the last number # not divisible by K while (final >= 0 and arr[final] % k == 0): final -= 1 sum, count = 0, 0 # Subarray doesn't exist if(ini == n): return -1 else: length = max(n - 1 - ini, final) # Sum of the window for i in range(length): sum += arr[i] if(sum % k != 0): count += 1 # Calculate the sum of rest of # the windows of size len for i in range(length, n): sum = sum + arr[i] sum = sum + arr[i - length] if (sum % k != 0): count += 1 return count # Driver Code if __name__ == '__main__': arr = [ 3, 2, 2, 2, 3 ] n = len(arr) k = 3 print(CountLongestSubarrays(arr, n, k)) # This code is contributed by Shivam Singh
C#
// C# program for the above problem
using System;
class GFG{
// Function to find the count of
// longest subarrays with sum not
// divisible by K
static int CountLongestSubarrays(int[] arr,
int n, int k)
{
// Sum of all elements in
// an array
int i, s = 0;
for(i = 0; i < n; ++i)
{
s += arr[i];
}
// If overall sum is not
// divisible then return
// 1, as only one subarray
// of size n is possible
if ((s % k) != 0)
{
return 1;
}
else
{
int ini = 0;
// Index of the first number
// not divisible by K
while (ini < n && arr[ini] % k == 0)
{
++ini;
}
int fin = n - 1;
// Index of the last number
// not divisible by K
while (fin >= 0 && arr[fin] % k == 0)
{
--fin;
}
int len, sum = 0, count = 0;
// Subarray doesn't exist
if (ini == n)
{
return -1;
}
else
{
len = Math.Max(n - 1 - ini, fin);
}
// Sum of the window
for(i = 0; i < len; i++)
{
sum += arr[i];
}
if (sum % k != 0)
{
count++;
}
// Calculate the sum of rest of
// the windows of size len
for(i = len; i < n; i++)
{
sum = sum + arr[i];
sum = sum - arr[i - len];
if (sum % k != 0)
{
count++;
}
}
return count;
}
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 3, 2, 2, 2, 3 };
int n = arr.Length;
int k = 3;
Console.WriteLine(CountLongestSubarrays(
arr, n, k));
}
}
// This code is contributed by jrishabh99
Javascript
<script>
// JavaScript program for the above problem
// Function to find the count of
// longest subarrays with sum not
// divisible by K
function CountLongestSubarrays(arr, n, k)
{
// Sum of all elements in
// an array
let i, s = 0;
for(i = 0; i < n; ++i)
{
s += arr[i];
}
// If overall sum is not
// divisible then return
// 1, as only one subarray
// of size n is possible
if ((s % k) != 0)
{
return 1;
}
else
{
let ini = 0;
// Index of the first number
// not divisible by K
while (ini < n && arr[ini] % k == 0)
{
++ini;
}
let fin = n - 1;
// Index of the last number
// not divisible by K
while (fin >= 0 && arr[fin] % k == 0)
{
--fin;
}
let len, sum = 0, count = 0;
// Subarray doesn't exist
if (ini == n)
{
return -1;
}
else
{
len = Math.max(n - 1 - ini, fin);
}
// Sum of the window
for(i = 0; i < len; i++)
{
sum += arr[i];
}
if (sum % k != 0)
{
count++;
}
// Calculate the sum of rest of
// the windows of size len
for(i = len; i < n; i++)
{
sum = sum + arr[i];
sum = sum - arr[i - len];
if (sum % k != 0)
{
count++;
}
}
return count;
}
}
// Driver Code
let arr = [ 3, 2, 2, 2, 3 ];
let n = arr.length;
let k = 3;
document.write(CountLongestSubarrays(
arr, n, k));
// This code is contributed by sanjoy_62
</script>
Producción:
2
Complejidad de Tiempo: O(N)
Complejidad de Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mayur_patil y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA