Smallest subarray whose product leaves remainder K when divided by size of the array
Given an array arr[] of N integers and an integer K, the task is to find the length of the smallest subarray whose product when divided by N gives remainder K. If no such subarray exists the print “-1”.
Examples:
Input: N = 3, arr = {2, 2, 6}, K = 1
Output: 2
Explanation:
All possible subarrays are:
{2} -> 2(mod 3) = 2
{2} -> 2(mod 3) = 2
{6} -> 6(mod 3) = 0
{2, 2} -> (2 * 2)(mod 3) = 1
{2, 6} -> (2 * 6)(mod 3) = 0
{2, 2, 6} -> (2 * 2 * 6)(mod 3) = 0
Only subarray {2, 2} leaves the remainder K( = 1).
Therefore, the length of the minimum subarray is 2.Input: N = 4, arr = {2, 2, 3, 3}, K = 1
Output: 2
Explanation:
Only subarray {3, 3} satisfies the property, thus the length of the minimum subarray is 2.
Approach:
The idea is to generate all possible subarrays of the given array and print the length of the smallest subarray whose product of all element gives remainder K when divided by N.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the subarray of // minimum length int findsubArray( int arr[], int N, int K) { // Initialize the minimum // subarray size to N + 1 int res = N + 1; // Generate all possible subarray for ( int i = 0; i < N; i++) { // Initialize the product int curr_prod = 1; for ( int j = i; j < N; j++) { // Find the product curr_prod = curr_prod * arr[j]; if (curr_prod % N == K && res > (j - i + 1)) { res = min(res, j - i + 1); break ; } } } // Return the minimum size of subarray return (res == N + 1) ? 0 : res; } // Driver Code int main() { // Given array int arr[] = { 2, 2, 3 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 1; int answer = findsubArray(arr, N, K); if (answer != 0) cout << answer; else cout << "-1" ; return 0; } |
Java
// Java program to implement the // above approach import java.util.*; class GFG{ // Function to find the subarray of // minimum length static int findsubArray( int arr[], int N, int K) { // Initialize the minimum // subarray size to N + 1 int res = N + 1 ; // Generate all possible subarray for ( int i = 0 ; i < N; i++) { // Initialize the product int curr_prod = 1 ; for ( int j = i; j < N; j++) { // Find the product curr_prod = curr_prod * arr[j]; if (curr_prod % N == K && res > (j - i + 1 )) { res = Math.min(res, j - i + 1 ); break ; } } } // Return the minimum size of subarray return (res == N + 1 ) ? 0 : res; } // Driver code public static void main(String[] args) { // Given array int arr[] = { 2 , 2 , 3 }; int N = arr.length; int K = 1 ; int answer = findsubArray(arr, N, K); if (answer != 0 ) System.out.println(answer); else System.out.println( "-1" ); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach # Function to find the subarray of # minimum length def findsubArray(arr, N, K): # Initialize the minimum # subarray size to N + 1 res = N + 1 # Generate all possible subarray for i in range ( 0 , N): # Initialize the product curr_prad = 1 for j in range (i, N): # Find the product curr_prad = curr_prad * arr[j] if (curr_prad % N = = K and res > (j - i + 1 )): res = min (res, j - i + 1 ) break # Return the minimum size of subarray if res = = N + 1 : return 0 else : return res # Driver code if __name__ = = '__main__' : # Given array arr = [ 2 , 2 , 3 ] N = len (arr) K = 1 answer = findsubArray(arr, N, K) if (answer ! = 0 ): print (answer) else : print ( - 1 ) # This code is contributed by virusbuddah_ |
C#
// C# program to implement the // above approach using System; class GFG{ // Function to find the subarray of // minimum length static int findsubArray( int []arr, int N, int K) { // Initialize the minimum // subarray size to N + 1 int res = N + 1; // Generate all possible subarray for ( int i = 0; i < N; i++) { // Initialize the product int curr_prod = 1; for ( int j = i; j < N; j++) { // Find the product curr_prod = curr_prod * arr[j]; if (curr_prod % N == K && res > (j - i + 1)) { res = Math.Min(res, j - i + 1); break ; } } } // Return the minimum size of subarray return (res == N + 1) ? 0 : res; } // Driver code public static void Main(String[] args) { // Given array int []arr = { 2, 2, 3 }; int N = arr.Length; int K = 1; int answer = findsubArray(arr, N, K); if (answer != 0) Console.WriteLine(answer); else Console.WriteLine( "-1" ); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript program to implement the // above approach // Function to find the subarray of // minimum length function findsubArray(arr, N, K) { // Initialize the minimum // subarray size to N + 1 var res = N + 1; // Generate all possible subarray for (i = 0; i < N; i++) { // Initialize the product var curr_prod = 1; for (j = i; j < N; j++) { // Find the product curr_prod = curr_prod * arr[j]; if (curr_prod % N == K && res > (j - i + 1)) { res = Math.min(res, j - i + 1); break ; } } } // Return the minimum size of subarray return (res == N + 1) ? 0 : res; } // Driver code // Given array var arr = [ 2, 2, 3 ]; var N = arr.length; var K = 1; var answer = findsubArray(arr, N, K); if (answer != 0) document.write(answer); else document.write( "-1" ); // This code is contributed by umadevi9616 </script> |
Output:
2
Time Complexity: O(N2)
Auxiliary Space: O(1)