Minimum index to split array into subarrays with co-prime products
Given an array arr[] consisting of N integers, the task is to find the maximum index K such that the product of subarrays {arr[0], arr[K]} and {arr[K + 1], arr[N – 1]} are co-prime. If no such index exists, then print “-1”.
Examples:
Input: arr[] = {2, 3, 4, 5}
Output: 2
Explanation:
Smallest index for partition is 2.
Product of left subarray is = 2 * 3 * 4 = 24.
Product of right subarray = 5.
Since 24 and 5 are co-prime, the required answer is 2.Input: arr[] = {23, 41, 52, 83, 7, 13}
Output: 0
Explanation:
Smallest index for partition is 0.
Product of left subarray = 23.
Product of right subarray = 41 * 52 * 83 * 7 * 13 = 16102996.
Since 23 and 16102996 are co-prime, the answer is 0.
Naive Approach: The simplest approach is to check all possible indexes of partition from the start of the array and check if the product of the subarrays formed is co-prime or not. If there exists any such index then print that index. Otherwise, print “-1”.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Better Approach: To optimize the above approach, the idea is to use the prefix product array and suffix product array and find the possible index. Follow the steps below to solve the problem:
- Create two auxiliary arrays, prefix[] and suffix[] to store the prefix and suffix array product. Initialize prefix[0] to arr[0] and suffix[N – 1] to arr[N – 1].
- Traverse the given array over the range [2, N] using variable i and update the prefix array as prefix[i] = prefix[i – 1]*arr[i].
- Traverse the given array from the back over the range [N – 2, 0] using variable i and update the suffix array as suffix[i] = suffix[i + 1]*arr[i].
- Iterate a loop over the range [0, N – 1] using variable i and check if prefix[i] and suffix[i + 1] are co-prime or not. If found to be true the print the current index and break out of the loop.
- If there doesn’t exist any such index in the above step then print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the GCD of 2 numbers int GCD( int a, int b) { // Base Case if (b == 0) return a; // Find the GCD recursively return GCD(b, a % b); } // Function to find the minimum partition // index K s.t. product of both subarrays // around that partition are co-prime int findPartition( int nums[], int N) { // Stores the prefix and suffix // array product int prefix[N], suffix[N], i, k; prefix[0] = nums[0]; // Update the prefix array for (i = 1; i < N; i++) { prefix[i] = prefix[i - 1] * nums[i]; } suffix[N - 1] = nums[N - 1]; // Update the suffix array for (i = N - 2; i >= 0; i--) { suffix[i] = suffix[i + 1] * nums[i]; } // Iterate the given array for (k = 0; k < N - 1; k++) { // Check if prefix[k] and // suffix[k+1] are co-prime if (GCD(prefix[k], suffix[k + 1]) == 1) { return k; } } // If no index for partition // exists, then return -1 return -1; } // Driver Code int main() { int arr[] = { 2, 3, 4, 5 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << findPartition(arr, N); return 0; } |
Java
// Java program for the // above approach import java.util.*; class solution{ // Function to find the // GCD of 2 numbers static int GCD( int a, int b) { // Base Case if (b == 0 ) return a; // Find the GCD // recursively return GCD(b, a % b); } // Function to find the minimum // partition index K s.t. product // of both subarrays around that // partition are co-prime static int findPartition( int nums[], int N) { // Stores the prefix and // suffix array product int []prefix = new int [N]; int []suffix = new int [N]; int i, k; prefix[ 0 ] = nums[ 0 ]; // Update the prefix array for (i = 1 ; i < N; i++) { prefix[i] = prefix[i - 1 ] * nums[i]; } suffix[N - 1 ] = nums[N - 1 ]; // Update the suffix array for (i = N - 2 ; i >= 0 ; i--) { suffix[i] = suffix[i + 1 ] * nums[i]; } // Iterate the given array for (k = 0 ; k < N - 1 ; k++) { // Check if prefix[k] and // suffix[k+1] are co-prime if (GCD(prefix[k], suffix[k + 1 ]) == 1 ) { return k; } } // If no index for partition // exists, then return -1 return - 1 ; } // Driver Code public static void main(String args[]) { int arr[] = { 2 , 3 , 4 , 5 }; int N = arr.length; // Function call System.out.println(findPartition(arr, N)); } } // This code is contributed by SURENDRA_GANGWAR |
Python3
# Python3 program for the # above approach # Function to find the # GCD of 2 numbers def GCD(a, b): # Base Case if (b = = 0 ): return a # Find the GCD recursively return GCD(b, a % b) # Function to find the minimum # partition index K s.t. product # of both subarrays around that # partition are co-prime def findPartition(nums, N): #Stores the prefix and # suffix array product prefix = [ 0 ] * N suffix = [ 0 ] * N prefix[ 0 ] = nums[ 0 ] # Update the prefix # array for i in range ( 1 , N): prefix[i] = (prefix[i - 1 ] * nums[i]) suffix[N - 1 ] = nums[N - 1 ] # Update the suffix array for i in range (N - 2 , - 1 , - 1 ): suffix[i] = (suffix[i + 1 ] * nums[i]) # Iterate the given array for k in range (N - 1 ): # Check if prefix[k] and # suffix[k+1] are co-prime if (GCD(prefix[k], suffix[k + 1 ]) = = 1 ): return k # If no index for partition # exists, then return -1 return - 1 # Driver Code if __name__ = = '__main__' : arr = [ 2 , 3 , 4 , 5 ] N = len (arr) # Function call print (findPartition(arr, N)) # This code is contributed by Mohit Kumar 29 |
C#
// C# program for the // above approach using System; class GFG{ // Function to find the // GCD of 2 numbers static int GCD( int a, int b) { // Base Case if (b == 0) return a; // Find the GCD // recursively return GCD(b, a % b); } // Function to find the minimum // partition index K s.t. product // of both subarrays around that // partition are co-prime static int findPartition( int [] nums, int N) { // Stores the prefix and // suffix array product int [] prefix = new int [N]; int [] suffix = new int [N]; int i, k; prefix[0] = nums[0]; // Update the prefix array for (i = 1; i < N; i++) { prefix[i] = prefix[i - 1] * nums[i]; } suffix[N - 1] = nums[N - 1]; // Update the suffix array for (i = N - 2; i >= 0; i--) { suffix[i] = suffix[i + 1] * nums[i]; } // Iterate the given array for (k = 0; k < N - 1; k++) { // Check if prefix[k] and // suffix[k+1] are co-prime if (GCD(prefix[k], suffix[k + 1]) == 1) { return k; } } // If no index for partition // exists, then return -1 return -1; } // Driver code static void Main() { int [] arr = {2, 3, 4, 5}; int N = arr.Length; // Function call Console.WriteLine(findPartition(arr, N)); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // JavaScript program for the above approach // Function to find the GCD of 2 numbers function GCD(a, b) { // Base Case if (b == 0) return a; // Find the GCD recursively return GCD(b, a % b); } // Function to find the minimum partition // index K s.t. product of both subarrays // around that partition are co-prime function findPartition(nums, N) { // Stores the prefix and suffix // array product var prefix = Array(N), suffix = Array(N), i, k; prefix[0] = nums[0]; // Update the prefix array for (i = 1; i < N; i++) { prefix[i] = prefix[i - 1] * nums[i]; } suffix[N - 1] = nums[N - 1]; // Update the suffix array for (i = N - 2; i >= 0; i--) { suffix[i] = suffix[i + 1] * nums[i]; } // Iterate the given array for (k = 0; k < N - 1; k++) { // Check if prefix[k] and // suffix[k+1] are co-prime if (GCD(prefix[k], suffix[k + 1]) == 1) { return k; } } // If no index for partition // exists, then return -1 return -1; } // Driver Code var arr = [2, 3, 4, 5]; var N = arr.length; // Function call document.write( findPartition(arr, N)); </script> |
2
Time Complexity: O(N log(N))
Auxiliary Space: O(N)
Efficient Approach: Above approach is using a prefix array and suffix array that stores the product of numbers , if the product of numbers exceeds the integer maximum value then it will lead to overflow , hence a different approach is needed such that it will work for every numbers that are present in the array. Follow the steps below to solve the problem:
- Create a frequency map total_freq that will store the count of all the prime factors of numbers that are present in the array using the primeFreq function that will calculate prime factors of number.
- Create an another frequency map curr_freq that will store the count of prime factors of current numbers of array.
- Iterate over array elements and create a boolean flg with value set to true and store the current prime divisors of number in curr_freq map. Then Iterate over the map curr_freq and check if the current prime factor count in curr_freq map and total_freq map are equal or not. If it is not equal then set flg to false and stop iteration of the curr_freq map and break.
- After that check if flg is true then return the value of current array element’s index that is giving this result.
- If there doesn’t exist any such index then print “-1“.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; void primeFreq( int x, unordered_map< int , int >& freq) { // Time Complexity - O(sqrt(x)) int temp = x; for ( int i = 2; i <= sqrt (x); i++) { while (temp % i == 0) { freq[i]++; temp /= i; } } if (temp > 1) { freq[temp]++; } } int findValidSplit(vector< int >& nums) { // Time Complexity - O(n) unordered_map< int , int > freq; for ( auto i : nums) { primeFreq(i, freq); } unordered_map< int , int > curr_freq; for ( int i = 0; i < nums.size(); i++) { primeFreq(nums[i], curr_freq); bool f = true ; for ( auto j : curr_freq) { if (freq[j.first] - j.second > 0) { f = false ; break ; } } if (f && i != nums.size() - 1) return i; } return -1; } int main() { vector< int > arr(4); // arr[4]={2,3,4,5} arr[0] = 2; arr[1] = 3; arr[2] = 4; arr[3] = 5; // Function call cout << findValidSplit(arr); return 0; } |
Java
import java.util.*; public class Main { public static void primeFreq( int x, HashMap<Integer, Integer> freq) { int temp = x; for ( int i = 2 ; i <= Math.sqrt(x); i++) { while (temp % i == 0 ) { freq.put(i, freq.getOrDefault(i, 0 ) + 1 ); temp /= i; } } if (temp > 1 ) { freq.put(temp, freq.getOrDefault(temp, 0 ) + 1 ); } } public static int findValidSplit(ArrayList<Integer> nums) { HashMap<Integer, Integer> freq = new HashMap<>(); for ( int i : nums) { primeFreq(i, freq); } HashMap<Integer, Integer> currFreq = new HashMap<>(); for ( int i = 0 ; i < nums.size(); i++) { primeFreq(nums.get(i), currFreq); boolean f = true ; for (Map.Entry<Integer, Integer> entry : currFreq.entrySet()) { int key = entry.getKey(); int value = entry.getValue(); if (freq.getOrDefault(key, 0 ) - value > 0 ) { f = false ; break ; } } if (f && i != nums.size() - 1 ) return i; } return - 1 ; } public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>(); arr.add( 2 ); arr.add( 3 ); arr.add( 4 ); arr.add( 5 ); // Function call System.out.println(findValidSplit(arr)); } } |
Python3
from math import sqrt from collections import defaultdict def primeFreq(x, freq): # This function finds the prime factors of a # number and updates their frequency in the freq dictionary temp = x i = 2 while i < = sqrt(x): while temp % i = = 0 : freq[i] + = 1 temp / / = i i + = 1 if temp > 1 : freq[temp] + = 1 def findValidSplit(nums): # This function finds a valid split # index in the given list of numbers # Time Complexity - O(n) # Find the frequency of prime factors # of all numbers in the list freq = defaultdict( int ) for i in nums: primeFreq(i, freq) curr_freq = defaultdict( int ) for i in range ( len (nums)): # Find the frequency of prime factors of the current number primeFreq(nums[i], curr_freq) f = True for j in curr_freq.items(): # Check if the frequency of any prime factor # is greater than its frequency in the rest of the list if freq[j[ 0 ]] - j[ 1 ] > 0 : f = False break # If all prime factors have equal frequency, # return the current index as a valid split index if f and i ! = len (nums) - 1 : return i # If no valid split index is found, return -1 return - 1 arr = [ 2 , 3 , 4 , 5 ] print (findValidSplit(arr)) |
C#
using System; using System.Collections.Generic; class MainClass { // Function to calculate the prime factorization of a number and update a frequency dictionary public static void PrimeFreq( int x, Dictionary< int , int > freq) { int temp = x; for ( int i = 2; i * i <= x; i++) { while (temp % i == 0) { // If the factor is already in the frequency dictionary, increment its count if (freq.ContainsKey(i)) { freq[i]++; } else { // If the factor is not in the dictionary, add it with a count of 1 freq[i] = 1; } temp /= i; } } // If there's a remaining prime factor greater than 1, update the frequency dictionary if (temp > 1) { if (freq.ContainsKey(temp)) { freq[temp]++; } else { freq[temp] = 1; } } } // Function to find the index where a valid split can occur public static int FindValidSplit(List< int > nums) { // Create a dictionary to store the prime factorization frequency of the entire list Dictionary< int , int > freq = new Dictionary< int , int >(); // Calculate the prime factorization of each number in the list and update the frequency dictionary foreach ( int num in nums) { PrimeFreq(num, freq); } // Initialize a temporary frequency dictionary Dictionary< int , int > currFreq = new Dictionary< int , int >(); // Iterate through the list for ( int i = 0; i < nums.Count; i++) { // Calculate the prime factorization of the current number and store it in the temporary dictionary PrimeFreq(nums[i], currFreq); bool isValidSplit = true ; // Compare the prime factorization of the current number with the frequency dictionary foreach (KeyValuePair< int , int > entry in currFreq) { int key = entry.Key; int value = entry.Value; // Check if there are enough prime factors of this type in the original frequency dictionary if (freq.ContainsKey(key) && freq[key] - value > 0) { isValidSplit = false ; break ; } } // If it's a valid split and not the last element, return the current index if (isValidSplit && i != nums.Count - 1) { return i; } } // If no valid split is found, return -1 return -1; } public static void Main( string [] args) { // Create a list of integers List< int > arr = new List< int >(); arr.Add(2); arr.Add(3); arr.Add(4); arr.Add(5); // Call the FindValidSplit function and print the result Console.WriteLine(FindValidSplit(arr)); } } |
Javascript
// Javascript code addition // Function, finds the frequency of prime numbers less than equal to x. function primeFreq(x, freq) { // Time Complexity - O(sqrt(x)) let temp = x; for (let i = 2; i <= Math.sqrt(x); i++) { while (temp % i === 0) { freq[i]++; temp = Math.floor(temp/x); } } if (temp > 1) { if (freq[temp]) freq[temp]++; else freq[temp] = 1; } } // The function returns a valid split in the array. function findValidSplit(nums) { // Time Complexity - O(n) const freq = {}; for (let i = 0; i < nums.length; i++) { primeFreq(nums[i], freq); } const currFreq = {}; for (let i = 0; i < nums.length; i++) { primeFreq(nums[i], currFreq); let f = true ; for (const j in currFreq) { if (freq[j] - currFreq[j] > 0) { f = false ; break ; } } if (f && i !== nums.length - 1) { return i; } } return -1; } // Driver code let arr = new Array(4); // arr ={2,3,4,5} arr[0] = 2; arr[1] = 3; arr[2] = 4; arr[3] = 5; // Function call console.log(findValidSplit(arr)); // The code is contributed by Arushi Goel. |
Output
2
Time Complexity: O(N*sqrt(N))
Auxiliary Space: O(N)