Suppose you are given an array. You have to find the length of the longest subarray such that each and every element of it is divisible by k.
Examples:
Input : arr[] = { 1, 7, 2, 6, 8, 100, 3, 6, 16}, k=2
Output : 4Input : arr[] = { 3, 11, 22, 32, 55, 100, 1, 5}, k=5
Output : 2
Approach:
- Initialize two variables current_count and max_count with value 0;
- Iterate the array from left to right and check the divisibility of each element by k.
- If the element is divisible, then increment current_count, otherwise make current_count equal to 0
- Compare current_count with max_count at each element, if current_count is greater than max_count, assign the value of current_count to max_count
- Finally, output value of max_count
Below is the implementation of the above approach:
C++
// C++ program of above approach#include <bits/stdc++.h>using namespace std;// function to find longest subarrayint longestsubarray(int arr[], int n, int k){ int current_count = 0; // this will contain length of longest subarray found int max_count = 0; for (int i = 0; i < n; i++) { if (arr[i] % k == 0) current_count++; else current_count = 0; max_count = max(current_count, max_count); } return max_count;}// Driver codeint main(){ int arr[] = { 2, 5, 11, 32, 64, 88 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 8; cout << longestsubarray(arr, n, k); return 0;} |
Java
// Java program of above approachimport java.io.*;class GFG { // function to find longest subarray static int longestsubarray(int arr[], int n, int k) { int current_count = 0; // this will contain length of // longest subarray found int max_count = 0; for (int i = 0; i < n; i++) { if (arr[i] % k == 0) current_count++; else current_count = 0; max_count = Math.max(current_count, max_count); } return max_count; } // Driver code public static void main(String[] args) { int arr[] = { 2, 5, 11, 32, 64, 88 }; int n = arr.length; int k = 8; System.out.println(longestsubarray(arr, n, k)); }}// This code is contributed// by ajit |
Python3
# Python 3 program of above approach# function to find longest subarraydef longestsubarray(arr, n, k): current_count = 0 # this will contain length of # longest subarray found max_count = 0 for i in range(0, n, 1): if (arr[i] % k == 0): current_count += 1 else: current_count = 0 max_count = max(current_count, max_count) return max_count# Driver codeif __name__ == '__main__': arr = [2, 5, 11, 32, 64, 88] n = len(arr) k = 8 print(longestsubarray(arr, n, k))# This code is contributed by# Surendra_Gangwar |
C#
// C# program of above approachusing System;class GFG{// function to find longest subarraystatic int longestsubarray(int[] arr, int n, int k){ int current_count = 0; // this will contain length of // longest subarray found int max_count = 0; for (int i = 0; i < n; i++) { if (arr[i] % k == 0) current_count++; else current_count = 0; max_count = Math.Max(current_count, max_count); } return max_count;}// Driver codepublic static void Main(){ int[] arr = { 2, 5, 11, 32, 64, 88 }; int n = arr.Length; int k = 8; Console.Write(longestsubarray(arr, n, k));}}// This code is contributed // by Akanksha Rai |
PHP
<?php// PHP program of above approach // function to find longest subarray function longestsubarray($arr, $n, $k) { $current_count = 0; // This will contain length of // longest subarray found $max_count = 0; for ($i = 0; $i < $n; $i++) { if ($arr[$i] % $k == 0) $current_count++; else $current_count = 0; $max_count = max($current_count, $max_count); } return $max_count; } // Driver code $arr = array(2, 5, 11, 32, 64, 88 ); $n = sizeof($arr); $k = 8; echo longestsubarray($arr, $n, $k); // This code is contributed // by Sach_Code?> |
Javascript
<script> // Javascript program of above approach // function to find longest subarray function longestsubarray(arr, n, k) { let current_count = 0; // this will contain length of longest subarray found let max_count = 0; for (let i = 0; i < n; i++) { if (arr[i] % k == 0) current_count++; else current_count = 0; max_count = Math.max(current_count, max_count); } return max_count; } let arr = [ 2, 5, 11, 32, 64, 88 ]; let n = arr.length; let k = 8; document.write(longestsubarray(arr, n, k)); </script> |
Output
3
Time Complexity: O(n)
Auxiliary Space: 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!