Given an array of integers arr[] and a positive integer K, the task is to find the count of the longest possible subarrays with sum of its elements not divisible by K.
Examples:
Input: arr[] = {2, 3, 4, 6}, K = 3
Output: 1
Explanation: There is only one longest possible subarray of size 3 i.e. {3, 4, 6} having a sum 13, which is not divisible by K = 3.Input: arr[] = {2, 4, 3, 5, 1}, K = 3
Output: 2
Explanation: There are 2 longest possible subarrays of size 4 i.e. {2, 4, 3, 5} and {4, 3, 5, 1} having a sum 14 and 13 respectively, which is not divisible by K = 3.
Approach:
- Check if the sum of all the elements of the array is divisible by K
- If the sum is not divisible by K, return 1 as the longest subarray would be of size N.
- Else
- Find the index of the first number not divisible by K. Let that be L.
- Find the index of the last number not divisible by K. Let that be R.
- Remove the elements all the way up to index L and find the size of the subarray. Remove the elements beyond R and find the size of this subarray as well. Whichever length is greater, that will be the size of the longest subarray not divisible by K.
- Using this length as the window size, apply the sliding window technique on the arr[] to find out the count of sub-arrays of the size obtained above which are not divisible by K.
Below is the implementation of the above approach:
C++
// C++ program for the above problem#include <bits/stdc++.h>using namespace std;// Function to find the count of// longest subarrays with sum not// divisible by Kint CountLongestSubarrays( int arr[], int n, int k){ // Sum of all elements in // an array int i, s = 0; for (i = 0; i < n; ++i) { s += arr[i]; } // If overall sum is not // divisible then return // 1, as only one subarray // of size n is possible if (s % k) { return 1; } else { int ini = 0; // Index of the first number // not divisible by K while (ini < n && arr[ini] % k == 0) { ++ini; } int final = n - 1; // Index of the last number // not divisible by K while (final >= 0 && arr[final] % k == 0) { --final; } int len, sum = 0, count = 0; // Subarray doesn't exist if (ini == n) { return -1; } else { len = max(n - 1 - ini, final); } // Sum of the window for (i = 0; i < len; i++) { sum += arr[i]; } if (sum % k != 0) { count++; } // Calculate the sum of rest of // the windows of size len for (i = len; i < n; i++) { sum = sum + arr[i]; sum = sum - arr[i - len]; if (sum % k != 0) { count++; } } return count; }}// Driver Codeint main(){ int arr[] = { 3, 2, 2, 2, 3 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; cout << CountLongestSubarrays(arr, n, k); return 0;} |
Java
// Java program for the above problem import java.util.*; class GFG{ // Function to find the count of // longest subarrays with sum not // divisible by K static int CountLongestSubarrays(int arr[], int n, int k) { // Sum of all elements in // an array int i, s = 0; for(i = 0; i < n; ++i) { s += arr[i]; } // If overall sum is not // divisible then return // 1, as only one subarray // of size n is possible if ((s % k) != 0) { return 1; } else { int ini = 0; // Index of the first number // not divisible by K while (ini < n && arr[ini] % k == 0) { ++ini; } int fin = n - 1; // Index of the last number // not divisible by K while (fin >= 0 && arr[fin] % k == 0) { --fin; } int len, sum = 0, count = 0; // Subarray doesn't exist if (ini == n) { return -1; } else { len = Math.max(n - 1 - ini, fin); } // Sum of the window for(i = 0; i < len; i++) { sum += arr[i]; } if (sum % k != 0) { count++; } // Calculate the sum of rest of // the windows of size len for(i = len; i < n; i++) { sum = sum + arr[i]; sum = sum - arr[i - len]; if (sum % k != 0) { count++; } } return count; } } // Driver Code public static void main (String []args) { int arr[] = { 3, 2, 2, 2, 3 }; int n = arr.length; int k = 3; System.out.print(CountLongestSubarrays( arr, n, k)); } } // This code is contributed by chitranayal |
Python3
# Python3 program for the above problem # Function to find the count of# longest subarrays with sum not# divisible by Kdef CountLongestSubarrays(arr, n, k): # Sum of all elements in # an array s = 0 for i in range(n): s += arr[i] # If overall sum is not # divisible then return # 1, as only one subarray # of size n is possible if(s % k): return 1 else: ini = 0 # Index of the first number # not divisible by K while (ini < n and arr[ini] % k == 0): ini += 1 final = n - 1 # Index of the last number # not divisible by K while (final >= 0 and arr[final] % k == 0): final -= 1 sum, count = 0, 0 # Subarray doesn't exist if(ini == n): return -1 else: length = max(n - 1 - ini, final) # Sum of the window for i in range(length): sum += arr[i] if(sum % k != 0): count += 1 # Calculate the sum of rest of # the windows of size len for i in range(length, n): sum = sum + arr[i] sum = sum + arr[i - length] if (sum % k != 0): count += 1 return count# Driver Codeif __name__ == '__main__': arr = [ 3, 2, 2, 2, 3 ] n = len(arr) k = 3 print(CountLongestSubarrays(arr, n, k)) # This code is contributed by Shivam Singh |
C#
// C# program for the above problemusing System;class GFG{// Function to find the count of// longest subarrays with sum not// divisible by Kstatic int CountLongestSubarrays(int[] arr, int n, int k){ // Sum of all elements in // an array int i, s = 0; for(i = 0; i < n; ++i) { s += arr[i]; } // If overall sum is not // divisible then return // 1, as only one subarray // of size n is possible if ((s % k) != 0) { return 1; } else { int ini = 0; // Index of the first number // not divisible by K while (ini < n && arr[ini] % k == 0) { ++ini; } int fin = n - 1; // Index of the last number // not divisible by K while (fin >= 0 && arr[fin] % k == 0) { --fin; } int len, sum = 0, count = 0; // Subarray doesn't exist if (ini == n) { return -1; } else { len = Math.Max(n - 1 - ini, fin); } // Sum of the window for(i = 0; i < len; i++) { sum += arr[i]; } if (sum % k != 0) { count++; } // Calculate the sum of rest of // the windows of size len for(i = len; i < n; i++) { sum = sum + arr[i]; sum = sum - arr[i - len]; if (sum % k != 0) { count++; } } return count; }}// Driver Codepublic static void Main(String[] args){ int[] arr = { 3, 2, 2, 2, 3 }; int n = arr.Length; int k = 3; Console.WriteLine(CountLongestSubarrays( arr, n, k));}}// This code is contributed by jrishabh99 |
Javascript
<script>// JavaScript program for the above problem // Function to find the count of // longest subarrays with sum not // divisible by K function CountLongestSubarrays(arr, n, k) { // Sum of all elements in // an array let i, s = 0; for(i = 0; i < n; ++i) { s += arr[i]; } // If overall sum is not // divisible then return // 1, as only one subarray // of size n is possible if ((s % k) != 0) { return 1; } else { let ini = 0; // Index of the first number // not divisible by K while (ini < n && arr[ini] % k == 0) { ++ini; } let fin = n - 1; // Index of the last number // not divisible by K while (fin >= 0 && arr[fin] % k == 0) { --fin; } let len, sum = 0, count = 0; // Subarray doesn't exist if (ini == n) { return -1; } else { len = Math.max(n - 1 - ini, fin); } // Sum of the window for(i = 0; i < len; i++) { sum += arr[i]; } if (sum % k != 0) { count++; } // Calculate the sum of rest of // the windows of size len for(i = len; i < n; i++) { sum = sum + arr[i]; sum = sum - arr[i - len]; if (sum % k != 0) { count++; } } return count; } } // Driver Codelet arr = [ 3, 2, 2, 2, 3 ]; let n = arr.length; let k = 3; document.write(CountLongestSubarrays( arr, n, k)); // This code is contributed by sanjoy_62 </script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
