Longest subarray with sum not divisible by K

Updated

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)

Comment
Mithlesh Upadhyay Published 19 Nov 2026 · 3 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials