Рубрики

Сделать двоичное дерево поиска

Дан массив arr [] размера N. Задача состоит в том, чтобы выяснить, можно ли сделать дерево двоичного поиска с заданным массивом элементов таким, чтобы наибольший общий делитель любых двух вершин, соединенных общим ребром, был > 1 . Если возможно, тогда напечатайте Да, иначе напечатайте Нет

Примеры:

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

Подход. Пусть DP (l, r, root) будет DP, определяющим, возможно ли собрать дерево с корнем в корне из подсегмента [l..r].
Легко видеть , что вычисление ее требует извлечений такого корня левого из [l..root — 1] и корень справа от [корень + 1..right], что:

  • gcd ( корень , корень слева )> 1
  • gcd ( корень , право root )> 1
  • DP (l, root-1, root left ) = 1
  • DP (root + 1, r, root right ) = 1

Это можно сделать в O (r — l), если нам даны все значения DP (x, y, z) для всех подсегментов в [l..r]. Учитывая общее количество состояний O (n 3 ) DP, конечная сложность составляет O (n 4 ), и это слишком много.

Давайте превратим наш DP в DPnew (l, r, состояние), где состояние может быть 0 или 1. Сразу получается, что DP (l, r, root) наследуется от DPnew (l, root-1, 1) и DPnew (root + 1, r, 0). Теперь у нас есть O (n 2 ) состояний, но в то же время все переходы выполняются за линейное время. Таким образом, конечная сложность O (n 3 ), которую достаточно пройти.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Максимальное количество вершин
#define N 705

  
// Хранить можно в
// определенный темп или нет

int dp[N][N][2];

  
// Возвращаем 1, если от l до r, возможно с
// данное состояние

int possibleWithState(int l, int r, int state, int a[])

{

    // Базовое условие

    if (l > r)

        return 1;

  

    // Если он уже рассчитан

    if (dp[l][r][state] != -1)

        return dp[l][r][state];

  

    // Выбираем корень

    int root;

    if (state == 1)

        root = a[r + 1];

    else

        root = a[l - 1];

  

    // Пройдите в диапазоне от l до r

    for (int i = l; i <= r; i++) {

  

        // Если gcd больше единицы

        // проверяем обе стороны

        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;

        }

    }

  

    // Если невозможно

    return dp[l][r][state] = 0;

}

  
// Функция, которая возвращает true, если это возможно
// сделать бинарное дерево поиска

bool isPossible(int a[], int n)

{

    memset(dp, -1, sizeof dp);

  

    // Сортировать указанный массив

    sort(a, a + n);

  

    // Проверяем, возможно ли укореняться в i

    for (int i = 0; i < n; i++)

  

        // Проверка с обеих сторон

        if (possibleWithState(0, i - 1, 1, a)

            && possibleWithState(i + 1, n - 1, 0, a)) {

            return true;

        }

  

    return false;

}

  
// Код драйвера

int 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 реализация подхода

import java.util.*;

class GFG

{

      

static int __gcd(int a, int b) 

      

    // Все делит 0

    if (a == 0

        return b; 

    if (b == 0

        return a; 

      

    // базовый вариант

    if (a == b) 

        return a; 

      

    // а больше

    if (a > b) 

        return __gcd(a - b, b); 

    return __gcd(a, b-a); 

  
// Максимальное количество вершин

static final int N = 705;

  
// Хранить можно в
// определенный темп или нет

static int dp[][][] = new int[N][N][2];

  
// Возвращаем 1, если от l до r, это
// возможно с данным состоянием

static int possibleWithState(int l, int r,

                        int state, int a[])

{

    // Базовое условие

    if (l > r)

        return 1;

  

    // Если он уже рассчитан

    if (dp[l][r][state] != -1)

        return dp[l][r][state];

  

    // Выбираем корень

    int root;

    if (state == 1)

        root = a[r + 1];

    else

        root = a[l - 1];

  

    // Пройдите в диапазоне от l до r

    for (int i = l; i <= r; i++) 

    {

  

        // Если gcd больше единицы

        // проверяем обе стороны

        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;

        }

    }

  

    // Если невозможно

    return dp[l][r][state] = 0;

}

  
// Функция, которая возвращает true, если это возможно
// сделать бинарное дерево поиска

static 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;

  

    // Сортировать указанный массив

    Arrays.sort(a);

  

    // Проверяем, возможно ли укореняться в i

    for (int i = 0; i < n; i++)

  

        // Проверка с обеих сторон

        if (possibleWithState(0, i - 1, 1, a) != 0 && 

            possibleWithState(i + 1, n - 1, 0, a) != 0)

        {

            return true;

        }

  

    return false;

}

  
// Код драйвера

public 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");

  
}
}

  
// Этот код предоставлен
// Арнаб кунду

python3

# Python3 реализация подхода

import math

  
Максимальное количество вершин

N = 705

  
# Хранить можно в
# определенный темп или нет

dp = [[[-1 for z in range(2)] 

           for x in range(N)] 

           for y in range(N)]

  
# Вернуть 1, если от l до r, это
# возможно с данным состоянием

def possibleWithState(l, r, state, a): 

  

    # Базовое состояние

    if (l > r):

        return 1

  

    # Если он уже рассчитан

    if (dp[l][r][state] != -1):

        return dp[l][r][state] 

  

    # Выберите корень

    root = 0

    if (state == 1) :

        root = a[r + 1

    else:

        root = a[l - 1

  

    # Ход в диапазоне от l до r

    for i in range(l, r + 1): 

  

        # Если gcd больше единицы

        # проверка для обеих сторон

        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

  

    # Если не возможно

    return 0

  
# Функция, которая возвращает true, если это
# возможно сделать двоичное дерево поиска

def isPossible(a, n): 

      

    # Сортировать указанный массив

    a.sort() 

  

    # Проверьте, возможно ли укорениться в I

    for i in range(n):

          

        # Проверьте с обеих сторон

        if (possibleWithState(0, i - 1, 1, a) and 

            possibleWithState(i + 1, n - 1, 0, a)):

            return True

              

    return False

  
Код водителя

if __name__ == '__main__'

    a = [3, 6, 9, 18, 36, 108]

    n = len(a) 

    if (isPossible(a, n)):

        print("Yes")

    else:

        print("No")

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

// C # реализация подхода

using System; 

  

class GFG 

      

static int __gcd(int a, int b) 

      

    // Все делит 0

    if (a == 0) 

        return b; 

    if (b == 0) 

        return a; 

      

    // базовый вариант

    if (a == b) 

        return a; 

      

    // а больше

    if (a > b) 

        return __gcd(a - b, b); 

    return __gcd(a, b-a); 

  
// Максимальное количество вершин

static int N = 705; 

  
// Хранить можно в
// определенный темп или нет

static int [,,]dp = new int[N, N, 2]; 

  
// Возвращаем 1, если от l до r, это
// возможно с данным состоянием

static int possibleWithState(int l, int r, 

                        int state, int []a) 

    // Базовое условие

    if (l > r) 

        return 1; 

  

    // Если он уже рассчитан

    if (dp[l, r, state] != -1) 

        return dp[l, r, state]; 

  

    // Выбираем корень

    int root; 

    if (state == 1) 

        root = a[r + 1]; 

    else

        root = a[l - 1]; 

  

    // Пройдите в диапазоне от l до r

    for (int i = l; i <= r; i++) 

    

  

        // Если gcd больше единицы

        // проверяем обе стороны

        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; 

        

    

  

    // Если невозможно

    return dp[l,r,state] = 0; 

  
// Функция, которая возвращает true
// если можно сделать
// Двоичное дерево поиска

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; 

  

    // Сортировать указанный массив

    Array.Sort(a); 

  

    // Проверяем, возможно ли укореняться в i

    for (int i = 0; i < n; i++) 

  

        // Проверка с обеих сторон

        if (possibleWithState(0, i - 1, 1, a) != 0 && 

            possibleWithState(i + 1, n - 1, 0, a) != 0) 

        

            return true

        

  

    return false

  
// Код драйвера

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"); 

  

  
// Этот код предоставлен 29AjayKumar

Выход:

Yes

Рекомендуемые посты:

Сделать двоичное дерево поиска

0.00 (0%) 0 votes