Given an array arr[] of size N. The task is to find whether it is possible to make Binary Search Tree with the given array of elements such that greatest common divisor of any two vertices connected by a common edge is > 1. If possible then print Yes else print No.
Examples:
Input: arr[] = {3, 6, 9, 18, 36, 108}
Output: Yes
This is one of the possible Binary Search Tree with given array.
Input: arr[] = {2, 17}
Output: No
Approach:
Let DP(l, r, root) be a DP determining whether it’s possible to assemble a tree rooted at root from the sub-segment [l..r].
It’s easy to see that calculating it requires extracting such rootleft from [l..root – 1] and rootright from [root + 1..right] such that:
- gcd(aroot, arootleft) > 1
- gcd(aroot, arootright) > 1
- DP(l, root-1, rootleft) = 1
- DP(root+1, r, rootright) = 1
This can be done in O(r – l) provided we are given all DP(x, y, z) values for all sub-segments of [l..r]. Considering a total of O(n3) DP states, the final complexity is O(n4) and that’s too much.
Let’s turn our DP into DPnew(l, r, state) where the state can be either 0 or 1. It immediately turns out that DP(l, r, root) is inherited from DPnew(l, root-1, 1) and DPnew(root+1, r, 0). Now we have O(n2) states, but at the same time, all transitions are performed in linear time. Thus final complexity is O(n3) which is sufficient to pass.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Maximum number of vertices#define N 705// To store is it possible at// particular pace or notint dp[N][N][2];// Return 1 if from l to r, it is possible with// the given stateint possibleWithState(int l, int r, int state, int a[]){ // Base condition if (l > r) return 1; // If it is already calculated if (dp[l][r][state] != -1) return dp[l][r][state]; // Choose the root int root; if (state == 1) root = a[r + 1]; else root = a[l - 1]; // Traverse in range l to r for (int i = l; i <= r; i++) { // If gcd is greater than one // check for both sides if (__gcd(a[i], root) > 1) { int x = possibleWithState(l, i - 1, 1, a); if (x != 1) continue; int y = possibleWithState(i + 1, r, 0, a); if (x == 1 && y == 1) return dp[l][r][state] = 1; } } // If not possible return dp[l][r][state] = 0;}// Function that return true if it is possible// to make Binary Search Treebool isPossible(int a[], int n){ memset(dp, -1, sizeof dp); // Sort the given array sort(a, a + n); // Check it is possible rooted at i for (int i = 0; i < n; i++) // Check at both sides if (possibleWithState(0, i - 1, 1, a) && possibleWithState(i + 1, n - 1, 0, a)) { return true; } return false;}// Driver codeint main(){ int a[] = { 3, 6, 9, 18, 36, 108 }; int n = sizeof(a) / sizeof(a[0]); if (isPossible(a, n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b-a); } // Maximum number of verticesstatic final int N = 705;// To store is it possible at// particular pace or notstatic int dp[][][] = new int[N][N][2];// Return 1 if from l to r, it is // possible with the given statestatic int possibleWithState(int l, int r, int state, int a[]){ // Base condition if (l > r) return 1; // If it is already calculated if (dp[l][r][state] != -1) return dp[l][r][state]; // Choose the root int root; if (state == 1) root = a[r + 1]; else root = a[l - 1]; // Traverse in range l to r for (int i = l; i <= r; i++) { // If gcd is greater than one // check for both sides if (__gcd(a[i], root) > 1) { int x = possibleWithState(l, i - 1, 1, a); if (x != 1) continue; int y = possibleWithState(i + 1, r, 0, a); if (x == 1 && y == 1) return dp[l][r][state] = 1; } } // If not possible return dp[l][r][state] = 0;}// Function that return true if it is possible// to make Binary Search Treestatic boolean isPossible(int a[], int n){ for(int i = 0; i < dp.length; i++) for(int j = 0; j < dp[i].length; j++) for(int k = 0; k < dp[i][j].length; k++) dp[i][j][k]=-1; // Sort the given array Arrays.sort(a); // Check it is possible rooted at i for (int i = 0; i < n; i++) // Check at both sides if (possibleWithState(0, i - 1, 1, a) != 0 && possibleWithState(i + 1, n - 1, 0, a) != 0) { return true; } return false;}// Driver codepublic static void main(String args[]){ int a[] = { 3, 6, 9, 18, 36, 108 }; int n = a.length; if (isPossible(a, n)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by // Arnab Kundu |
Python3
# Python3 implementation of the approach import math# Maximum number of vertices N = 705# To store is it possible at # particular pace or not dp = [[[-1 for z in range(2)] for x in range(N)] for y in range(N)]# Return 1 if from l to r, it is # possible with the given state def possibleWithState(l, r, state, a): # Base condition if (l > r): return 1 # If it is already calculated if (dp[l][r][state] != -1): return dp[l][r][state] # Choose the root root = 0 if (state == 1) : root = a[r + 1] else: root = a[l - 1] # Traverse in range l to r for i in range(l, r + 1): # If gcd is greater than one # check for both sides if (math.gcd(a[i], root) > 1): x = possibleWithState(l, i - 1, 1, a) if (x != 1): continue y = possibleWithState(i + 1, r, 0, a) if (x == 1 and y == 1) : return 1 # If not possible return 0# Function that return true if it is # possible to make Binary Search Tree def isPossible(a, n): # Sort the given array a.sort() # Check it is possible rooted at i for i in range(n): # Check at both sides if (possibleWithState(0, i - 1, 1, a) and possibleWithState(i + 1, n - 1, 0, a)): return True return False# Driver Code if __name__ == '__main__': a = [3, 6, 9, 18, 36, 108] n = len(a) if (isPossible(a, n)): print("Yes") else: print("No")# This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
// C# implementation of the approach using System; class GFG { static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b-a); } // Maximum number of vertices static int N = 705; // To store is it possible at // particular pace or not static int [,,]dp = new int[N, N, 2]; // Return 1 if from l to r, it is // possible with the given state static int possibleWithState(int l, int r, int state, int []a) { // Base condition if (l > r) return 1; // If it is already calculated if (dp[l, r, state] != -1) return dp[l, r, state]; // Choose the root int root; if (state == 1) root = a[r + 1]; else root = a[l - 1]; // Traverse in range l to r for (int i = l; i <= r; i++) { // If gcd is greater than one // check for both sides if (__gcd(a[i], root) > 1) { int x = possibleWithState(l, i - 1, 1, a); if (x != 1) continue; int y = possibleWithState(i + 1, r, 0, a); if (x == 1 && y == 1) return dp[l,r,state] = 1; } } // If not possible return dp[l,r,state] = 0; } // Function that return true // if it is possible to make // Binary Search Tree static bool isPossible(int []a, int n) { for(int i = 0; i < dp.GetLength(0); i++) for(int j = 0; j < dp.GetLength(1); j++) for(int k = 0; k < dp.GetLength(2); k++) dp[i, j, k]=-1; // Sort the given array Array.Sort(a); // Check it is possible rooted at i for (int i = 0; i < n; i++) // Check at both sides if (possibleWithState(0, i - 1, 1, a) != 0 && possibleWithState(i + 1, n - 1, 0, a) != 0) { return true; } return false; } // Driver code public static void Main(String []args) { int []a = { 3, 6, 9, 18, 36, 108 }; int n = a.Length; if (isPossible(a, n)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b-a); } // Maximum number of vertices var N = 705; // To store is it possible at // particular pace or not var dp = Array.from(Array(N), ()=>Array(N));for(var i = 0; i<N; i++){ for(var j = 0; j<N; j++) { dp[i][j] = new Array(2).fill(-1); }}// Return 1 if from l to r, it is // possible with the given state function possibleWithState(l, r, state,a) { // Base condition if (l > r) return 1; // If it is already calculated if (dp[l][r][state] != -1) return dp[l][r][state]; // Choose the root var root; if (state == 1) root = a[r + 1]; else root = a[l - 1]; // Traverse in range l to r for (var i = l; i <= r; i++) { // If gcd is greater than one // check for both sides if (__gcd(a[i], root) > 1) { var x = possibleWithState(l, i - 1, 1, a); if (x != 1) continue; var y = possibleWithState(i + 1, r, 0, a); if (x == 1 && y == 1) return dp[l][r][state] = 1; } } // If not possible return dp[l][r][state] = 0; } // Function that return true // if it is possible to make // Binary Search Tree function isPossible(a, n) { // Sort the given array a.sort(); // Check it is possible rooted at i for (var i = 0; i < n; i++) // Check at both sides if (possibleWithState(0, i - 1, 1, a) != 0 && possibleWithState(i + 1, n - 1, 0, a) != 0) { return true; } return false; } // Driver code var a = [3, 6, 9, 18, 36, 108]; var n = a.length; if (isPossible(a, n)) document.write("Yes"); else document.write("No"); // This code is contributed by itsok.</script> |
Output
Yes
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
