Skip to main content

Hashing

Split the Array to Make Coprime Products Solution In C++/Java/Python/Javascript

Problem Description

You are given a 0-indexed integer array nums of length n.
A split at an index i where 0 <= i <= n - 2 is called valid if the product of the first i + 1 elements and the product of the remaining elements are coprime.

For example, if nums = [2, 3, 3], then a split at the index i = 0 is valid because 2 and 9 are coprime, while a split at the index i = 1 is not valid because 6 and 3 are not coprime. A split at the index i = 2 is not valid because i == n - 1.

Return the smallest index i at which the array can be split validly or -1 if there is no such split.
Two values val1 and val2 are coprime if gcd(val1, val2) == 1 where gcd(val1, val2) is the greatest common divisor of val1 and val2.

Examples:

Input : nums = [4,7,8,15,3,5]
Output : 2
Explanation: The table above shows the values of the product of the first i + 1 elements, the remaining elements, and their gcd at each index i.
The only valid split is at index 2.

Input: nums = [4,7,15,8,3,5]
Output: -1
Explanation: The table above shows the values of the product of the first i + 1 elements, the remaining elements, and their gcd at each index i.
There is no valid split.

Constraints

  • n == nums.length
  • 1 <= n <= 10^4
  • 1 <= nums[i] <= 10^6
💡
Try it Yourself First!
This problem is an intriguing exploration of array splitting and coprime conditions. The challenge lies in efficiently finding the smallest index where the product of the left subarray and the product of the right subarray are coprime. The key insight revolves around leveraging the properties of prime factors and the greatest common divisor (GCD) to ensure the two products share no common factors, making the split valid

Brute Force Approach

Intuition

The brute force approach to solving this problem is based on systematically checking every possible way to split the array and verifying whether the two resulting parts are coprime. The core idea is that for a split to be valid, the product of numbers in the first part should share no common factors with the product of numbers in the second part. Since there are multiple ways to split the array, we need to explore each possibility and determine the smallest valid split index.

To approach this, we consider all possible positions where the array can be divided into two subarrays. For each split position, we analyze the numbers on the left and the numbers on the right separately. The key observation is that if the two groups do not share any prime factors, their greatest common divisor (GCD) will be 1, meaning they are coprime. If such a split exists, we take note of the first occurrence where this condition holds.

Since we are dealing with products of numbers, an important challenge is that multiplication can grow extremely large, leading to computational inefficiencies. However, conceptually, the approach remains simple: check each split, determine the two products, and verify if their GCD is 1. If we find a valid split, we stop immediately and return the index; otherwise, we continue checking until the end of the array.

Approach

Step 1: Read input and initialize the solution class

First, we take input for the size of the array n and then read the n elements into a vector named nums. We also create an instance of the Solution class to call the function that determines the valid split.

Step 2: Iterate through all possible split points

We loop through all possible split indices i, starting from 0 and going up to n - 2. At each index, we consider splitting the array into two parts: the first i+1 elements and the remaining elements.

Step 3: Compute the product of elements in the first part

For each possible split index, we calculate the product of the first i+1 elements and store it in prod1. This represents the product of numbers from index 0 to i.

Step 4: Compute the product of elements in the second part

Similarly, we compute the product of the remaining elements (from index i+1 to n-1) and store it in prod2. This represents the product of numbers from index i+1 to the end of the array.

Step 5: Check if the two products are coprime

We use the gcd function to check if prod1 and prod2 are coprime. If gcd(prod1, prod2) == 1, it means the two parts do not share any common prime factors, making this a valid split. In this case, we return the index i as the answer.

Step 6: Return -1 if no valid split is found

If we complete the loop without finding a valid split, it means no such index exists, and we return -1. This indicates that there is no way to split the array while ensuring the two parts are coprime.

Split the Array to Make Coprime Products Dry run - BruteForce

nums = [4, 7, 8, 15, 3, 5]
Step 1: i = 0

  • prod1: 4 (first element).
  • prod2: 7 * 8 * 15 * 3 * 5 = 12600.
  • gcd(4, 12600): 4 (not coprime).
  • Result: Not valid.

Step 2: i = 1

  • prod1: 4 * 7 = 28.
  • prod2: 8 * 15 * 3 * 5 = 1800.
  • gcd(28, 1800): 4 (not coprime).
  • Result: Not valid.

Step 3: i = 2

  • prod1: 4 * 7 * 8 = 224.
  • prod2: 15 * 3 * 5 = 225.
  • gcd(224, 225): 1 (coprime).
  • Result: Valid split at index 2.

Step 4: i = 3

  • prod1: 4 * 7 * 8 * 15 = 3360.
  • prod2: 3 * 5 = 15.
  • gcd(3360, 15): 15 (not coprime).
  • Result: Not valid.

Step 5: i = 4

  • prod1: 4 * 7 * 8 * 15 * 3 = 10080.
  • prod2: 5 (last element).
  • gcd(10080, 5): 5 (not coprime).
  • Result: Not valid.

Final Output

The smallest valid split index is 2.

Split the Array to Make Coprime - Code for All Languages
C++ 
#include <iostream>
#include <vector>
#include <numeric>  // for gcd
using namespace std;

class Solution {
public:
    int findValidSplit(vector<int>& nums) {
        int n = nums.size();
        
        for (int i = 0; i < n - 1; i++) {
            long long prod1 = 1, prod2 = 1;

            // Compute product of first i+1 elements
            for (int j = 0; j <= i; j++) {
                prod1 *= nums[j];
            }

            // Compute product of remaining elements
            for (int j = i + 1; j < n; j++) {
                prod2 *= nums[j];
            }

            // Check if they are coprime
            if (gcd(prod1, prod2) == 1) {
                return i;
            }
        }

        return -1;
    }
};

int main() {
    int n;
    cin >> n;  // Read array size
    vector<int> nums(n);
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];  // Read array elements
    }
    
    Solution sol;
    cout << sol.findValidSplit(nums) << endl;  // Output the result
    return 0;
}

Split the Array to Make Coprime code in Java - Brute Force 
import java.util.*;

class Solution {
    public int findValidSplit(int[] nums) {
        int n = nums.length;
        
        for (int i = 0; i < n - 1; i++) {
            long prod1 = 1, prod2 = 1;

            // Compute product of first i+1 elements
            for (int j = 0; j <= i; j++) {
                prod1 *= nums[j];
            }

            // Compute product of remaining elements
            for (int j = i + 1; j < n; j++) {
                prod2 *= nums[j];
            }

            // Check if they are coprime
            if (gcd(prod1, prod2) == 1) {
                return i;
            }
        }

        return -1;
    }

    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        Solution sol = new Solution();
        System.out.println(sol.findValidSplit(nums));

        sc.close();
    }
}

Split the Array to Make Coprime code in Python - Brute Force 
import math

class Solution:
    def findValidSplit(self, nums):
        n = len(nums)
        
        for i in range(n - 1):
            prod1 = 1
            prod2 = 1

            # Compute product of first i+1 elements
            for j in range(i + 1):
                prod1 *= nums[j]

            # Compute product of remaining elements
            for j in range(i + 1, n):
                prod2 *= nums[j]

            # Check if they are coprime
            if math.gcd(prod1, prod2) == 1:
                return i
        
        return -1

if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))

    sol = Solution()
    print(sol.findValidSplit(nums))

Split the Array to Make Coprime code in JavaScript - Brute Force 
class Solution {
    fourSumCount(nums1, nums2, nums3, nums4) {
        // Initialize count to keep track of valid quadruplets
        let count = 0;
        
        // Brute force: Check all possible quadruplets by using four nested loops
        for (let a of nums1) {
            for (let b of nums2) {
                for (let c of nums3) {
                    for (let d of nums4) {
                        // Calculate the sum of the four selected numbers
                        if (a + b + c + d === 0) {
                            // Increment the count for every valid quadruplet
                            count++;
                        }
                    }
                }
            }
        }
        
        // Return the final count of valid quadruplets
        return count;
    }
}

// Input handling in JavaScript
let nums1 = [];
let nums2 = [];
let nums3 = [];
let nums4 = [];

let n = parseInt(prompt());
nums1 = prompt().split(' ').map(Number);

n = parseInt(prompt());
nums2 = prompt().split(' ').map(Number);

n = parseInt(prompt());
nums3 = prompt().split(' ').map(Number);

n = parseInt(prompt());
nums4 = prompt().split(' ').map(Number);

// Create Solution object to call the fourSumCount method
let sol = new Solution();
let result = sol.fourSumCount(nums1, nums2, nums3, nums4);

