Dado un arreglo arr[] , de tamaño N y un entero positivo K , la tarea es encontrar un subarreglo de tamaño K cuyos elementos se puedan usar para generar un número que sea divisible por 3. Si no existe tal subarreglo, imprima – 1 .
Ejemplos:
Entrada: arr[] = {84, 23, 45, 12 56, 82}, K = 3
Salida: 12, 56, 82
Explicación:
El número formado por el subarreglo {12, 56, 82} es 125682, que es divisible por 3.Entrada: arr[] = {84, 23, 45, 14 56, 82}, K = 3
Salida: -1
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles de tamaño K a partir del arreglo dado y, para cada subarreglo, verificar si el número formado por ese subarreglo es divisible por 3 o no.
Complejidad temporal: O(N * K)
Espacio auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en la siguiente observación:
Un número es divisible por 3 si y solo si la suma de los dígitos del número es divisible por 3.
Siga los pasos a continuación para resolver el problema:
- Almacene la suma de los primeros K elementos de la array en una variable, digamos sum .
- Atraviesa los elementos restantes de la array.
- Usando la técnica de la ventana deslizante , reste el primer elemento del subarreglo de la suma y agregue el siguiente elemento del arreglo al subarreglo.
- En cada paso, comprueba si la suma es divisible por 3 o no.
- Si se encuentra que es cierto, imprima el subarreglo de tamaño K actual .
- Si no se encuentra tal subarreglo, imprima -1.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// K size subarray
void findSubArray(vector<int> arr, int k)
{
pair<int, int> ans;
int i, sum = 0;
// Check if the first K elements
// forms a number which is
// divisible by 3
for (i = 0; i < k; i++) {
sum += arr[i];
}
int found = 0;
if (sum % 3 == 0) {
ans = make_pair(0, i - 1);
found = 1;
}
// Using Sliding window technique
for (int j = i; j < arr.size(); j++) {
if (found == 1)
break;
// Calculate sum of next K
// size subarray
sum = sum + arr[j] - arr[j - k];
// Check if sum is divisible by 3
if (sum % 3 == 0) {
// Update the indices of
// the subarray
ans = make_pair(j - k + 1, j);
found = 1;
}
}
// If no such subarray is found
if (found == 0)
ans = make_pair(-1, 0);
if (ans.first == -1) {
cout << -1;
}
else {
// Print the subarray
for (i = ans.first; i <= ans.second;
i++) {
cout << arr[i] << " ";
}
}
}
// Driver's code
int main()
{
// Given array and K
vector<int> arr = { 84, 23, 45,
12, 56, 82 };
int K = 3;
// Function Call
findSubArray(arr, K);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
import java.awt.Point;
class GFG{
// Function to find the
// K size subarray
public static void findSubArray(Vector<Integer> arr,
int k)
{
Point ans = new Point(0, 0);
int i, sum = 0;
// Check if the first K elements
// forms a number which is
// divisible by 3
for(i = 0; i < k; i++)
{
sum += arr.get(i);
}
int found = 0;
if (sum % 3 == 0)
{
ans = new Point(0, i - 1);
found = 1;
}
// Using Sliding window technique
for(int j = i; j < arr.size(); j++)
{
if (found == 1)
break;
// Calculate sum of next K
// size subarray
sum = sum + arr.get(j) - arr.get(j - k);
// Check if sum is divisible by 3
if (sum % 3 == 0)
{
// Update the indices of
// the subarray
ans = new Point(j - k + 1, j);
found = 1;
}
}
// If no such subarray is found
if (found == 0)
ans = new Point(-1, 0);
if (ans.x == -1)
{
System.out.print(-1);
}
else
{
// Print the subarray
for(i = ans.x; i <= ans.y; i++)
{
System.out.print(arr.get(i) + " ");
}
}
}
// Driver code
public static void main(String[] args)
{
// Given array and K
Vector<Integer> arr = new Vector<Integer>();
arr.add(84);
arr.add(23);
arr.add(45);
arr.add(12);
arr.add(56);
arr.add(82);
int K = 3;
// Function call
findSubArray(arr, K);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation of the # above approach # Function to find the # K size subarray def findSubArray(arr, k): ans = [(0, 0)] sm = 0 i = 0 found = 0 # Check if the first K elements # forms a number which is # divisible by 3 while (i < k): sm += arr[i] i += 1 if (sm % 3 == 0): ans = [(0, i - 1)] found = 1 # Using Sliding window technique for j in range(i, len(arr), 1): if (found == 1): break # Calculate sum of next K # size subarray sm = sm + arr[j] - arr[j - k] # Check if sum is divisible by 3 if (sm % 3 == 0): # Update the indices of # the subarray ans = [(j - k + 1, j)] found = 1 # If no such subarray is found if (found == 0): ans = [(-1, 0)] if (ans[0][0] == -1): print(-1) else: # Print the subarray for i in range(ans[0][0], ans[0][1] + 1, 1): print(arr[i], end = " ") # Driver code if __name__ == '__main__': # Given array and K arr = [ 84, 23, 45, 12, 56, 82 ] K = 3 # Function call findSubArray(arr, K) # This code is contributed by SURENDRA_GANGWAR
C#
// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
class GFG{
class Point
{
public int x, y;
public Point(int first,
int second)
{
this.x = first;
this.y = second;
}
}
// Function to find the
// K size subarray
public static void findSubArray(List<int> arr,
int k)
{
Point ans = new Point(0, 0);
int i, sum = 0;
// Check if the first K elements
// forms a number which is
// divisible by 3
for(i = 0; i < k; i++)
{
sum += arr[i];
}
int found = 0;
if (sum % 3 == 0)
{
ans = new Point(0, i - 1);
found = 1;
}
// Using Sliding window technique
for(int j = i; j < arr.Count; j++)
{
if (found == 1)
break;
// Calculate sum of next K
// size subarray
sum = sum + arr[j] -
arr[j - k];
// Check if sum is
// divisible by 3
if (sum % 3 == 0)
{
// Update the indices of
// the subarray
ans = new Point(j - k + 1, j);
found = 1;
}
}
// If no such subarray is found
if (found == 0)
ans = new Point(-1, 0);
if (ans.x == -1)
{
Console.Write(-1);
}
else
{
// Print the subarray
for(i = ans.x; i <= ans.y; i++)
{
Console.Write(arr[i] + " ");
}
}
}
// Driver code
public static void Main(String[] args)
{
// Given array and K
List<int> arr = new List<int>();
arr.Add(84);
arr.Add(23);
arr.Add(45);
arr.Add(12);
arr.Add(56);
arr.Add(82);
int K = 3;
// Function call
findSubArray(arr, K);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the above approach
// Function to find the
// K size subarray
function findSubArray(arr, k)
{
var ans = [];
var i, sum = 0;
// Check if the first K elements
// forms a number which is
// divisible by 3
for(i = 0; i < k; i++)
{
sum += arr[i];
}
var found = 0;
if (sum % 3 == 0)
{
ans = [0, i - 1];
found = 1;
}
// Using Sliding window technique
for(var j = i; j < arr.length; j++)
{
if (found == 1)
break;
// Calculate sum of next K
// size subarray
sum = sum + arr[j] - arr[j - k];
// Check if sum is divisible by 3
if (sum % 3 == 0)
{
// Update the indices of
// the subarray
ans = [j - k + 1, j];
found = 1;
}
}
// If no such subarray is found
if (found == 0)
ans = [-1, 0];
if (ans.first == -1)
{
cout << -1;
}
else
{
// Print the subarray
for(i = ans[0]; i <= ans[1]; i++)
{
document.write( arr[i] + " ");
}
}
}
// Driver code
// Given array and K
var arr = [ 84, 23, 45, 12, 56, 82 ];
var K = 3;
// Function Call
findSubArray(arr, K);
// This code is contributed by importantly
</script>
Producción:
12 56 82
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shawavisek35 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA