Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution{
- public:
- vector<int> segment_tree, v;
- int gcd(int a, int b) {
- if(a < b) {
- swap(a, b);
- }
- while(b != 0) {
- int tmp = a % b;
- a = b;
- b = tmp;
- }
- return a;
- }
- void build(int L, int R, int pos) {
- if(L == R) {
- segment_tree[pos] = v[L];
- }
- else {
- int mid = (L + R) / 2;
- build(L, mid, 2 * pos);
- build(mid + 1, R, 2 * pos + 1);
- segment_tree[pos] = gcd(segment_tree[2 * pos], segment_tree[2 * pos + 1]);
- }
- }
- int query(int L, int R, int pos, int i, int j) {
- // L R i L R j L R
- if(i <= L and R <= j) {
- return segment_tree[pos];
- }
- if(R < i or j < L) {
- return 0;
- }
- int mid = (L + R) / 2;
- return gcd(query(L, mid, 2 * pos, i, j), query(mid + 1, R, 2 * pos + 1, i, j));
- }
- int findSmallestSubArr(int arr[], int n, int g) {
- int ok = -1;
- v.resize(n);
- for(int i = 0; i < n; i++) {
- if(arr[i] == g) {
- return 1;
- }
- if(arr[i] % g == 0) {
- ok = 1;
- }
- v[i] = arr[i];
- }
- if(ok == -1) {
- return -1;
- }
- segment_tree.resize(4 * n);
- build(0, n - 1, 1);
- int res = 2e9;
- for(int i = 0; i < n; i++) {
- if(v[i] % g == 0) {
- int L = i + 1, R = n - 1;
- int idx = -1;
- while(L <= R) {
- int mid = L + (R - L) / 2;
- int gcd = query(0, n - 1, 1, i, mid);
- if(gcd == g) {
- R = mid - 1;
- idx = mid;
- }
- else if(gcd > g) {
- L = mid + 1;
- }
- else {
- R = mid - 1;
- }
- }
- if(idx != -1) {
- res = min(res, idx - i + 1);
- }
- }
- }
- if(res == 2e9) {
- res = -1;
- }
- return res;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement