Check for Subarray splitting possibility in Prime number
Given a positive integer array arr[] of size N and a prime number p, the task is to form an N number of non-empty subarrays by performing a series of steps. In each step, you can select an existing subarray (which may be the result of previous steps) with a length of at least two and split it into two sub-subarrays, if, for each resulting sub-subarray, at least one of the following holds:
- The length of the sub-subarray is one.
- The sum of elements of any one of the two sub-subarrays is greater than or equal to the given prime number.
Examples:
Input: arr = [2, 5, 8, 3] p = 11
Output: Possible to Split
Explanation: We can split the array into [2] and [5, 8, 3] in the first step. Then, in the second step, we can split [5, 8, 3] into [5] and [8, 3]. and in the last step, we can split [8, 3] into [8] and [3]. As a result, the answer is possible.Input: arr = [4, 2, 1] p = 7
Output: Not possible to split
Explanation: We cannot split the array into two valid subarrays, as none of the valid splitting conditions can satisfy any combination of splitting steps.Input: arr = [2, 4, 5, 7, 4] p = 13
Output: Not possible to split
Approach: To solve the problem follow the below Intuition:
- We just need subarray of length 2 whose sum >= p, through this subarray we can reduce all elements which are present before and after the subarray one by one.
- If N == 2, can split once.
- If N > 2, we must have subarray of length 2 whose arr[i] + arr[i + 1] >= p. Otherwise it is not possible to split the array into N subarrays.
Follow the steps to solve the problem:
- When splitting an array arr[] if we find a case where arr[i] + arr[i+1] >= p we can split the whole array into N parts.
- Since while splitting the array into subarrays we may reach a stage where size of array arr[] is 3 and only way to split the array is when we have sum of 2 consecutive numbers is greater than or equal to p.
Below is the implementation for the above approach:
C++14
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to check if it is // possible to split the array bool isPossibleToSplitArray(vector< int >& arr, int p) { int n = arr.size(); // If the array has 2 or fewer elements, // it is always possible to split it if (n <= 2) return true ; // Iterate through the array to find a pair // of adjacent elements whose sum is >= 'p' for ( int i = 1; i < n; i++) { int sum = arr[i - 1] + arr[i]; if (sum >= p) return true ; } // If no such pair is found, // it is impossible to split // the array as required return false ; } // Driver Code int main() { vector< int > arr = { 2, 5, 8, 3 }; int p = 11; // Call the function to check if it // is possible to split the array bool ans = isPossibleToSplitArray(arr, p); if (ans == true ) cout << "Possible to Split" << endl; else cout << "Not Possible to Split" << endl; return 0; } |
Java
// Java Code import java.io.*; import java.util.ArrayList; import java.util.List; public class Main { // Function to check if it is possible to split the array public static boolean isPossibleToSplitArray(List<Integer> arr, int p) { int n = arr.size(); // If the array has 2 or fewer elements, // it is always possible to split it if (n <= 2 ) { return true ; } // Iterate through the array to find a pair // of adjacent elements whose sum is >= 'p' for ( int i = 1 ; i < n; i++) { int sum = arr.get(i - 1 ) + arr.get(i); if (sum >= p) { return true ; } } // If no such pair is found, // it is impossible to split // the array as required return false ; } public static void main(String[] args) { List<Integer> arr = new ArrayList<>(); arr.add( 2 ); arr.add( 5 ); arr.add( 8 ); arr.add( 3 ); int p = 11 ; // Call the function to check if it // is possible to split the array boolean ans = isPossibleToSplitArray(arr, p); if (ans) { System.out.println( "Possible to Split" ); } else { System.out.println( "Not Possible to Split" ); } } } |
Python3
# Function to check if it is # possible to split the array def is_possible_to_split_array(arr, p): n = len (arr) # If the array has 2 or fewer elements, # it is always possible to split it if n < = 2 : return True # Iterate through the array to find a pair # of adjacent elements whose sum is >= 'p' for i in range ( 1 , n): sum_val = arr[i - 1 ] + arr[i] if sum_val > = p: return True # If no such pair is found, # it is impossible to split # the array as required return False # Driver Code if __name__ = = "__main__" : arr = [ 2 , 5 , 8 , 3 ] p = 11 # Call the function to check if it # is possible to split the array ans = is_possible_to_split_array(arr, p) if ans: print ( "Possible to Split" ) else : print ( "Not Possible to Split" ) |
C#
using System; using System.Collections.Generic; class Program { // Function to check if it is possible to split the list public static bool IsPossibleToSplitList(List< int > list, int p) { int n = list.Count; // If the list has 2 or fewer elements, // it is always possible to split it if (n <= 2) { return true ; } // Iterate through the list to find a pair // of adjacent elements whose sum is >= 'p' for ( int i = 1; i < n; i++) { int sum = list[i - 1] + list[i]; if (sum >= p) { return true ; } } // If no such pair is found, // it is impossible to split // the list as required return false ; } public static void Main( string [] args) { List< int > list = new List< int > { 2, 5, 8, 3 }; int p = 11; // Call the function to check if it // is possible to split the list bool isPossible = IsPossibleToSplitList(list, p); if (isPossible) { Console.WriteLine( "Possible to Split" ); } else { Console.WriteLine( "Not Possible to Split" ); } } } |
Javascript
// Function to check if it is possible to split the array function isPossibleToSplitArray(arr, p) { const n = arr.length; // If the array has 2 or fewer elements, // it is always possible to split it if (n <= 2) { return true ; } // Iterate through the array to find a pair // of adjacent elements whose sum is >= 'p' for (let i = 1; i < n; i++) { const sum = arr[i - 1] + arr[i]; if (sum >= p) { return true ; } } // If no such pair is found, // it is impossible to split // the array as required return false ; } // Driver Code function main() { const arr = [2, 5, 8, 3]; const p = 11; // Call the function to check if it // is possible to split the array const ans = isPossibleToSplitArray(arr, p); if (ans) { console.log( "Possible to Split" ); } else { console.log( "Not Possible to Split" ); } } main(); // Call the main function to execute the code |
Possible to Split
Time Complexity: O(n), where n is the length of the array
Auxiliary Space: O(1), no extra space is required, so it is a constant.