- Longest subarray
- 2024-03-29 11:24:03 @

**Prerequisite** : Number Theory, Binary Search, Two Pointer, Prefix Sum

**Problem statement summary** : You are given an Array A[] of length N. You need to find out the length of the longest subarray where the GCD of the subarray is greater than X.

**Solution** : If you have noticed , X and all elements of the array are less than or equal 100.

For each i is 1<= i <= 100, we can calculate in a 2d array , total cost for which gcd we want to make.

For example, if we want to make gcd = 3, and subarray is looking like A = {1 , 2, 1};

For position 1, we need to increase 2 times, A ={ 3, 2, 1}

For position 2, we need to increase 1 times, A = {3, 3, 1}

For position 3, we need to increase 2 times, A ={ 3, 3,3} , gcd = 3.

Total cost for each position we can save an array.

In each subarray, We can use binary search, because we have limit of cost K.

For each, i > X , Find the best subarray which length is maximum and total cost is less than or equal K.

**Time Complexity** : O ( 100 * N * log (N) ).

Instead of Binary Search we can use two pointer, time complexity has less than above solution and its complexity: O (100 * N). check ->(Tester Code) in Solution section.

# 0 comments

# Information

- ID
- 1043
- Difficulty
- 7
- Category
- (None)
- Tags
- (None)
- # Submissions
- 17
- Accepted
- 6
- Accepted Ratio
- 35%
- Uploaded By