Length of longest subarray whose sum is not divisible by integer K

Given an array arr[] of size N, find the length of its longest subarray such that the sum of its elements not divisible by K, or determine that such subarray does not exist.

Examples:

Input : N = 3 , K = 3
arr[] = {1, 2, 3}
Output : 2
Explanation : Subarray [2,3] has sum of elements 5, which isn't divisible by 3

Input : N = 2 , K = 2
arr[] = {0, 6}
Output : No such subarray

Approach:
If the whole array is divisible by K, then there will be no such subarray. Also, if the sum of all elements is not divisible by K, then N will be the answer. Otherwise, we must remove some elements. Now, the idea is that there is no profit in removing elements which are divisible by K, because the sum will still be divisible by K. So, we must remove just one non divisible element and then rest array will be the answer. So let the first non-multiple of K be at index l, and the last one be at index r. We must either remove the prefix all the way up to l or the suffix all the way up to r, and we will clearly remove whichever shorter.

Below is the implementation of above approach.

Implementation in C++:

// CPP code to find the longest subarray with
// sum not divisible by K
#include<bits/stdc++.h>
using namespace std;

// function to find the longest subarray with
// sum not divisible by K
void subarrayNotDivisibleByK(int arr[], int n, int k)
{
    int sum = 0, l = -1, r;

    for (int i = 0; i < n; i++)
    {
        // non-multiple element of k
        if (arr[i] % k != 0)
        {
            // update left and right pointers
            if (l == -1)
                l = i;
            r = i;
        }
        // calculate total array sum
        sum += arr[i];
    }

    // if whole array sum is not
    // divisible, then N is answer
    if (sum % k != 0)
    {
        cout<< n;
        return;
    }

    // if no non-multiple element
    // is found, then there is no
    // such subarray
    if (l == -1)
    {
        cout<<"No subarray found";
        return;
    }

    // answer is subarray after removing
    // minimum of either prefix or
    // suffix
    cout<< n - min(l + 1, n - r);
    return;
}

// Driver code to test the above function
int main()
{
    int k = 3;
    int arr[] = {1, 2, 1, 2, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    subarrayNotDivisibleByK(arr, n, k);
    return 0;
}

Output: 5

Time complexity : O(N)
Space complexity : O(1)