How to find the largest subarray in an array whose all elements are divisible by 6 in O(N) ?

Question

Constraints :

1<=N<=1000000

1<=A[i]<=1000000000

Example :

4 6 12 18 33 32

Output : 3 {6,12,18} is the largest subarray whose all elements are divisible by 6 .

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

Answer 1

Algorithm:

1. Iterate over a loop from 1 to n.

2. In each loop check the length of the sub array which will be divisable by 6, that sub array will strt from i.

3. Keep on updating the max_size to get the max sub array size.

4. If any case is giving the output grater than the previous case then store its start and end values.

5. Finally print the array from start index to end index.

 

Program:

Void fun(int a[], int n){

     int max_size=0, start=0, end=0;

     for (int i=0;i<n;i++){

         int c=0, j=i;

         while(j<n and a[j]%6==0){

            j++;

            c++;

        }

       if(c>max_size){

             max_size=c;

             start= i;

             end=j;

        }

        i=j-1;

    }

    for(int i=start;i<end;i++) cout<<a[i]<<' ';

    cout<<endl;

}

Time: o(n)

Space: o(1)

Answer 2

Approach
1. Initialize startindex endindex(to calculate max len), start, end(to get actual index so as to get final subarray),flag(used to have a look that the subarray is continuous)
2. Iterating over an array
2.a. if element mod 6 is equal to 0 then calculate the max Len if it is len 
2.b. if flag is true it means subarray is going continually
2.c.Else make flag false to indicate break in subarray

Complexity 
Time complexity: O(n)
Space Complexity: O(1)

Answer 3

#How to find the largest subarray in an array whose all elements are divisible by 6 in O(N) ?
# solution:
# (start_index , end_index) is local range
# (max_start_index , max_end_index) is global range
# Here I iterate through every element if element is divisable by 6 and the last element was also
# divisable by 6 then i am updating the end_index which is a local valriable containg the upper bound of the slice.
# if the item is not divisable by 6 the i am checking is the local range is wider than global range or not if yes then i am updating it.

# Time complexity : O(N)
# space Complexity  O(1)

arr=list(map(int,input().split()))
n=len(arr)

start_index=0
end_index=0
max_start_index=0
max_end_index=0
for ind in range(n):
    if arr[ind] %6==0:
        if end_index == 0:
            start_index = ind
            end_index = ind
        end_index+=1
    else:
        if end_index - start_index > max_end_index - max_start_index :
            max_start_index=start_index
            max_end_index = end_index
            end_index=0
            start_index=0
print(arr[max_start_index : max_end_index])