Skip to main content

Posts

Equal Beauty CodeChef SnackDown 2021 Round 1A

 Equal Beauty CodeChef SnackDown 2021 Round 1A Question The beauty of an (non-empty) array of integers is defined as the difference between its largest and smallest element. For example, the beauty of the array [2,3,4,4,6] is 6−2=4. An array A is said to be good if it is possible to partition the elements of A into two non-empty arrays B1 and B2 such that B1 and B2 have the same beauty. Each element of array A should be in exactly one array: either in B1 or in B2. For example, the array [6,2,4,4,4] is good because its elements can be partitioned into two arrays B1=[6,4,4] and B2=[2,4], where both B1 and B2 have the same beauty (6−4=4−2=2). You are given an array A of length N. In one move you can: Select an index i (1≤i≤N) and either increase Ai by 1 or decrease Ai by 1. Find the minimum number of moves required to make the array A good. Input Format The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow. Each ...
Post a Comment
Read more

Best Time to Buy and Sell Stock III LeetCode Solution

 Best Time to Buy and Sell Stock III LeetCode Solution Question You are given an array  prices  where  prices[i]  is the price of a given stock on the  i th  day. Find the maximum profit you can achieve. You may complete  at most two transactions . Note:  You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).   Example 1: Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3. Example 2: Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again. Example 3: Input: prices = [7,6,4,3,1] Output: 0 Ex...
Post a Comment
Read more

Best Time to Buy and Sell Stock with Cooldown LeetCode Solution

 Best Time to Buy and Sell Stock with Cooldown LeetCode Solution Question You are given an array  prices  where  prices[i]  is the price of a given stock on the  i th  day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions: After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day). Note:  You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).   Example 1: Input: prices = [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell] Example 2: Input: prices = [1] Output: 0   Constraints: 1 <= prices.length <= 5000 0 <= prices[i] <= 1000 Explanation This question is categorized as medium difficulty question as this question involves Dynamic Programming, although it can be done usin...
Post a Comment
Read more

Perfect Squares LeetCode Solution

 Perfect Squares LeetCode Solution Question Given an integer  n , return  the least number of perfect square numbers that sum to   n . A  perfect square  is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example,  1 ,  4 ,  9 , and  16  are perfect squares while  3  and  11  are not.   Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.   Constraints: 1 <= n <= 10 4 Explanation This problem is categorized as medium level problem since this to solve this problem we need the Dynamic Programming approach. For a given number n, n can only be represented by numbers from 1 to sqrt(n). Next thing we need to have a recursive approach. We calculate a dp array by taking dp[current position - count*count]+1 and just returning dp[n] makes it done. You just need to code...
Post a Comment
Read more

Construct Binary Search Tree from Preorder Traversal LeetCode Solution

 Construct Binary Search Tree from Preorder Traversal LeetCode Solution Question Given an array of integers preorder, which represents the  preorder traversal  of a BST (i.e.,  binary search tree ), construct the tree and return  its root . It is  guaranteed  that there is always possible to find a binary search tree with the given requirements for the given test cases. A  binary search tree  is a binary tree where for every node, any descendant of  Node.left  has a value  strictly less than   Node.val , and any descendant of  Node.right  has a value  strictly greater than   Node.val . A  preorder traversal  of a binary tree displays the value of the node first, then traverses  Node.left , then traverses  Node.right .   Example 1: Input: preorder = [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12] Example 2: Input: preorder = [1,3] Output: [1,null,3]   Constraints: 1 <= p...
Post a Comment
Read more

Guess Number Higher or Lower LeetCode Solution

 Guess Number Higher or Lower LeetCode Solution Question We are playing the Guess Game. The game is as follows: I pick a number from  1  to  n . You have to guess which number I picked. Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess. You call a pre-defined API  int guess(int num) , which returns 3 possible results: -1 : The number I picked is lower than your guess (i.e.  pick < num ). 1 : The number I picked is higher than your guess (i.e.  pick > num ). 0 : The number I picked is equal to your guess (i.e.  pick == num ). Return  the number that I picked .   Example 1: Input: n = 10, pick = 6 Output: 6 Example 2: Input: n = 1, pick = 1 Output: 1 Example 3: Input: n = 2, pick = 1 Output: 1 Example 4: Input: n = 2, pick = 2 Output: 2   Constraints: 1 <= n <= 2 31  - 1 1 <= pick <= n Explanation This program is quite simple as you just need ...
Post a Comment
Read more