// Output the result
console.log(result);

Time Complexity : O(n^2 log(max product))

The brute-force approach iterates through all possible split indices i (from 0 to n−2). For each index i, we:

  1. Compute the product of the first i+1 elements → O(i+1)
  2. Compute the product of the remaining n−i−1 elements → O(n−i−1)
  3. Compute the GCD of the two products → O(log⁡(max⁡ product))

In the worst case, when iterating through all ii, we sum up the complexities: O(1+2+⋯+(n−1))=O(n^2)
Since computing the GCD takes O(log⁡product), the final time complexity is: O(n^2log⁡(max⁡ product))

Space Complexity : O(1)

Auxiliary Space : O(1)
The only extra space used in this brute-force approach is for the variables:
prod1, prod2 (each using O(1) space)
Loop variables and function stack frames (also O(1))

Total Space Complexity : O(n)
The input array nums itself takes O(n) space.

Why the Brute-Force Approach Won’t Work Efficiently?

Time Complexity is Too High
The brute-force approach iterates over all possible split indices and computes:

  • Product of first i+1 elements → O(i+1)
  • Product of remaining elements → O(n−i−1)
  • GCD computation → O(log⁡(max product))

Summing over all possible i values, the total time complexity is:O(n^2log⁡(max product))
For large n, this becomes too slow. For example, if n = 10^5, the quadratic nature means billions of operations, making it infeasible.

Integer Overflow
Since we are multiplying multiple numbers together, the product grows exponentially.

  • For an array like [1000, 1000, 1000, ..., 1000], the product reaches 10^300 for n = 300, which exceeds standard data type limits (even long long in C++ or long in Java).
  • In Python, integers can grow arbitrarily large, but computing gcd of such huge numbers is computationally expensive.

Unnecessary Product Computation
Recomputing the product from scratch for each i is wasteful.

  • We can avoid recomputation by keeping track of prefix products and suffix products instead.
  • Instead of multiplying all elements from the beginning every time, we can update the values incrementally.

Optimal Approach

Intuition

The core idea behind this approach is to determine a valid split by analyzing the prime factors of the numbers in the array. Instead of computing the product of the two partitions directly (which would be computationally expensive due to large values), we use prime factorization to track shared factors. The goal is to find the smallest index where the left and right partitions do not share any prime factors, ensuring their greatest common divisor (GCD) is 1.

To efficiently determine prime factors, we first use the Sieve of Eratosthenes to precompute all prime numbers up to a large limit. This allows us to quickly factorize each number in the array. For each element in nums, we extract its prime factors and maintain a frequency map to track how many times each prime factor appears across the entire array. This helps in determining when a prime factor completely leaves the left partition as we iterate through the array.

As we traverse nums, we maintain a set of "active primes," which represents prime factors that are still present in both partitions. We decrement the count of each prime factor in our frequency map as it moves from the right partition to the left. If at any point the set of active primes becomes empty, it means that the left and right partitions no longer share any prime factors, making that index a valid split point.

By leveraging prime factorization instead of direct multiplication, we avoid overflow and unnecessary computations. The use of a set to track active primes allows us to efficiently determine when all shared prime factors are removed, leading to an optimal solution. This approach ensures that we find the valid split, if it exists, in a computationally efficient manner.

Approach

Step 1: Initialize Sieve of Eratosthenes

Before processing the array, we use the Sieve of Eratosthenes to generate all prime numbers up to 10^6. This helps in efficient prime factorization later.

  • We initialize a vector p where p[i] = 1 means i is prime.
  • We iterate through numbers from 2 to 10^6, marking multiples of each prime as non-prime.
  • All prime numbers are stored in the primes list.

Step 2: Precompute Prime Factor Counts

To determine when a valid split occurs, we need to track the count of prime factors across the entire array.

  • We initialize a map mp, which stores the frequency of each prime factor across all elements of nums.
  • For each number x in nums, we perform prime factorization using the precomputed primes.
  • If x is divisible by a prime, we repeatedly divide x by that prime and update mp.
  • If after division x > 1, it means x itself is a prime factor and should be counted.

Step 3: Process the Array to Find a Valid Split

We iterate over nums to determine where we can split the array such that the left and right halves are coprime.

  • We maintain a set activePrimes, which tracks the prime factors currently in both halves.
  • For each number x in nums (processing from left to right):
  • We extract its prime factors and add them to activePrimes.
  • We decrement their count in mp (as they move from the right partition to the left).
  • If any prime’s count in mp reaches zero, it means that prime is no longer present in the right partition, so we remove it from activePrimes.
  • If at any index, activePrimes becomes empty, it means the two partitions no longer share any prime factors. That index is the valid split point.

Step 4: Return the Valid Split Index

  • If we find an index where activePrimes becomes empty, we return it as the valid split.
  • If no valid split is found after checking all indices, return -1.

Dry Run

Step 1: Compute Prime Numbers using Sieve of Eratosthenes

  • The algorithm finds all prime numbers up to 106106.
  • The relevant primes for this test case are 2, 3, 5, 7, 11, 13.

Step 2: Prime Factorization of the Entire Array

  • The algorithm counts the occurrences of prime factors in nums.

Processing 4:

  • 4=22, so mp[2] = 2.

Processing 7:

  • 7=71, so mp[7] = 1.

Processing 8:

  • 8=23, so mp[2] = 5.

Processing 15:

  • 15=31×51, so mp[3] = 1 and mp[5] = 1.

Processing 3:

  • 3=31, so mp[3] = 2.

Processing 5:

  • 5=51, so mp[5] = 2.

At this point, mp = {2: 5, 7: 1, 3: 2, 5: 2}.

Step 3: Finding the Valid Split

  • The algorithm processes each number from left to right while maintaining a set of prime factors.
  • If all prime factors are removed from mp at any point, that index is the valid split.

Processing 4:

  • 4=22, so se = {2}.
  • mp[2] = 3 after decrementing.

Processing 7:

  • 7=71, so se = {2, 7}.
  • mp[7] = 0, so se = {2}.

Processing 8:

  • 8=23, so se = {2}.
  • mp[2] = 0, so se is empty.
  • Since se.size() == 0, return index 2 (0-based).

Thus, the valid split index is 2.

Split the Array to Make Coprime Code for All Languages - Optimised
C++ 
#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;

const int N = 1e6 + 10;
vector<int> p(N, 1), primes;

class Solution {
public:
    
    // Sieve of Eratosthenes to calculate primes up to N
    void seive() {
        
        // Iterate over numbers to find primes
        for (int i = 2; i < N; i++) {
            
            // Skip if the number is already marked as non-prime
            if (p[i] != 1) continue;  
            
            // Add prime number to the list
            primes.push_back(i);  
            
            // Mark multiples of the prime as non-prime
            for (int j = 2 * i; j < N; j += i) {
                p[j] = 0;
            }
        }
    }

    
    // Function to find the valid split index in the array
    int findValidSplit(vector<int>& nums) {
        
        // Mark 2 as non-prime to avoid unnecessary computation
        p[2] = 1;  
        
        // Run sieve to precompute primes
        seive();    

        
        // Frequency map to store the prime factor counts for numbers in nums
        map<int, int> mp;
        
        // For each number in nums, calculate its prime factors
        for (int x : nums) {
            
            // For each prime, divide the number by it if divisible
            for (int prime : primes) {
                
                // Break if prime squared is greater than the current number
                if (prime * prime > x) {
                    
                    // If number is greater than 1, add it to the map
                    if (x > 1) mp[x]++;
                    break;
                }
                
                // While divisible by prime, keep dividing and updating the map
                while (x % prime == 0) {
                    mp[prime]++;
                    x /= prime;
                }
            }
        }

        
        // Set to track active primes for the current split
        set<int> activePrimes;

        
        // Loop through nums to find the valid split index
        for (int i = 0; i < nums.size() - 1; i++) {
            
            // Take the current element from the array
            int x = nums[i];
            
            // For each prime, check its factors for the current element
            for (int prime : primes) {
                
                // Break if prime squared is greater than the current number
                if (prime * prime > x) {
                    
                    // If x is greater than 1, add it to activePrimes
                    if (x > 1) {
                        activePrimes.insert(x);
                        
                        // Decrease count in the map and remove from activePrimes if count reaches 0
                        mp[x]--;
                        if (mp[x] == 0) activePrimes.erase(x);
                    }
                    break;
                }
                
                // While divisible by prime, update activePrimes and map
                while (x % prime == 0) {
                    activePrimes.insert(prime);
                    mp[prime]--;
                    if (mp[prime] == 0) activePrimes.erase(prime);
                    x /= prime;
                }
            }

            
            // If no active primes, it means there's a valid split at this index
            if (activePrimes.empty()) {
                return i;
            }
        }

        
        // Return -1 if no valid split is found
        return -1;  
    }
};

int main() {
    
    Solution solution;

    
    int n;
    cin >> n;  // Input the size of the array

    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];  // Input the array elements
    }

    
    int result = solution.findValidSplit(nums);  // Call the function to find valid split index
    cout << result << endl;  // Output the result

    return 0;
}

Split the Array to Make Coprime code in Java - Optimised 
import java.util.*;

public class Solution {
    
    final int N = (int)1e6 + 10;
    boolean[] p = new boolean[N];
    List<Integer> primes = new ArrayList<>();
    
    // Sieve of Eratosthenes to calculate primes up to N
    public void seive() {
        
        // Iterate over numbers to find primes
        for (int i = 2; i < N; i++) {
            
            // Skip if the number is already marked as non-prime
            if (p[i]) continue;
            
            // Add prime number to the list
            primes.add(i);
            
            // Mark multiples of the prime as non-prime
            for (int j = 2 * i; j < N; j += i) {
                p[j] = true;
            }
        }
    }
    
    // Function to find the valid split index in the array
    public int findValidSplit(int[] nums) {
        
        // Mark 2 as non-prime to avoid unnecessary computation
        p[2] = true;
        
        // Run sieve to precompute primes
        seive();
        
        // Frequency map to store the prime factor counts for numbers in nums
        Map<Integer, Integer> mp = new HashMap<>();
        
        // For each number in nums, calculate its prime factors
        for (int x : nums) {
            
            // For each prime, divide the number by it if divisible
            for (int prime : primes) {
                
                // Break if prime squared is greater than the current number
                if (prime * prime > x) {
                    
                    // If number is greater than 1, add it to the map
                    if (x > 1) mp.put(x, mp.getOrDefault(x, 0) + 1);
                    break;
                }
                
                // While divisible by prime, keep dividing and updating the map
                while (x % prime == 0) {
                    mp.put(prime, mp.getOrDefault(prime, 0) + 1);
                    x /= prime;
                }
            }
        }
        
        // Set to track active primes for the current split
        Set<Integer> activePrimes = new HashSet<>();
        
        // Loop through nums to find the valid split index
        for (int i = 0; i < nums.length - 1; i++) {
            
            // Take the current element from the array
            int x = nums[i];
            
            // For each prime, check its factors for the current element
            for (int prime : primes) {
                
                // Break if prime squared is greater than the current number
                if (prime * prime > x) {
                    
                    // If x is greater than 1, add it to activePrimes
                    if (x > 1) {
                        activePrimes.add(x);
                        
                        // Decrease count in the map and remove from activePrimes if count reaches 0
                        mp.put(x, mp.get(x) - 1);
                        if (mp.get(x) == 0) activePrimes.remove(x);
                    }
                    break;
                }
                
                // While divisible by prime, update activePrimes and map
                while (x % prime == 0) {
                    activePrimes.add(prime);
                    mp.put(prime, mp.get(prime) - 1);
                    if (mp.get(prime) == 0) activePrimes.remove(prime);
                    x /= prime;
                }
            }
            
            // If no active primes, it means there's a valid split at this index
            if (activePrimes.isEmpty()) {
                return i;
            }
        }
        
        // Return -1 if no valid split is found
        return -1;
    }

    public static void main(String[] args) {
        
        Solution solution = new Solution();
        
        // Input size of array
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        
        // Input array elements
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        
        // Call the function to find valid split index and output result
        int result = solution.findValidSplit(nums);
        System.out.println(result);
    }
}

Split the Array to Make Coprime code in Python - Optimised 
class Solution:
    def __init__(self):
        # Define the upper limit for the sieve
        self.N = int(1e6) + 10
        
        # Boolean array to mark prime numbers
        self.p = [1] * self.N
        
        # List to store prime numbers
        self.primes = []

    # Sieve of Eratosthenes to calculate primes up to N
    def seive(self):
        
        # Iterate over numbers to mark primes
        for i in range(2, self.N):
            
            # Skip if the number is already marked as non-prime
            if self.p[i] != 1:
                continue
            
            # Add prime number to the list
            self.primes.append(i)
            
            # Mark multiples of the prime as non-prime
            for j in range(2 * i, self.N, i):
                self.p[j] = 0

    # Function to find the valid split index in the array
    def findValidSplit(self, nums):
        
        # Mark 2 as non-prime to avoid unnecessary computation
        self.p[2] = 1
        
        # Run sieve to precompute primes
        self.seive()
        
        # Dictionary to store the prime factor counts for numbers in nums
        mp = {}
        
        # For each number in nums, calculate its prime factors
        for x in nums:
            
            # For each prime, divide the number by it if divisible
            for prime in self.primes:
                
                # Break if prime squared is greater than the current number
                if prime * prime > x:
                    
                    # If number is greater than 1, add it to the dictionary
                    if x > 1:
                        mp[x] = mp.get(x, 0) + 1
                    break
                
                # While divisible by prime, keep dividing and updating the dictionary
                while x % prime == 0:
                    mp[prime] = mp.get(prime, 0) + 1
                    x //= prime

        # Set to track active primes for the current split
        active_primes = set()

        # Loop through nums to find the valid split index
        for i in range(len(nums) - 1):
            
            # Take the current element from the array
            x = nums[i]
            
            # For each prime, check its factors for the current element
            for prime in self.primes:
                
                # Break if prime squared is greater than the current number
                if prime * prime > x:
                    
                    # If x is greater than 1, add it to active_primes
                    if x > 1:
                        active_primes.add(x)
                        
                        # Decrease count in the dictionary and remove from active_primes if count reaches 0
                        mp[x] -= 1
                        if mp[x] == 0:
                            active_primes.remove(x)
                    break
                
                # While divisible by prime, update active_primes and dictionary
                while x % prime == 0:
                    active_primes.add(prime)
                    mp[prime] -= 1
                    if mp[prime] == 0:
                        active_primes.remove(prime)
                    x //= prime

            # If no active primes remain, a valid split is found
            if len(active_primes) == 0:
                return i

        # Return -1 if no valid split is found
        return -1


# Input handling

# Create an instance of the Solution class
solution = Solution()

# Read the size of the array
n = int(input())

# Read the array elements
nums = list(map(int, input().split()))

# Find the valid split index
result = solution.findValidSplit(nums)

# Output the result
print(result)

Split the Array to Make Coprime code in JavaScript - Optimised 
class Solution {
    constructor() {
        // Define the upper limit for the sieve
        this.N = 1e6 + 10;

        // Boolean array to mark prime numbers
        this.p = Array(this.N).fill(1);

        // List to store prime numbers
        this.primes = [];
    }

    // Sieve of Eratosthenes to calculate primes up to N
    seive() {
        
        // Iterate over numbers to mark primes
        for (let i = 2; i < this.N; i++) {
            
            // Skip if the number is already marked as non-prime
            if (this.p[i] !== 1) continue;

            // Add prime number to the list
            this.primes.push(i);

            // Mark multiples of the prime as non-prime
            for (let j = 2 * i; j < this.N; j += i) {
                this.p[j] = 0;
            }
        }
    }

    // Function to find the valid split index in the array
    findValidSplit(nums) {
        
        // Mark 2 as non-prime to avoid unnecessary computation
        this.p[2] = 1;

        // Run sieve to precompute primes
        this.seive();

        // Map to store the prime factor counts for numbers in nums
        let mp = new Map();

        // For each number in nums, calculate its prime factors
        for (let x of nums) {
            
            // For each prime, divide the number by it if divisible
            for (let prime of this.primes) {
                
                // Break if prime squared is greater than the current number
                if (prime * prime > x) {
                    
                    // If number is greater than 1, add it to the map
                    if (x > 1) mp.set(x, (mp.get(x) || 0) + 1);
                    break;
                }

                // While divisible by prime, keep dividing and updating the map
                while (x % prime === 0) {
                    mp.set(prime, (mp.get(prime) || 0) + 1);
                    x /= prime;
                }
            }
        }

        // Set to track active primes for the current split
        let activePrimes = new Set();

        // Loop through nums to find the valid split index
        for (let i = 0; i < nums.length - 1; i++) {
            
            // Take the current element from the array
            let x = nums[i];

            // For each prime, check its factors for the current element
            for (let prime of this.primes) {
                
                // Break if prime squared is greater than the current number
                if (prime * prime > x) {
                    
                    // If x is greater than 1, add it to activePrimes
                    if (x > 1) {
                        activePrimes.add(x);
                        
                        // Decrease count in the map and remove from activePrimes if count reaches 0
                        mp.set(x, mp.get(x) - 1);
                        if (mp.get(x) === 0) activePrimes.delete(x);
                    }
                    break;
                }

                // While divisible by prime, update activePrimes and map
                while (x % prime === 0) {
                    activePrimes.add(prime);
                    mp.set(prime, mp.get(prime) - 1);
                    if (mp.get(prime) === 0) activePrimes.delete(prime);
                    x /= prime;
                }
            }

            // If no active primes remain, a valid split is found
            if (activePrimes.size === 0) return i;
        }

        // Return -1 if no valid split is found
        return -1;
    }
}

