Dado un arreglo arr[] que consta de N enteros positivos, la tarea es encontrar un subarreglo de longitud K tal que la concatenación de cada elemento del subarreglo sea divisible por X. Si no existe tal subarreglo, imprima «-1» . Si existe más de un subarreglo, imprima cualquiera de ellos.
Ejemplos:
Entrada: arr[] = {1, 2, 4, 5, 9, 6, 4, 3, 7, 8}, K = 4, X = 4
Salida: 4 5 9 6
Explicación:
Los elementos del subarreglo {4 , 5, 9, 6} se concatena para formar 4596, que es divisible por 4.Entrada: arr[] = {2, 3, 5, 1, 3}, K = 3, X = 6
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles de longitud K e imprimir ese subarreglo cuya concatenación de elementos es divisible por X . Si no existe tal subarreglo, imprima «-1» . De lo contrario, imprima cualquiera de estos subarreglos.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la técnica de la ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Genere un número concatenando los primeros elementos de la array K. Guárdelo en una variable, digamos num .
- Comprueba si el número generado es divisible por X o no. Si se encuentra que es cierto, imprima el subarreglo actual.
- De lo contrario, recorra la array sobre el rango [K, N] y para cada elemento siga los pasos a continuación:
- Agregue los dígitos del elemento arr[i] a la variable num .
- Elimina los dígitos del elemento arr[i – K] del frente del num .
- Ahora comprueba si el número actual formado es divisible por X o no. Si se encuentra que es cierto, imprima el subarreglo actual en el rango [i – K, i] .
- De lo contrario, busque el siguiente subarreglo.
- Si no existe tal subarreglo, imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the starting
// index of the subarray whose
// concatenation is divisible by X
int findSubarray(vector<int> arr,
int K, int X)
{
int i, num = 0;
// Generate the concatenation
// of first K length subarray
for (i = 0; i < K; i++) {
num = num * 10 + arr[i];
}
// If num is divisible by X
if (num % X == 0) {
return 0;
}
// Traverse the remaining array
for (int j = i; j < arr.size(); j++) {
// Append the digits of arr[i]
num = (num % (int)pow(10, j - 1))
* 10
+ arr[j];
// If num is divisible by X
if (num % X == 0) {
return j - i + 1;
}
}
// No subarray exists
return -1;
}
// Function to print the subarray in
// the range [answer, answer + K]
void print(vector<int> arr, int answer,
int K)
{
// No such subarray exists
if (answer == -1) {
cout << answer;
}
// Otherwise
else {
// Print the subarray in the
// range [answer, answer + K]
for (int i = answer;
i < answer + K; i++) {
cout << arr[i] << " ";
}
}
}
// Driver Code
int main()
{
// Given array arr[]
vector<int> arr = { 1, 2, 4, 5, 9,
6, 4, 3, 7, 8 };
int K = 4, X = 4;
// Function Call
int answer = findSubarray(arr, K, X);
// Function Call to print subarray
print(arr, answer, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to return the starting
// index of the subarray whose
// concatenation is divisible by X
static int findSubarray(ArrayList<Integer> arr, int K,
int X)
{
int i, num = 0;
// Generate the concatenation
// of first K length subarray
for(i = 0; i < K; i++)
{
num = num * 10 + arr.get(i);
}
// If num is divisible by X
if (num % X == 0)
{
return 0;
}
// Traverse the remaining array
for(int j = i; j < arr.size(); j++)
{
// Append the digits of arr[i]
num = (num % (int)Math.pow(10, j - 1)) *
10 + arr.get(j);
// If num is divisible by X
if (num % X == 0)
{
return j - i + 1;
}
}
// No subarray exists
return -1;
}
// Function to print the subarray in
// the range [answer, answer + K]
static void print(ArrayList<Integer> arr, int answer,
int K)
{
// No such subarray exists
if (answer == -1)
{
System.out.println(answer);
}
// Otherwise
else
{
// Print the subarray in the
// range [answer, answer + K]
for(int i = answer; i < answer + K; i++)
{
System.out.print(arr.get(i) + " ");
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
ArrayList<Integer> arr = new ArrayList<Integer>(
Arrays.asList(1, 2, 4, 5, 9, 6, 4, 3, 7, 8));
int K = 4, X = 4;
// Function call
int answer = findSubarray(arr, K, X);
// Function call to print subarray
print(arr, answer, K);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program for the above approach # Function to return the starting # index of the subarray whose # concatenation is divisible by X def findSubarray(arr, K, X): num = 0 # Generate the concatenation # of first K length subarray for i in range(0, K): num = num * 10 + arr[i] # If num is divisible by X if num % X == 0: return 0 i = K # Traverse the remaining array for j in range(i, len(arr)): # Append the digits of arr[i] num = ((num % int(pow(10, j - 1))) * 10 + arr[j]) # If num is divisible by X if num % X == 0: return j - i + 1 # No subarray exists return -1 # Function to print the subarray in # the range [answer, answer + K] def print_subarray(arr, answer, K): # No such subarray exists if answer == -1: print(answer) # Otherwise else: # Print the subarray in the # range [answer, answer + K] for i in range(answer, answer + K): print(arr[i], end = " ") # Driver Code if __name__ == "__main__": # Given array arr[] arr = [ 1, 2, 4, 5, 9, 6, 4, 3, 7, 8 ] K = 4 X = 4 # Function call answer = findSubarray(arr, K, X) # Function call to print subarray print_subarray(arr, answer, K) # This code is contributed by akhilsaini
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return the starting
// index of the subarray whose
// concatenation is divisible by X
static int findSubarray(List<int> arr, int K,
int X)
{
int i, num = 0;
// Generate the concatenation
// of first K length subarray
for(i = 0; i < K; i++)
{
num = num * 10 + arr[i];
}
// If num is divisible by X
if (num % X == 0)
{
return 0;
}
// Traverse the remaining array
for(int j = i; j < arr.Count; j++)
{
// Append the digits of arr[i]
num = (num % (int)Math.Pow(10, j - 1)) *
10 + arr[j];
// If num is divisible by X
if (num % X == 0)
{
return j - i + 1;
}
}
// No subarray exists
return -1;
}
// Function to print the subarray in
// the range [answer, answer + K]
static void print(List<int> arr, int answer,
int K)
{
// No such subarray exists
if (answer == -1)
{
Console.WriteLine(answer);
}
// Otherwise
else
{
// Print the subarray in the
// range [answer, answer + K]
for(int i = answer; i < answer + K; i++)
{
Console.Write(arr[i] + " ");
}
}
}
// Driver Code
static public void Main()
{
// Given array arr[]
List<int> arr = new List<int>(){ 1, 2, 4, 5, 9,
6, 4, 3, 7, 8 };
int K = 4, X = 4;
// Function call
int answer = findSubarray(arr, K, X);
// Function call to print subarray
print(arr, answer, K);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program for the above approach
// Function to return the starting
// index of the subarray whose
// concatenation is divisible by X
function findSubarray(arr, K, X)
{
var i, num = 0;
// Generate the concatenation
// of first K length subarray
for(i = 0; i < K; i++)
{
num = num * 10 + arr[i];
}
// If num is divisible by X
if (num % X == 0)
{
return 0;
}
// Traverse the remaining array
for(var j = i; j < arr.length; j++)
{
// Append the digits of arr[i]
num = (num % parseInt(Math.pow(10, j - 1))) *
10 + arr[j];
// If num is divisible by X
if (num % X == 0)
{
return j - i + 1;
}
}
// No subarray exists
return -1;
}
// Function to print the subarray in
// the range [answer, answer + K]
function print(arr, answer, K)
{
// No such subarray exists
if (answer == -1)
{
document.write(answer);
}
// Otherwise
else
{
// Print the subarray in the
// range [answer, answer + K]
for(var i = answer;
i < answer + K; i++)
{
document.write( arr[i] + " ");
}
}
}
// Driver Code
// Given array arr[]
var arr = [ 1, 2, 4, 5, 9,
6, 4, 3, 7, 8 ];
var K = 4, X = 4;
// Function Call
var answer = findSubarray(arr, K, X);
// Function Call to print subarray
print(arr, answer, K);
// This code is contributed by itsok
</script>
Producción:
4 5 9 6
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