Longest Increasing Subarray of Composite Numbers in Array
Given an array of integers arr[], the task is to find the longest increasing subarray of composite numbers in an array.
Examples:
Input: arr[] = [1, 4, 7, 6, 8, 10, 12]
Output: [6, 8, 10, 12]
Explanation: The longest increasing subarray of composite numbers in the given array is [6, 8, 10, 12], which consists of the composite numbers 6, 8, 10, and 12. The subarray starts at index 3 (6) and ends at index 6 (12).Input: arr[] = [10, 15, 23, 9, 27, 30, 45, 21, 8, 12]
Output: [9, 27, 30, 45]
Explanation: The longest increasing subarray of composite numbers in the given array is [9, 27, 30, 45, 21], which consists of the composite numbers 9, 27, 21, 30, and 45. The subarray starts at index 3 (9) and ends at index 6 (45).
Approach: To solve the problem follow the below idea:
- The approach to solve this problem is iterating through the array, checking whether each element is composite or not.
- If the current element is composite, the program checks if it’s greater than the previous element (or if it’s the first element).
- If it is, then the length of the current increasing subarray is incremented, otherwise, it is reset to 1.
- If the length of the current increasing subarray is greater than the maximum length seen so far, the maximum length and the starting index of the subarray are updated.
- Finally, the program returns the longest increasing subarray of composite numbers as a vector. If there is no such subarray, it returns an empty vector.
Here are the steps of the approach:
- Initialize maxLen to 0, len to 0, and startIndex to -1 to keep track of the longest increasing subarray of composite numbers found, the length of the current subarray, and the starting index.
- Check If the current element is composite, If it’s the first element or greater than the previous, increment len.
- Otherwise, start a new subarray.
- And update maxLen to len and startIndex to i – len.
- If not composite or we’ve reached the end of the array.
- Reset len to 0 to start counting a new subarray.
- If a subarray of composite numbers was found (if maxLen > 0), return it starting from startIndex and of length maxLen. Otherwise, return an empty array to indicate no increasing subarray of composite numbers was found in the input array.
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to check if a number is composite // (has divisors other than 1 and itself) bool isComposite( int num) { // Check if the number is less than 2 if (num < 2) { // Numbers less than 2 are not // considered composite return false ; } // Iterate through potential divisors // from 2 to num/2 for ( int i = 2; i <= num / 2; i++) { // If a divisor is found, the number // is composite if (num % i == 0) { return true ; } } // If no divisors are found, the number // is not composite return false ; } // Function to find the longest increasing // subarray of composite numbers vector< int > longestIncreasingSubarrayOfCompositeNumbers( vector< int >& arr) { int n = arr.size(); int maxLen = 0, len = 0, startIndex = -1; for ( int i = 0; i < n; i++) { // Check if the current // element is composite if (isComposite(arr[i])) { // If it's the first element or // greater than the previous, // increment subarray length if (i == 0 || arr[i] > arr[i - 1]) { len++; } // Otherwise, start a new subarray else { len = 1; } // Update the maximum length if a // longer subarray is found if (len > maxLen) { maxLen = len; // Update the start index // of the longest subarray startIndex = i - len + 1; } } // Reset the subarray length if the // current element is not composite else { len = 0; } } // If no increasing subarray of composite // numbers is found, return an empty vector if (maxLen == 0) { return {}; } vector< int > result(maxLen); // Copy the elements of the longest // subarray into the result vector for ( int i = 0; i < maxLen; i++) { result[i] = arr[startIndex + i]; } return result; } // Drivers code int main() { vector< int > arr = { 10, 15, 23, 9, 27, 30, 45, 21, 8, 12 }; vector< int > result = longestIncreasingSubarrayOfCompositeNumbers(arr); // Print the longest increasing subarray // of composite numbers cout << "Longest increasing subarray of composite " "numbers:" ; for ( int i = 0; i < result.size(); i++) { cout << " " << result[i]; } return 0; } |
Java
// Java code for the above approach: import java.util.ArrayList; import java.util.List; public class Main { // Function to check if a number is composite // (has divisors other than 1 and itself) static boolean isComposite( int num) { // Check if the number is less than 2 if (num < 2 ) { // Numbers less than 2 are not // considered composite return false ; } // Iterate through potential divisors // from 2 to num/2 for ( int i = 2 ; i <= num / 2 ; i++) { // If a divisor is found, the number // is composite if (num % i == 0 ) { return true ; } } // If no divisors are found, the number // is not composite return false ; } // Function to find the longest increasing // subarray of composite numbers static List<Integer> longestIncreasingSubarrayOfCompositeNumbers(List<Integer> arr) { int n = arr.size(); int maxLen = 0 , len = 0 , startIndex = - 1 ; for ( int i = 0 ; i < n; i++) { // Check if the current element is composite if (isComposite(arr.get(i))) { // If it's the first element or // greater than the previous, // increment subarray length if (i == 0 || arr.get(i) > arr.get(i - 1 )) { len++; } // Otherwise, start a new subarray else { len = 1 ; } // Update the maximum length if a // longer subarray is found if (len > maxLen) { maxLen = len; // Update the start index // of the longest subarray startIndex = i - len + 1 ; } } else { // Reset the subarray length if the // current element is not composite len = 0 ; } } // If no increasing subarray of composite // numbers is found, return an empty list if (maxLen == 0 ) { return new ArrayList<>(); } List<Integer> result = new ArrayList<>(); // Copy the elements of the longest // subarray into the result list for ( int i = 0 ; i < maxLen; i++) { result.add(arr.get(startIndex + i)); } return result; } // Driver code public static void main(String[] args) { List<Integer> arr = List.of( 10 , 15 , 23 , 9 , 27 , 30 , 45 , 21 , 8 , 12 ); List<Integer> result = longestIncreasingSubarrayOfCompositeNumbers(arr); // Print the longest increasing subarray // of composite numbers System.out.print( "Longest increasing subarray of composite numbers:" ); for ( int i = 0 ; i < result.size(); i++) { System.out.print( " " + result.get(i)); } } } |
Python3
# Function to check if a number is composite # (has divisors other than 1 and itself) def isComposite(num): # Check if the number is less than 2 if num < 2 : # Numbers less than 2 are not considered composite return False # Iterate through potential divisors from 2 to num/2 for i in range ( 2 , num / / 2 + 1 ): # If a divisor is found, the number is composite if num % i = = 0 : return True # If no divisors are found, the number is not composite return False # Function to find the longest increasing subarray of composite numbers def longestIncreasingSubarrayOfCompositeNumbers(arr): n = len (arr) maxLen = 0 length = 0 startIndex = - 1 for i in range (n): # Check if the current element is composite if isComposite(arr[i]): # If it's the first element or greater than the previous, increment subarray length if i = = 0 or arr[i] > arr[i - 1 ]: length + = 1 # Otherwise, start a new subarray else : length = 1 # Update the maximum length if a longer subarray is found if length > maxLen: maxLen = length # Update the start index of the longest subarray startIndex = i - length + 1 # Reset the subarray length if the current element is not composite else : length = 0 # If no increasing subarray of composite numbers is found, return an empty list if maxLen = = 0 : return [] result = [ 0 ] * maxLen # Copy the elements of the longest subarray into the result list for i in range (maxLen): result[i] = arr[startIndex + i] return result # Drivers code arr = [ 10 , 15 , 23 , 9 , 27 , 30 , 45 , 21 , 8 , 12 ] result = longestIncreasingSubarrayOfCompositeNumbers(arr) # Print the longest increasing subarray of composite numbers print ( "Longest increasing subarray of composite numbers:" , end = "") for i in range ( len (result)): print ( " " , result[i], end = "") # This code is contributed by Sakshi |
C#
using System; using System.Collections.Generic; class Program { // Function to check if a number is composite // (has divisors other than 1 and itself) static bool IsComposite( int num) { // Check if the number is less than 2 if (num < 2) { // Numbers less than 2 are not // considered composite return false ; } // Iterate through potential divisors // from 2 to num/2 for ( int i = 2; i <= num / 2; i++) { // If a divisor is found, the number // is composite if (num % i == 0) { return true ; } } // If no divisors are found, the number // is not composite return false ; } // Function to find the longest increasing // subarray of composite numbers static List< int > LongestIncreasingSubarrayOfCompositeNumbers(List< int > arr) { int n = arr.Count; int maxLen = 0, len = 0, startIndex = -1; for ( int i = 0; i < n; i++) { // Check if the current element is composite if (IsComposite(arr[i])) { // If it's the first element or greater than the previous, // increment subarray length if (i == 0 || arr[i] > arr[i - 1]) { len++; } // Otherwise, start a new subarray else { len = 1; } // Update the maximum length if a longer subarray is found if (len > maxLen) { maxLen = len; // Update the start index of the longest subarray startIndex = i - len + 1; } } // Reset the subarray length if the current element is not composite else { len = 0; } } // If no increasing subarray of composite numbers is found, return an empty list if (maxLen == 0) { return new List< int >(); } List< int > result = new List< int >(maxLen); // Copy the elements of the longest subarray into the result list for ( int i = 0; i < maxLen; i++) { result.Add(arr[startIndex + i]); } return result; } // Main method static void Main( string [] args) { List< int > arr = new List< int >() { 10, 15, 23, 9, 27, 30, 45, 21, 8, 12 }; List< int > result = LongestIncreasingSubarrayOfCompositeNumbers(arr); // Print the longest increasing subarray of composite numbers Console.Write( "Longest increasing subarray of composite numbers:" ); foreach ( var num in result) { Console.Write( " " + num); } } } |
Javascript
function GFG(num) { // Check if the number is less than 2 if (num < 2) { // Numbers less than 2 are not considered composite return false ; } // Iterate through potential divisors from 2 to num/2 for (let i = 2; i <= Math.floor(num / 2); i++) { // If a divisor is found // the number is composite if (num % i === 0) { return true ; } } // If no divisors are found // the number is not composite return false ; } // Function to find the longest increasing subarray of composite numbers function CompositeNumbers(arr) { const n = arr.length; let maxLen = 0; let len = 0; let startIndex = -1; for (let i = 0; i < n; i++) { // Check if the current element is composite if (GFG(arr[i])) { // If it's the first element or greater than the previous // increment subarray length if (i === 0 || arr[i] > arr[i - 1]) { len++; } else { len = 1; } // Update the maximum length if a longer subarray is found if (len > maxLen) { maxLen = len; // Update the start index of longest subarray startIndex = i - len + 1; } } else { // Reset the subarray length if the current element is not composite len = 0; } } // If no increasing subarray of composite numbers is found // return an empty array if (maxLen === 0) { return []; } // Copy the elements of the longest subarray into result array const result = []; for (let i = 0; i < maxLen; i++) { result.push(arr[startIndex + i]); } return result; } // Driver Code const arr = [10, 15, 23, 9, 27, 30, 45, 21, 8, 12]; const result = CompositeNumbers(arr); // Print the longest increasing subarray of composite numbers console.log( "Longest increasing subarray of composite numbers:" , result.join( " " )); |
Longest increasing subarray of composite numbers: 9 27 30 45
Time Complexity: O(n * sqrt(max_num)), where n is the number of elements in the input array and max_num is the maximum element in the array, due to iterating through the array and checking if each number is composite.
Axillary space: O(m), where m is the length of the longest increasing subarray of composite numbers. This is because the result vector created at the end will have at most m elements.
Contact Us