Given an array arr[] consisting of N positive integers, the task is to find a subarray of length K such that concatenation of each element of the subarray is divisible by X. If no such subarray exists, then print “-1”. If more than one such subarray exists, print any one of them.
Examples:
Input: arr[] = {1, 2, 4, 5, 9, 6, 4, 3, 7, 8}, K = 4, X = 4
Output: 4 5 9 6
Explanation:
The elements of the subarray {4, 5, 9, 6} concatenates to form 4596, which is divisible by 4.Input: arr[] = {2, 3, 5, 1, 3}, K = 3, X = 6
Output: -1
Naive Approach: The simplest approach to solve the problem is to generate all possible subarrays of length K and print that subarray whose concatenation of elements is divisible by X. If no such subarray exists, print “-1”. Otherwise, print any of these subarrays.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using the Sliding Window Technique. Follow the steps below to solve the problem:
- Generate a number by concatenating the first K array elements. Store it in a variable, say num.
- Check if the number generated is divisible by X or not. If found to be true, then print the current subarray.
- Otherwise, traverse the array over the range [K, N] and for each element follow the steps below:
- Add the digits of the element arr[i] to the variable num.
- Remove the digits of the element arr[i – K] from the front of the num.
- Now check if the current number formed is divisible by X or not. If found to be true, then print the current subarray in the range [i – K, i].
- Otherwise, check for the next subarray.
- If no such subarray exists, then print “-1”.
Below is the implementation of the above approach:
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 Xint 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 Codeint 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 approachimport java.io.*;import java.util.*;class GFG{// Function to return the starting// index of the subarray whose// concatenation is divisible by Xstatic 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 Codepublic 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 Xdef 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Function to return the starting// index of the subarray whose// concatenation is divisible by Xstatic 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 Codestatic 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 Xfunction 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 Callvar answer = findSubarray(arr, K, X);// Function Call to print subarrayprint(arr, answer, K);// This code is contributed by itsok</script> |
Output:
4 5 9 6
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
