| 8 | |
| 2 | |
| 6 9 7 10 12 24 36 27 |
Given an array arr[] of n numbers and an integer k, find length of the minimum sub-array with gcd equals to k.
Example:
Input: arr[] = {6, 9, 7, 10, 12, 24, 36, 27}, k = 3
Output: 2
Explanation: GCD of subarray {6,9} is 3. GCD of subarray {24,36,27} is also 3, but {6,9} is the smallest
| import java.io.*; | |
| import java.util.*; | |
| public class SmallestSubarrayWithGCD { | |
| // Input format: | |
| // n | |
| // K | |
| // numbers | |
| public static void main (String [] args) | |
| { | |
| Scanner in = new Scanner(System.in); | |
| int n = in.nextInt(); // n : number of the numbers | |
| int K = in.nextInt(); // K : | |
| int arr[] = new int[n]; | |
| int idx = 0; | |
| while (in.hasNextInt()) | |
| { | |
| arr[idx++] = in.nextInt(); | |
| } | |
| int A[][] = new int[n][n]; | |
| for (int i = 0; i < n; i++) | |
| { | |
| A[i][i] = arr[i]; | |
| } | |
| for (int i = 1; i < n; i++) | |
| { | |
| for (int j = 0; i+j < n; j++) | |
| { | |
| A[i+j][j] = gcd (A[i+j-1][j], A[i+j][j+1]); | |
| if (A[i+j][j] == K) | |
| { | |
| System.out.println(i+1); | |
| return; | |
| } | |
| } | |
| } | |
| System.out.println(-1); | |
| return; | |
| } | |
| private static int gcd(int a, int b) | |
| { | |
| int x, y; | |
| if (a < 0 || b < 0) return -1; | |
| if (a > b) | |
| { | |
| x = a; y = b; | |
| } | |
| else | |
| { | |
| x = b; y = a; | |
| } | |
| if (y == 0) return x; | |
| else return gcd(y, x % y); | |
| } | |
| } |
There's a better algorithm using segment tree.