// Input handling

// Create an instance of the Solution class
const solution = new Solution();

// Read input size of array
const n = parseInt(prompt());

// Read input array elements
const nums = prompt().split(' ').map(Number);

// Find the valid split index
const result = solution.findValidSplit(nums);

// Output the result
console.log(result);

Time Complexity: O(m*log(X))

The given solution consists of two main parts:

  1. Precomputing prime numbers using the Sieve of Eratosthenes
  2. Finding the valid split index using prime factorization

Sieve of Eratosthenes: O(Nlog⁡log⁡N)
The seive() function generates all prime numbers up to N=10^6. The time complexity of the Sieve of Eratosthenes is: O(Nlog⁡log⁡N)

  • Each number ii is iterated once.
  • The multiples of ii are marked in O(Ni) operations.
  • The total sum of these operations results in O(Nlog⁡log⁡N).

Thus, sieve execution takes O(Nlog⁡log⁡N) time.
Prime Factorization for Each Number in nums: O(Mlog⁡X)
For each element in the array nums, the algorithm performs trial division using precomputed primes.

  • Let M be the size of the array nums.
  • Each number x is factorized using primes from the primes list.
  • The number of prime factors of a number x is at most O(log⁡X), where X is the largest number in nums.
  • Since each number is divided by its smallest prime factor at every step, the factorization of one number takes O(log⁡X) time.

Thus, for M numbers, prime factorization takes O(Mlog⁡X) time.
Finding the Valid Split: O(Mlog⁡X)
After computing the prime factors:

  • The algorithm iterates over M elements.
  • It updates the active prime factors in a set, which takes O(log⁡X) per element in the worst case.

Thus, finding the split index runs in O(Mlog⁡X) time.
Overall Complexity

  • Sieve of Eratosthenes: O(Nlog⁡log⁡N)
  • Prime Factorization and Finding Split: O(Mlog⁡X)

Since N=106, the sieve operation is a one-time precomputation. The dominant factor in practice is the O(Mlog⁡X) complexity from factorization and checking for valid splits.

Space Complexity: O(N+M)

Auxiliary Space Complexity
Auxiliary space refers to the extra space used beyond the input array.

Prime Array (p[N]): O(N)
The sieve algorithm maintains an array p of size N=10^6 to mark prime numbers.
Prime Numbers List (primes): O(N/log⁡N)
The number of primes up to N is approximately O(N/log⁡N), which is about 78,500 primes for N=106.

  • Map (mp) for Storing Prime Factors: O(K)
    This stores the frequency of prime factors, where K is the number of distinct prime factors across all numbers in nums.
    In the worst case, each number is a unique prime, so K=O(M).
  • Set (se) for Active Prime Factors: O(K)
    The set maintains active prime factors, which in the worst case can be O(M).

Thus, the auxiliary space complexity is: O(N)+O(K)
For N=106 and K=O(M), the auxiliary space is:O(N+M)
Total Space Complexity (including input storage)

  • Input Array (nums): O(M)
    The array nums is given as input and takes O(M) space.

Adding this to auxiliary space:O(N+M)
Since N=106 is a constant in this context, the dominant term depends on M, making the total space complexity: O(N+M)

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Replace Non-Coprime Numbers in Array

Iterate through nums, checking adjacent elements. If any two are non-coprime (GCD(x, y) > 1), replace them with their LCM(x, y) and restart from the previous index to maintain order. Repeat until no such pairs exist. Return the final modified array.