Skip to content

Instantly share code, notes, and snippets.

@kyunghoj
Last active July 7, 2016 15:06
Show Gist options
  • Save kyunghoj/7f4573a047d39fff42305e90be9d4b01 to your computer and use it in GitHub Desktop.
Save kyunghoj/7f4573a047d39fff42305e90be9d4b01 to your computer and use it in GitHub Desktop.
Coding challenge #13
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);
}
}
@kyunghoj
Copy link
Author

kyunghoj commented Jul 7, 2016

There's a better algorithm using segment tree.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment