{"id":"30243b57-014a-4b29-ab47-2a46da8e3db3","name":"Optimal Binary Search Tree","description":"1. You are given two arrays - \r\n The first array(keys), which is sorted and has distinct integers, represents search keys.\r\n Second one(freq) represents frequency counts, where freq[i] is the number of searches to keys[i].\r\n2. A binary search tree is constructed containing all keys and the total cost of searches is minimum. \r\n3. The cost of a BST node is the level of that node multiplied by its frequency.\r\n4. You have to find the minimum cost of all searches.","inputFormat":"A number N\r\na1\r\na2.. N integers\r\nb1\r\nb2.. N numbers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 1000\r\n1 &lt;= keys[i],freq[i] &lt;= 1000","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n \r\n private static void optimalbst(int[] keys, int[] frequency, int n) {\r\n //write your code here\r\n \r\n\t}\r\n\r\n public static void main(String[] args) {\r\n\t\tScanner scn = new Scanner(System.in);\r\n\t\tint n = scn.nextInt();\r\n\tint[] keys = new int[n];\r\n\tint[] frequency = new int[n];\r\n for(int i= 0 ;i < n ; i++) {\r\n\t\tkeys[i] = scn.nextInt();\r\n\t}\r\n\tfor(int i = 0 ; i < n; i++){\r\n frequency[i] = scn.nextInt();\r\n }\r\n\toptimalbst(keys,frequency,n);\r\n\t}\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"9\r\n1\r\n3\r\n4\r\n5\r\n6\r\n7\r\n8\r\n9\r\n11\r\n3\r\n6\r\n4\r\n8\r\n7\r\n3\r\n7\r\n4\r\n7\r\n","sampleOutput":"125\r\n","questionVideo":"https://www.youtube.com/embed/HnslzEs8dbY?end=689","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"62e9f3cc-c37e-47b5-96ae-c5139900d663","name":"Optimal Binary Search Tree","slug":"optimal-binary-search-tree","type":1}],"next":{"id":"83c9a459-c532-41f8-abcb-f5cfef9bb0c9","name":"Optimal binary search tree MCQ","type":0,"slug":"optimal-binary-search-tree-mcq"},"prev":{"id":"b6af6456-130f-4db2-aa2f-9357594aabee","name":"Maximum Sum Of M Non - overlapping Subarrays","type":3,"slug":"maximum-sum-of-m-non-overlapping-subarrays"}}}

Optimal Binary Search Tree

1. You are given two arrays - The first array(keys), which is sorted and has distinct integers, represents search keys. Second one(freq) represents frequency counts, where freq[i] is the number of searches to keys[i]. 2. A binary search tree is constructed containing all keys and the total cost of searches is minimum. 3. The cost of a BST node is the level of that node multiplied by its frequency. 4. You have to find the minimum cost of all searches.

{"id":"30243b57-014a-4b29-ab47-2a46da8e3db3","name":"Optimal Binary Search Tree","description":"1. You are given two arrays - \r\n The first array(keys), which is sorted and has distinct integers, represents search keys.\r\n Second one(freq) represents frequency counts, where freq[i] is the number of searches to keys[i].\r\n2. A binary search tree is constructed containing all keys and the total cost of searches is minimum. \r\n3. The cost of a BST node is the level of that node multiplied by its frequency.\r\n4. You have to find the minimum cost of all searches.","inputFormat":"A number N\r\na1\r\na2.. N integers\r\nb1\r\nb2.. N numbers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 1000\r\n1 &lt;= keys[i],freq[i] &lt;= 1000","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n \r\n private static void optimalbst(int[] keys, int[] frequency, int n) {\r\n //write your code here\r\n \r\n\t}\r\n\r\n public static void main(String[] args) {\r\n\t\tScanner scn = new Scanner(System.in);\r\n\t\tint n = scn.nextInt();\r\n\tint[] keys = new int[n];\r\n\tint[] frequency = new int[n];\r\n for(int i= 0 ;i < n ; i++) {\r\n\t\tkeys[i] = scn.nextInt();\r\n\t}\r\n\tfor(int i = 0 ; i < n; i++){\r\n frequency[i] = scn.nextInt();\r\n }\r\n\toptimalbst(keys,frequency,n);\r\n\t}\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"9\r\n1\r\n3\r\n4\r\n5\r\n6\r\n7\r\n8\r\n9\r\n11\r\n3\r\n6\r\n4\r\n8\r\n7\r\n3\r\n7\r\n4\r\n7\r\n","sampleOutput":"125\r\n","questionVideo":"https://www.youtube.com/embed/HnslzEs8dbY?end=689","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"62e9f3cc-c37e-47b5-96ae-c5139900d663","name":"Optimal Binary Search Tree","slug":"optimal-binary-search-tree","type":1}],"next":{"id":"83c9a459-c532-41f8-abcb-f5cfef9bb0c9","name":"Optimal binary search tree MCQ","type":0,"slug":"optimal-binary-search-tree-mcq"},"prev":{"id":"b6af6456-130f-4db2-aa2f-9357594aabee","name":"Maximum Sum Of M Non - overlapping Subarrays","type":3,"slug":"maximum-sum-of-m-non-overlapping-subarrays"}}}
plane

Editor

Loading...

Optimal Binary Search Tree

easy

1. You are given two arrays - The first array(keys), which is sorted and has distinct integers, represents search keys. Second one(freq) represents frequency counts, where freq[i] is the number of searches to keys[i]. 2. A binary search tree is constructed containing all keys and the total cost of searches is minimum. 3. The cost of a BST node is the level of that node multiplied by its frequency. 4. You have to find the minimum cost of all searches.

Constraints

1 <= N <= 1000 1 <= keys[i],freq[i] <= 1000

Format

Input

A number N a1 a2.. N integers b1 b2.. N numbers

Output

Check the sample output and question video.

Example

Sample Input

9 1 3 4 5 6 7 8 9 11 3 6 4 8 7 3 7 4 7

Sample Output

125

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode