Given an array A[] of size N and a positive integer K, the task is to find the length of the longest subarray such that all elements of the subarray is a factor of K.
Examples:
Input: A[] = {2, 8, 3, 10, 6, 7, 4, 9}, K = 60
Output: 3
Explanation: The longest subarray in which all elements are a factor of K (= 60) is {3, 10, 6}. Therefore, the required output is 3.Input: A[] = {7, 20, 8, 10, 5}, K = 20
Output: 2
Explanation: The longest subarray in which all elements are a factor of K (= 20) is {10, 5}. Therefore, the required output is 2.
Naive Approach: This simplest approach to solve this problem is to traverse the array and generate all possible subarrays of the given array. For each subarray, check if all its elements are a factor of K or not. If found to be true, then store the length of the subarray if it the maximum obtained till then. Finally, print the maximum length obtained as the required answer.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to traverse the array and check if arr[i] is a factor of K or not. If found to be true, then increment the length of the subarray. Otherwise, store the length of the subarray if it is the maximum obtained so far and reset to 0. Follow the steps below to solve the problem:
- Initialize a variable, say MaxLen, to store the length of longest subarray such that every element in the subarray is a factor of K.
- Initialize a variable, say Len, to store the length of the current subarray.
- Traverse the array and check if K % arr[i] = 0 or not. If found to be true, then increment the value of Len and update the value of MaxLen = max(Len, MaxLen).
- Finally, print the value of MaxLen.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the length of the longest// subarray in which all elements are a factor of Kint find_longest_subarray(int A[], int N, int K){ // Stores length of the longest subarray // in which all elements are a factor of K int MaxLen = 0; // Stores length of // the current subarray int Len = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If A[i] is a factor of K if (K % A[i] == 0) { // Update Len Len++; // Update MaxLen MaxLen = max(MaxLen, Len); } else { // Reset Len Len = 0; } } return MaxLen;}// Driver Codeint main(){ int A[] = { 2, 8, 3, 10, 6, 7, 4, 9 }; int N = sizeof(A) / sizeof(A[0]); ; int K = 60; cout << find_longest_subarray(A, N, K); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG { // Function to find the length of the longest // subarray in which all elements are a factor of K static int find_longest_subarray(int[] A, int N, int K) { // Stores length of the longest subarray // in which all elements are a factor of K int MaxLen = 0; // Stores length of // the current subarray int Len = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If A[i] is a // factor of K if (K % A[i] == 0) { // Update Len Len++; // Update MaxLen MaxLen = Math.max( MaxLen, Len); } // If A[i] is not a // factor of K else { // Update Len Len = 0; } } return MaxLen; } // Driver Code public static void main(String[] args) { int[] A = { 2, 8, 3, 10, 6, 7, 4, 9 }; int N = A.length; int K = 60; System.out.println( find_longest_subarray(A, N, K)); }} |
Python3
# Python3 program to implement# the above approach # Function to find the length of the# longest subarray in which all # elements are a factor of Kdef find_longest_subarray(A, N, K): # Stores length of the longest # subarray in which all elements # are a factor of K MaxLen = 0 # Stores length of the # current subarray Len = 0 # Traverse the array arr[] for i in range(N): # If A[i] is a factor of K if (K % A[i] == 0): # Update Len Len += 1 # Update MaxLen MaxLen = max(MaxLen, Len) # If A[i] is not a # factor of K else: # Reset Len Len = 0 return MaxLen# Driver CodeA = [ 2, 8, 3, 10, 6, 7, 4, 9 ]N = len(A) K = 60 print(find_longest_subarray(A, N, K)) # This code is contributed by susmitakundugoaldanga |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to find the length of the longest// subarray in which all elements are a factor of Kstatic int find_longest_subarray(int[] A, int N, int K){ // Stores length of the longest subarray // in which all elements are a factor of K int MaxLen = 0; // Stores length of // the current subarray int Len = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { // If A[i] is a // factor of K if (K % A[i] == 0) { // Update Len Len++; // Update MaxLen MaxLen = Math.Max(MaxLen, Len); } // If A[i] is not a // factor of K else { // Update Len Len = 0; } } return MaxLen;}// Driver Codepublic static void Main(string[] args){ int[] A = { 2, 8, 3, 10, 6, 7, 4, 9 }; int N = A.Length; int K = 60; Console.WriteLine(find_longest_subarray( A, N, K));}}// This code is contributed by chitranayal |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the length of the longest// subarray in which all elements are a factor of Kfunction find_longest_subarray(A, N, K){ // Stores length of the longest subarray // in which all elements are a factor of K let MaxLen = 0; // Stores length of // the current subarray let Len = 0; // Traverse the array arr[] for(let i = 0; i < N; i++) { // If A[i] is a // factor of K if (K % A[i] == 0) { // Update Len Len++; // Update MaxLen MaxLen = Math.max(MaxLen, Len); } // If A[i] is not a // factor of K else { // Update Len Len = 0; } } return MaxLen;}// Driver codelet A = [ 2, 8, 3, 10, 6, 7, 4, 9 ];let N = A.length;let K = 60;document.write(find_longest_subarray(A, N, K));// This code is contributed by code_hunt</script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
