乘积可被k整除的最小子阵-yiteyi-C++库

给定一个非负数数组，求其乘积为k的倍数的最小子数组的长度。 例如：

null

Input : arr[] = {1, 9, 16, 5, 4, 3, 2}           k = 720Output: 3The smallest subarray is {9, 16, 5} whoseproduct is 720.Input : arr[] = {1, 2, 4, 5, 6}        K = 96Output : No such subarray exists

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个想法很简单。我们穿过所有的子阵列。对于每个子阵列，我们计算其乘积。如果乘积是k的倍数，我们检查子数组的长度是否小于当前结果。

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 array                       
                         int                                     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 Function                       
                         int                                     main(                                     void                                     )                       
                         {                       
                                                 int                                     array[] = { 1, 9, 16, 5, 4, 3, 2 };                       
                                                 int                                     k = 720;                       
                                                 int                                     answer = findsubArray(array, k);                       
                                   
                                                 if                                     (answer != 0)                       
                                                 cout<<answer<<                                     ""                                     ;                       
                                                 else                       
                                                 cout<<                                     "No Such subarray exists."                                     <<                                     ""                                     ;                       
                                   
                                                 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 array                       
                         public                                     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 array                       
                         def                                     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 Function                       
                         array                                     =                                     [                                     1                                     ,                                     9                                     ,                                     16                                     ,                                     5                                     ,                                     4                                     ,                                     3                                     ,                                     2                                     ]                       
                         k                                     =                                     720                       
                         answer                                     =                                     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 array                       
                         function                                     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                                     .                                     ""                                     ;                       
                                                 else                       
                                                 echo                                     "No Such subarray exists."                                     .                                     ""                                     ;                       
                                   
                         // 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>                       

输出：

时间复杂度=O（n^2）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章