Given an array arr[] containing positive integer elements, and a positive integer K. The problem is to find the length of longest subarray, whose sum is not divisible by K
Examples :
Input : arr[] = {1, 2, 3, 5} , K = 2
Output : 4
longest subarray : {1, 2, 3, 5} having sum = 11 which is not
divisible by 2
Input : arr[] = {2, 6} , K = 2
Output : No Subarray Found
Naive Approach :
Find all the subarrays and return the length of the longest subarray with sum not divisible by k. Time complexity : O(N^2)
Efficient Approach :
1. If the sum of all elements of an array is not divisible by K, then answer would be the size of the array, otherwise remove some elements either from start or end. 2. If we remove the elements which is divisible by K from start or from the end which are contiguous, the answer would not get affected. So remove all elements which are divisible by k either from start or end. 3. After step 2, if we remove one element which is not divisible by K from start or end, then sum would not be divisible by K. 4. For longest subarray, answer would be either the prefix or the suffix of the array. So find both and then take the maximum of the two. So let the first non-multiple of K be at index start, and the last one be at index end.
Implementation :
// C++ implementation of the above approach
#include<bits/stdc++.h>
using namespace std;
//Function to find maximum of two numbers
int max(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
//Function to find longest subarray sum not divisible by K
int longestSubarray(int arr[], int N, int K)
{
int sum = 0, Longest=0;
//Finding sum of all elements
for (int i = 0; i < N; i++)
sum = sum + arr[i];
//check if sum of all elements is divisible by K or not
if (sum%K != 0)
Longest = N;
else
{
//initializing start with N-1 and end with 0
// so that if all elements are divisible by K
// Ans would be assigned as 0
int start = N-1, end = 0;
for (int i = 0; i < N; i++)
{
if (arr[i]%K != 0)
{
start=i;
break;
}
}
for (int i = N-1; i >= 0; i--)
{
if (arr[i]%K != 0)
{
end=i;
break;
}
}
//Finding maximum of prefix and suffix
Longest = max(N-start-1,end);
}
return Longest;
}
//Driver Code
int main()
{
int arr[] = {1, 2, 4, 5};
int K = 4;
int N = sizeof(arr) / sizeof(arr[0]);
int Longest = longestSubarray(arr, N, K);
if(Longest == 0)
cout << "No Subarray Found";
else
cout << Longest;
return 0;
}
Output : 3
Time Complexity : O(N)