Question:
Given an array, A of size N. Find whether it is possible to make a Binary Search Tree with elements of A such that the greatest common divisor of any two vertices connected by a common edge is > 1. Print Yes if possible, otherwise print No.
Read more about Binary Search Trees from here.
Examples:
Alert Ninjas: Don’t stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and spaceefficient code and compete in code competitions worldwide.
1.
Input: A = { 3, 18, 6, 9, 36, 108 } Output: Yes

Explanation: One of the possible BTS is given below. Here vertices of every edge have GCD > 1.
2.
Input: A = {2, 47} Output: No 
Explanation: GCD of 2 and 47 is 1.
Recommended: Please try to solve it yourself before moving on to the solution.
Solution:
Approach1:
The idea is to use Dynamic Programming (DP).
Let DP(l, r, root) be a DP array with values 0 or 1 determining if it is possible to create a BST root at the root from the subsegment [ l, r ] of the given array.
Calculating DP(l, r, root) requires extracting the (leftRoot) root of the left subtree from [l..root – 1] and (rightRoot) root of the right subtree from [root + 1..right] in the following manner:
 gcd(a_{root}, a_{rightRoot}) > 1
 gcd(a_{root}, a_{leftRoot}) > 1
 DP(l, root1, leftRoot) = 1
 DP(root+1, r, rightRoot) = 1
In DP(l, r, root), l can take n values, r can take n values, and root can also take n values. Therefore there are n^{3} DP states.
Also, the transition time for DP will be O(n). Hence, a total of n^{4} time complexity of this solution.
Better Approach
Let’s define DP differently; let DP_{New}(l, r, state) be a DP, where a state can be 0 or 1.
Here we can calculate DP(l, r, root) from DP_{New}(l, root  1, 1) and DP_{New}(root + 1, r, 0).
Here l can take n values, r can take n values, and state can take two values. Therefore there are n^{2} DP states.
Also, the transition time for DP will be O(n). Hence, it has a total of n^{3} time complexity which is enough to pass.
C++
#include <bits/stdc++.h>
for (int i = 0; i < n; i++){

Output:
Time Complexity: O(N^{3})