Given an array of non-negative numbers, find length of smallest subarray whose product is a multiple of k.
Examples :
Input : arr[] = {1, 9, 16, 5, 4, 3, 2}
k = 720
Output: 3
The smallest subarray is {9, 16, 5} whose
product is 720.
Input : arr[] = {1, 2, 4, 5, 6}
K = 96
Output : No such subarray exists
The idea is simple. We traverse through all subarrays. For each subarray, we compute its product. If the product is multiple of k, we check if length of the subarray is smaller than current result.
Implementation:
C++
// C++ program to find smallest subarray// with product divisible by k.#include <bits/stdc++.h>using namespace std;// function to find the subarray of// minimum length and end of sub arrayint findsubArray(int arr[], int k){ // find the length of array int n = 7; // try of every sub array whether it // result in multiple of k or not if it // is store it in the result // and find for the minimum using // dynamic programming int res = n + 1; for (int i = 0; i < n; i++) { // Find minimum length product // beginning with arr[i]. int curr_prod = 1; for (int j = i; j < n; j++) { curr_prod = curr_prod * arr[j]; if (curr_prod % k == 0 && res > (j - i + 1)) { res = min(res, j - i + 1); break; } } } return (res == n + 1) ? 0 : res;}// driver Functionint main(void){ int array[] = { 1, 9, 16, 5, 4, 3, 2 }; int k = 720; int answer = findsubArray(array, k); if (answer != 0) cout<<answer<<"\n"; else cout<<"No Such subarray exists."<<"\n"; return 0;} // This code is contributed by Nikita Tiwari. |
Java
// Java program to find smallest subarray// with product divisible by k.import java.util.*;// function to find the subarray of// minimum length and end of sub arraypublic class findSubArray { public static int findsubArray(int arr[], int k) { // find the length of array int n = arr.length; // try of every sub array whether it result // in multiple of k or not if it // is store it in the result // and find for the minimum using // dynamic programming int res = n+1; for (int i = 0; i < n; i++) { // Find minimum length product beginning // with arr[i]. int curr_prod = 1; for (int j = i; j < n; j++) { curr_prod = curr_prod * arr[j]; if (curr_prod % k == 0 && res > (j-i+1)) { res = Math.min(res, j-i+1); break; } } } return (res == n+1)? 0 : res; } // driver Function public static void main(String[] args) { int array[] = { 1, 9, 16, 5, 4, 3, 2 }; int k = 720; int answer = findsubArray(array, k); if (answer != 0) System.out.println(answer); else System.out.println("No Such subarray exists."); }} |
Python3
# Python 3 program to find smallest # subarray with product divisible by k.# function to find the subarray of# minimum length and end of sub arraydef findsubArray(arr, k) : # find the length of array n= len(arr) # try of every sub array whether it # result in multiple of k or not if # it is store it in the result # and find for the minimum using # dynamic programming res = n+1 for i in range(0,n) : # Find minimum length product # beginning with arr[i]. curr_prod = 1 for j in range( i, n): curr_prod = curr_prod * arr[j] if (curr_prod % k == 0 and res > (j - i + 1)) : res = min(res, j - i + 1) break if(res == n + 1) : return 0 else : return res # driver Functionarray = [1, 9, 16, 5, 4, 3, 2 ]k = 720answer = findsubArray(array, k)if (answer != 0): print(answer)else : print("No Such subarray exists.") # This code is contributed by Nikita Tiwari. |
C#
// C# program to find smallest subarray// with product divisible by k.using System;public class GFG { // function to find the subarray of // minimum length and end of sub array public static int findsubArray(int []arr, int k) { // find the length of array int n = arr.Length; // try of every sub array whether it result // in multiple of k or not if it // is store it in the result // and find for the minimum using // dynamic programming int res = n+1; for (int i = 0; i < n; i++) { // Find minimum length product beginning // with arr[i]. int curr_prod = 1; for (int j = i; j < n; j++) { curr_prod = curr_prod * arr[j]; if (curr_prod % k == 0 && res > (j-i+1)) { res = Math.Min(res, j-i+1); break; } } } return (res == n+1) ? 0 : res; } // driver Function public static void Main() { int []array = { 1, 9, 16, 5, 4, 3, 2 }; int k = 720; int answer = findsubArray(array, k); if (answer != 0) Console.WriteLine(answer); else Console.WriteLine("No Such subarray" + " exists."); }}// This code is contributed by vt_m. |
PHP
<?php// PHP program to find smallest subarray// with product divisible by k.// function to find the subarray of// minimum length and end of sub arrayfunction findsubArray($arr, $k){ // find the length of array $n = 7; // try of every sub array // whether it result in // multiple of k or not if // it is store it in the // result and find for the // minimum using dynamic // programming $res = $n + 1; for ($i = 0; $i < $n; $i++) { // Find minimum length product // beginning with arr[i]. $curr_prod = 1; for ($j = $i; $j < $n; $j++) { $curr_prod = $curr_prod * $arr[$j]; if ($curr_prod % $k == 0 && $res > ($j - $i + 1)) { $res = min($res, $j - $i + 1); break; } } } return ($res == $n + 1) ? 0 : $res;} // Driver Code $arr = array(1, 9, 16, 5, 4, 3, 2); $k = 720; $answer = findsubArray($arr, $k); if ($answer != 0) echo $answer."\n"; else echo "No Such subarray exists."."\n"; // This code is contributed by Sam007?> |
Javascript
<script> // Javascript program to find smallest subarray // with product divisible by k. // function to find the subarray of // minimum length and end of sub array function findsubArray(arr, k) { // find the length of array let n = arr.length; // try of every sub array whether it result // in multiple of k or not if it // is store it in the result // and find for the minimum using // dynamic programming let res = n+1; for (let i = 0; i < n; i++) { // Find minimum length product beginning // with arr[i]. let curr_prod = 1; for (let j = i; j < n; j++) { curr_prod = curr_prod * arr[j]; if (curr_prod % k == 0 && res > (j-i+1)) { res = Math.min(res, j-i+1); break; } } } return (res == n+1) ? 0 : res; } let array = [ 1, 9, 16, 5, 4, 3, 2 ]; let k = 720; let answer = findsubArray(array, k); if (answer != 0) document.write(answer); else document.write("No Such subarray" + " exists."); </script> |
Output:
3
Time Complexity: O(n^2)
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!
