Must Do DSA Topics Day 57
Tree
Postorder traversal of Binary Tree without recursion and without stack : Given a binary tree, perform postorder traversal. We have discussed the below methods for postorder traversal.
1) Recursive Postorder Traversal.
2) Postorder traversal using Stack.
2) Postorder traversal using two Stacks.
Learn more : https://bit.ly/3FiUiTK
Diagonal Traversal of Binary Tree : Consider lines with a slope of -1 that cross through nodes. Print all diagonal elements in a binary tree that belong to the same line, given a binary tree.
Learn more : https://bit.ly/3VHo4s9
Iterative diagonal traversal of binary tree : Consider lines of slope -1 passing between nodes. Given a Binary Tree, print all diagonal elements in a binary tree belonging to the same line.
Learn more : https://bit.ly/3FIOSCF
Tree
Postorder traversal of Binary Tree without recursion and without stack : Given a binary tree, perform postorder traversal. We have discussed the below methods for postorder traversal.
1) Recursive Postorder Traversal.
2) Postorder traversal using Stack.
2) Postorder traversal using two Stacks.
Learn more : https://bit.ly/3FiUiTK
Diagonal Traversal of Binary Tree : Consider lines with a slope of -1 that cross through nodes. Print all diagonal elements in a binary tree that belong to the same line, given a binary tree.
Learn more : https://bit.ly/3VHo4s9
Iterative diagonal traversal of binary tree : Consider lines of slope -1 passing between nodes. Given a Binary Tree, print all diagonal elements in a binary tree belonging to the same line.
Learn more : https://bit.ly/3FIOSCF
👍1🔥1
Must Do DSA Topics Day 58
Tree
Calculate depth of a full Binary tree from Preorder : Given preorder of a binary tree, calculate its depth(or height) [starting from depth 0]. The preorder is given as a string with two possible characters.
Learn more : https://bit.ly/3VHDBIt
Number of Binary Trees for given Preorder Sequence length : Count the number of Binary Tree possible for a given Preorder Sequence length n. In Preorder traversal, we process the root node first, then traverse the left child node and then right child node.
Learn more : https://bit.ly/3Fkt3rU
Modify a binary tree to get Preorder traversal using right pointers only : Given a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only the right pointers. During modification, you can use right as well as left pointers.
Learn more : https://bit.ly/3Yi8BAD
Tree
Calculate depth of a full Binary tree from Preorder : Given preorder of a binary tree, calculate its depth(or height) [starting from depth 0]. The preorder is given as a string with two possible characters.
Learn more : https://bit.ly/3VHDBIt
Number of Binary Trees for given Preorder Sequence length : Count the number of Binary Tree possible for a given Preorder Sequence length n. In Preorder traversal, we process the root node first, then traverse the left child node and then right child node.
Learn more : https://bit.ly/3Fkt3rU
Modify a binary tree to get Preorder traversal using right pointers only : Given a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only the right pointers. During modification, you can use right as well as left pointers.
Learn more : https://bit.ly/3Yi8BAD
👍1
Problem Of The Day
“Split Array Largest Sum”
Solve the problem to win points
Given an array arr[] of N elements and a number K. Split the given array into K subarrays such that the maximum subarray sum achievable out of K subarrays formed is minimum possible. Find that possible subarray sum.
Example 1:
Input:
N = 4, K = 3
arr[] = {1, 2, 3, 4}
Output: 4
Explanation:
Optimal Split is {1, 2}, {3}, {4}.
Maximum sum of all subarrays is 4,
which is minimum possible for 3 splits.
Example 2:
Input:
N = 3, K = 2
A[] = {1, 1, 2}
Output:
2
Explanation:
Splitting the array as {1,1} and {2} is optimal.
This results in a maximum sum subarray of 2.
Your Task:
The task is to complete the function splitArray() which returns the maximum sum subarray after splitting the array into K subarrays such that maximum sum subarray is minimum possible.
Constraints:
1 ≤ N ≤ 105
1 ≤ K ≤ N
1 ≤ arr[i] ≤ 104
Expected Time Complexity: O(N*log(sum(arr))).
Expected Auxiliary Space: O(1).
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/f04fd67b26b4828b6180715d8b1700426b637247/1
“Split Array Largest Sum”
Solve the problem to win points
Given an array arr[] of N elements and a number K. Split the given array into K subarrays such that the maximum subarray sum achievable out of K subarrays formed is minimum possible. Find that possible subarray sum.
Example 1:
Input:
N = 4, K = 3
arr[] = {1, 2, 3, 4}
Output: 4
Explanation:
Optimal Split is {1, 2}, {3}, {4}.
Maximum sum of all subarrays is 4,
which is minimum possible for 3 splits.
Example 2:
Input:
N = 3, K = 2
A[] = {1, 1, 2}
Output:
2
Explanation:
Splitting the array as {1,1} and {2} is optimal.
This results in a maximum sum subarray of 2.
Your Task:
The task is to complete the function splitArray() which returns the maximum sum subarray after splitting the array into K subarrays such that maximum sum subarray is minimum possible.
Constraints:
1 ≤ N ≤ 105
1 ≤ K ≤ N
1 ≤ arr[i] ≤ 104
Expected Time Complexity: O(N*log(sum(arr))).
Expected Auxiliary Space: O(1).
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/f04fd67b26b4828b6180715d8b1700426b637247/1
practice.geeksforgeeks.org
Split Array Largest Sum | Practice | GeeksforGeeks
Given an array arr[] of N elements and a number K. Split the given array into K subarrays such that the maximum subarray sum achievable out of K subarrays formed is minimum possible. Find that possible subarray sum.
Example 1:
Input:
N = 4,
Example 1:
Input:
N = 4,
👍2
Must Do DSA Topics Day 59
Tree
Construct Tree from given Inorder and Preorder traversals : In a Preorder sequence, the leftmost element is the root of the tree. So we know ‘A’ is the root for given sequences.
Learn more : https://bit.ly/3VSVcNL
Construct a tree from Inorder and Level order traversals : Given inorder and level-order traversals of a Binary Tree, construct the Binary Tree. Following is an example to illustrate the problem.
Learn more : https://bit.ly/3uHLCRU
Construct Complete Binary Tree from its Linked List Representation : Given Linked List Representation of Complete Binary Tree, construct the Binary tree. A complete binary tree can be represented in an array in the following approach.
Learn more : https://bit.ly/3Ygp5ZT
Tree
Construct Tree from given Inorder and Preorder traversals : In a Preorder sequence, the leftmost element is the root of the tree. So we know ‘A’ is the root for given sequences.
Learn more : https://bit.ly/3VSVcNL
Construct a tree from Inorder and Level order traversals : Given inorder and level-order traversals of a Binary Tree, construct the Binary Tree. Following is an example to illustrate the problem.
Learn more : https://bit.ly/3uHLCRU
Construct Complete Binary Tree from its Linked List Representation : Given Linked List Representation of Complete Binary Tree, construct the Binary tree. A complete binary tree can be represented in an array in the following approach.
Learn more : https://bit.ly/3Ygp5ZT
Must Do DSA Topics Day 60
Tree
Check for Children Sum Property in a Binary Tree : Given a binary tree, you need to check whether sum of all covered elements is equal to sum of all uncovered elements or not.
Learn more : bit.ly/3UYtv4K
Check if a given Binary Tree is SumTree : Write a function that returns true if the given Binary Tree is SumTree else false. A SumTree is a Binary Tree where the value of a node is equal to the sum of the nodes present in its left subtree and right subtree.
Learn more : bit.ly/3VRYv7W
Check sum of Covered and Uncovered nodes of Binary Tree : Given a binary tree, the task is to check for every node, its value is equal to the sum of values of its immediate left and right child. For NULL values, consider the value to be 0.
Learn more : bit.ly/3hmNjRI
Get access to more topics of Tree : https://www.geeksforgeeks.org/binary-tree-data-structure/
Tree
Check for Children Sum Property in a Binary Tree : Given a binary tree, you need to check whether sum of all covered elements is equal to sum of all uncovered elements or not.
Learn more : bit.ly/3UYtv4K
Check if a given Binary Tree is SumTree : Write a function that returns true if the given Binary Tree is SumTree else false. A SumTree is a Binary Tree where the value of a node is equal to the sum of the nodes present in its left subtree and right subtree.
Learn more : bit.ly/3VRYv7W
Check sum of Covered and Uncovered nodes of Binary Tree : Given a binary tree, the task is to check for every node, its value is equal to the sum of values of its immediate left and right child. For NULL values, consider the value to be 0.
Learn more : bit.ly/3hmNjRI
Get access to more topics of Tree : https://www.geeksforgeeks.org/binary-tree-data-structure/
Problem Of The Day
"Complement"
Solve the problem to win points
You are given a binary string str. In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and complement the characters between L and R i.e strL, strL+1, …, strR. By complement, we mean change character 0 to 1 and vice-versa.
You task is to perform ATMOST one operation such that in final string number of 1s is maximised. If there is no need to completement, i.e., string contains all 1s, return -1. Else, return the two values denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R.
Example 1:
Input:
N = 3
str = "111"
Output: -1
Explanation: As all characters are '1',
so don't need to complement any.
Example 2:
Input:
N = 2
str = "01"
Output: 1 1
Explanation: After complementing [1, 1]
the string becomes "11".
Your Task:
You don't need to read input or print anything. Complete the function findRange() which takes the string str and the size of the string, n, as input parameters and returns an array of length 2 or 1 representing the answer. You don't to print answer or take inputs.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/complement3911/1
"Complement"
Solve the problem to win points
You are given a binary string str. In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and complement the characters between L and R i.e strL, strL+1, …, strR. By complement, we mean change character 0 to 1 and vice-versa.
You task is to perform ATMOST one operation such that in final string number of 1s is maximised. If there is no need to completement, i.e., string contains all 1s, return -1. Else, return the two values denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R.
Example 1:
Input:
N = 3
str = "111"
Output: -1
Explanation: As all characters are '1',
so don't need to complement any.
Example 2:
Input:
N = 2
str = "01"
Output: 1 1
Explanation: After complementing [1, 1]
the string becomes "11".
Your Task:
You don't need to read input or print anything. Complete the function findRange() which takes the string str and the size of the string, n, as input parameters and returns an array of length 2 or 1 representing the answer. You don't to print answer or take inputs.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/complement3911/1
practice.geeksforgeeks.org
Complement | Practice | GeeksforGeeks
You are given a binary string str. In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and complement the characters between L and R i.e strL, strL+1, …, strR. By complement, we mean change character 0 to
👍4👏1
Must Do DSA Topics Day 61
Binary Search Tree
Introduction to Binary Search Tree – Data Structure and Algorithm Tutorials : Binary Search Tree is a node-based binary tree data structure which has the following properties:
-The left subtree of a node contains only nodes with keys lesser than the node’s key.
-The right subtree of a node contains only nodes with keys greater than the node’s key.
Learn more : https://bit.ly/3Bw91JW
Applications of BST : Binary Search Tree, is a node-based binary tree data structure which has the following properties:
-The left subtree of a node contains only nodes with keys lesser than the node’s key.
-The right subtree of a node contains only nodes with keys greater than the node’s key.
Learn more : https://bit.ly/3BWMfLx
Application, Advantages and Disadvantages of Binary Search Tree : Searching in BST involves the comparison of the key values.
Learn more : https://bit.ly/3hvrPlv
Binary Search Tree
Introduction to Binary Search Tree – Data Structure and Algorithm Tutorials : Binary Search Tree is a node-based binary tree data structure which has the following properties:
-The left subtree of a node contains only nodes with keys lesser than the node’s key.
-The right subtree of a node contains only nodes with keys greater than the node’s key.
Learn more : https://bit.ly/3Bw91JW
Applications of BST : Binary Search Tree, is a node-based binary tree data structure which has the following properties:
-The left subtree of a node contains only nodes with keys lesser than the node’s key.
-The right subtree of a node contains only nodes with keys greater than the node’s key.
Learn more : https://bit.ly/3BWMfLx
Application, Advantages and Disadvantages of Binary Search Tree : Searching in BST involves the comparison of the key values.
Learn more : https://bit.ly/3hvrPlv
Problem Of The Day
"Balanced string"
Solve the problem to win points
Given an integer N.Create a string using only lowercase characters from a to z that follows the given rules.
When N is even:
Use N/2 characters from the beginning of a-z and N/2 characters from the ending of a-z.
When N is greater than 26,continue repeating the instructions until length of string becomes N.
When N is odd:
Case 1: If the sum of digits of N is even, Select (N+1)/2 characters from the beginning of a-z and (N-1)/2 characters from the ending of a-z.
Case 2: If the sum of digits of N is odd, Select (N-1)/2 characters from the beginning of a-z and (N+1)/2 characters from the ending of a-z.
When N is greater than 26,continue repeating the instructions until length of string becomes N.
Example 1:
Input:
N=21
Output:
abcdefghijpqrstuvwxyz
Explanation:
Since 21 is odd and sum of digits
of 21 is also odd,we take (21-1)/2=10
characters from the beginning and
(21+1)/2=11 characters from the
end of a-z.
Example 2:
Input:
N=28
Output:
abcdefghijklmnopqrstuvwxyzaz
Explanation:
Since 28>26, we keep repeating
the process until length of string becomes
28.
Your Task:
You don't need to read input or print anything. Your task is to complete the function BalancedString() which takes the integer N as input parameter and returns the string created using given procedures.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/balanced-string1627/1
"Balanced string"
Solve the problem to win points
Given an integer N.Create a string using only lowercase characters from a to z that follows the given rules.
When N is even:
Use N/2 characters from the beginning of a-z and N/2 characters from the ending of a-z.
When N is greater than 26,continue repeating the instructions until length of string becomes N.
When N is odd:
Case 1: If the sum of digits of N is even, Select (N+1)/2 characters from the beginning of a-z and (N-1)/2 characters from the ending of a-z.
Case 2: If the sum of digits of N is odd, Select (N-1)/2 characters from the beginning of a-z and (N+1)/2 characters from the ending of a-z.
When N is greater than 26,continue repeating the instructions until length of string becomes N.
Example 1:
Input:
N=21
Output:
abcdefghijpqrstuvwxyz
Explanation:
Since 21 is odd and sum of digits
of 21 is also odd,we take (21-1)/2=10
characters from the beginning and
(21+1)/2=11 characters from the
end of a-z.
Example 2:
Input:
N=28
Output:
abcdefghijklmnopqrstuvwxyzaz
Explanation:
Since 28>26, we keep repeating
the process until length of string becomes
28.
Your Task:
You don't need to read input or print anything. Your task is to complete the function BalancedString() which takes the integer N as input parameter and returns the string created using given procedures.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/balanced-string1627/1
practice.geeksforgeeks.org
Balanced string | Practice | GeeksforGeeks
Given an integer N.Create a string using only lowercase characters from a to z that follows the given rules.
When N is even:
Use N/2 characters from the beginning of a-z and N/2 characters from the ending of a-z.
When N is greater than
When N is even:
Use N/2 characters from the beginning of a-z and N/2 characters from the ending of a-z.
When N is greater than
👍2
Must Do DSA Topics Day 62
Binary Search Tree
Insertion in Binary Search Tree : A new key is always inserted at the leaf by maintaining the property of the binary search tree. We start searching for a key from the root until we hit a leaf node.
Learn more : https://bit.ly/3BC13yK
Deletion in Binary Search Tree : We have discussed BST search and insert operations. In this post, the delete operation is discussed. When we delete a node, three possibilities arise.
Learn more : https://bit.ly/3BCdRFA
Convert a normal BST to Balanced BST : Given a BST (Binary Search Tree) that may be unbalanced, convert it into a balanced BST that has minimum possible height.
Learn more : https://bit.ly/3G41C7n
Binary Search Tree
Insertion in Binary Search Tree : A new key is always inserted at the leaf by maintaining the property of the binary search tree. We start searching for a key from the root until we hit a leaf node.
Learn more : https://bit.ly/3BC13yK
Deletion in Binary Search Tree : We have discussed BST search and insert operations. In this post, the delete operation is discussed. When we delete a node, three possibilities arise.
Learn more : https://bit.ly/3BCdRFA
Convert a normal BST to Balanced BST : Given a BST (Binary Search Tree) that may be unbalanced, convert it into a balanced BST that has minimum possible height.
Learn more : https://bit.ly/3G41C7n
👍3
Problem Of The Day
"2D Hopscotch"
Solve the problem to win points
Aakriti, Avantika and Mehak are playing 2D Hopscotch. The arena is in the form of a n*m 2D matrix. But the position of the cells is slightly modified as shown below.
Mehak starts the game from tile (i,j) while Avantika and Aakriti direct her. In each turn Mehak will collect all the stones present (1 or 2) steps away from where she is standing. Avantika can direct Mehak to take 1 step and and Aakriti can direct Mehak to take 2 steps.
If the director ty is known to you as ty = 0 being Avantika and 1 being Aakriti, find the number of stones that Mehak will collect.
Example 1:
Input:
n = 3, m = 3
mat = {{5, 9, 7},
{6, 4, 5},
{8, 1, 2}}
ty = 0,
i = 1, j = 1
Output: 31
Explaination:
ty=0, so Avantika is the director.
ie- Mehak will move only one step in
any direction to collect the stones.
(0,1), (1,0), (1,2), (2,1), (2,2), (2,0)
are at a distance of 1 from (1,1).
Adding them 9+6+5+8+1+2=31.
Example 2:
Input:
n = 3, m = 3
mat = {{5, 9, 7},
{6, 4, 5},
{8, 1, 2}}
ty = 1,
i = 1, j = 1
Output: 12
Explaination:
ty=1, so Aakriti is the director.
ie- Mehak can move 2 steps.
(0,0) and (0,2) are the only tiles that
are at a distance of two from (1,1).
Adding them gives 5+7=12.
Your Task:
You do not need to read input or print anything. Your task is to complete the function hopscotch() which takes n, m, mat, ty, i and j as input parameters and returns the number of collected stones.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/hopscotch4857/1
Powered by Hirist.com
"2D Hopscotch"
Solve the problem to win points
Aakriti, Avantika and Mehak are playing 2D Hopscotch. The arena is in the form of a n*m 2D matrix. But the position of the cells is slightly modified as shown below.
Mehak starts the game from tile (i,j) while Avantika and Aakriti direct her. In each turn Mehak will collect all the stones present (1 or 2) steps away from where she is standing. Avantika can direct Mehak to take 1 step and and Aakriti can direct Mehak to take 2 steps.
If the director ty is known to you as ty = 0 being Avantika and 1 being Aakriti, find the number of stones that Mehak will collect.
Example 1:
Input:
n = 3, m = 3
mat = {{5, 9, 7},
{6, 4, 5},
{8, 1, 2}}
ty = 0,
i = 1, j = 1
Output: 31
Explaination:
ty=0, so Avantika is the director.
ie- Mehak will move only one step in
any direction to collect the stones.
(0,1), (1,0), (1,2), (2,1), (2,2), (2,0)
are at a distance of 1 from (1,1).
Adding them 9+6+5+8+1+2=31.
Example 2:
Input:
n = 3, m = 3
mat = {{5, 9, 7},
{6, 4, 5},
{8, 1, 2}}
ty = 1,
i = 1, j = 1
Output: 12
Explaination:
ty=1, so Aakriti is the director.
ie- Mehak can move 2 steps.
(0,0) and (0,2) are the only tiles that
are at a distance of two from (1,1).
Adding them gives 5+7=12.
Your Task:
You do not need to read input or print anything. Your task is to complete the function hopscotch() which takes n, m, mat, ty, i and j as input parameters and returns the number of collected stones.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/hopscotch4857/1
Powered by Hirist.com
practice.geeksforgeeks.org
2D Hopscotch | Practice | GeeksforGeeks
Aakriti, Avantika and Mehak are playing 2D Hopscotch. The arena is in the form of a n*m 2D matrix. But the position of the cells is slightly modified as shown below.
Mehak starts the game from tile (i,j) while Avantika and Aakriti direct h
Mehak starts the game from tile (i,j) while Avantika and Aakriti direct h
👍1
Must Do DSA Topics Day 63
Binary Search Tree
Iterative searching in Binary Search Tree : Given a binary search tree and a key. Check the given key exists in BST or not without recursion.
Learn more : https://bit.ly/3uWDoVY
A program to check if a binary tree is BST or not: The idea is to for each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.
Learn more : https://bit.ly/3uVFhCr
Binary Tree to Binary Search Tree Conversion : Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree.
Learn more : https://bit.ly/3BI7eBA
Binary Search Tree
Iterative searching in Binary Search Tree : Given a binary search tree and a key. Check the given key exists in BST or not without recursion.
Learn more : https://bit.ly/3uWDoVY
A program to check if a binary tree is BST or not: The idea is to for each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.
Learn more : https://bit.ly/3uVFhCr
Binary Tree to Binary Search Tree Conversion : Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree.
Learn more : https://bit.ly/3BI7eBA
Problem Of The Day
"Break a number"
Solve the problem to win points
Given a really large number N, break it into 3 whole numbers such that they sum up to the original number and find the number of ways to do so. Since this number can be very large, return it modulo 109+7.
Example 1:
Input:
N = 2
Output:
6
Explanation:
Possible ways to break the number:
0 + 0 + 2 = 2
0 + 2 + 0 = 2
2 + 0 + 0 = 2
0 + 1 + 1 = 2
1 + 1 + 0 = 2
1 + 0 + 1 = 2
Example 2:
Input:
N = 3
Output:
10
Explanation:
Possible ways to break the number:
0+0+3 = 3
0+3+0 = 3
3+0+0 = 3
0+1+2 = 3
0+2+1 = 3
1+0+2 = 3
1+2+0 = 3
2+0+1 = 3
2+1+0 = 3
1+1+1 = 3
Your Task:
You don't need to read input or print anything. Your task is to complete the function waysToBreakNumber() which takes an integer N and returns the possible ways to break the number in 3 parts.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/break-a-number5913/1
Powered by hirist.com
"Break a number"
Solve the problem to win points
Given a really large number N, break it into 3 whole numbers such that they sum up to the original number and find the number of ways to do so. Since this number can be very large, return it modulo 109+7.
Example 1:
Input:
N = 2
Output:
6
Explanation:
Possible ways to break the number:
0 + 0 + 2 = 2
0 + 2 + 0 = 2
2 + 0 + 0 = 2
0 + 1 + 1 = 2
1 + 1 + 0 = 2
1 + 0 + 1 = 2
Example 2:
Input:
N = 3
Output:
10
Explanation:
Possible ways to break the number:
0+0+3 = 3
0+3+0 = 3
3+0+0 = 3
0+1+2 = 3
0+2+1 = 3
1+0+2 = 3
1+2+0 = 3
2+0+1 = 3
2+1+0 = 3
1+1+1 = 3
Your Task:
You don't need to read input or print anything. Your task is to complete the function waysToBreakNumber() which takes an integer N and returns the possible ways to break the number in 3 parts.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/break-a-number5913/1
Powered by hirist.com
www.geeksforgeeks.org
Break a number | Practice | GeeksforGeeks
Given a really large number N, break it into 3 whole numbers such that they sum up to the original number and find the number of ways to do so. Since this number can be very large, return it modulo 109+7.
Example 1:
Input:
N
Example 1:
Input:
N
👍1
Must Do DSA Topics Day 64
Binary Search Tree
Sorted Linked List to Balanced BST : Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List.
Learn more : https://bit.ly/3PxEssQ
Transform a BST to greater sum tree : Given a BST, transform it into a greater sum tree where each node contains sum of all nodes greater than that node.
Learn more : https://bit.ly/3C5QhRR
Construct all possible BSTs for keys 1 to N : In this article, first count of possible BST (Binary Search Trees)s is discussed, then the construction of all possible BSTs.
Learn more : https://bit.ly/3hFtO6O
Get access to all the topics of Binary Search Tree : https://www.geeksforgeeks.org/binary-search-tree-data-structure/?ref=gcse
Binary Search Tree
Sorted Linked List to Balanced BST : Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List.
Learn more : https://bit.ly/3PxEssQ
Transform a BST to greater sum tree : Given a BST, transform it into a greater sum tree where each node contains sum of all nodes greater than that node.
Learn more : https://bit.ly/3C5QhRR
Construct all possible BSTs for keys 1 to N : In this article, first count of possible BST (Binary Search Trees)s is discussed, then the construction of all possible BSTs.
Learn more : https://bit.ly/3hFtO6O
Get access to all the topics of Binary Search Tree : https://www.geeksforgeeks.org/binary-search-tree-data-structure/?ref=gcse
Job Alert 🔊
Twerlo is hiring for Fullstack (Angular). Eligible candidates can apply. Also, share with your friends who might be looking for the opportunity.
Location - Banglore
Last date to apply - Dec 21, 2022
Get more details about the job here : https://practice.geeksforgeeks.org/jobs/Ttwerlo-aangularfullstack
Twerlo is hiring for Fullstack (Angular). Eligible candidates can apply. Also, share with your friends who might be looking for the opportunity.
Location - Banglore
Last date to apply - Dec 21, 2022
Get more details about the job here : https://practice.geeksforgeeks.org/jobs/Ttwerlo-aangularfullstack
Problem Of The Day
"A Game of LCM"
Solve the problem to win points
Given an integer N. Find maximum LCM (Least Common Multiple) that can be obtained from four numbers less than or equal to N.
Note: Duplicate numbers can be used.
Example 1:
Input:
N = 4
Output: 12
Explanation:
The four numbers can be [4,4,3,2] or
[4,4,4,3], etc. It can be shown that 12 is
the maximum LCM of four numbers that can
be obtained from numbers less than or equal
to 4.
Example 2:
Input:
N = 5
Output: 60
Explanation:
The four numbers can be [5,5,4,3] or
[5,4,3,2], etc. 60 is the maximum that can
be obtained.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxGcd() which takes N as the input parameter and returns the maximum LCM that can be obtained from four numbers less than or equal to N.
Expected Time Complexity: O( Log2(max(N)) )
Expected Auxillary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/a-game-of-lcm2531/1
Hey Geeks! You can also share the approach you used to solve the problem in the comments.🙌
Powered by Hirist.com
"A Game of LCM"
Solve the problem to win points
Given an integer N. Find maximum LCM (Least Common Multiple) that can be obtained from four numbers less than or equal to N.
Note: Duplicate numbers can be used.
Example 1:
Input:
N = 4
Output: 12
Explanation:
The four numbers can be [4,4,3,2] or
[4,4,4,3], etc. It can be shown that 12 is
the maximum LCM of four numbers that can
be obtained from numbers less than or equal
to 4.
Example 2:
Input:
N = 5
Output: 60
Explanation:
The four numbers can be [5,5,4,3] or
[5,4,3,2], etc. 60 is the maximum that can
be obtained.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxGcd() which takes N as the input parameter and returns the maximum LCM that can be obtained from four numbers less than or equal to N.
Expected Time Complexity: O( Log2(max(N)) )
Expected Auxillary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/a-game-of-lcm2531/1
Hey Geeks! You can also share the approach you used to solve the problem in the comments.🙌
Powered by Hirist.com
practice.geeksforgeeks.org
A Game of LCM | Practice | GeeksforGeeks
Given an integer N. Find maximum LCM (Least Common Multiple) that can be obtained from four numbers less than or equal to N.
Note: Duplicate numbers can be used.
Example 1:
Input:
N = 4
Output: 12
Explanation:
The four num
Note: Duplicate numbers can be used.
Example 1:
Input:
N = 4
Output: 12
Explanation:
The four num
Must Do DSA Topics Day 65
Heap
Binary Heap : A Binary Heap is a Complete Binary Tree. A binary heap is typically represented as an array.
Learn more : https://bit.ly/3BKlHwD
Time Complexity of building a heap : Consider the following algorithm for building a Heap of an input array A.
Learn more : https://bit.ly/3jd2yx9
Applications of Heap Data Structure : Heap Data Structure is generally taught with Heapsort. Heapsort algorithm has limited uses because Quicksort is better in practice.
Learn more : https://bit.ly/3G3qWKI
Heap
Binary Heap : A Binary Heap is a Complete Binary Tree. A binary heap is typically represented as an array.
Learn more : https://bit.ly/3BKlHwD
Time Complexity of building a heap : Consider the following algorithm for building a Heap of an input array A.
Learn more : https://bit.ly/3jd2yx9
Applications of Heap Data Structure : Heap Data Structure is generally taught with Heapsort. Heapsort algorithm has limited uses because Quicksort is better in practice.
Learn more : https://bit.ly/3G3qWKI
👍1
Job Alert 🔊
Hubilo is hiring for Backend.
Candidates should have 6-8 years of experience. Do apply and share with your friends who might be interested in the position.
Get more details of the job: https://practice.geeksforgeeks.org/jobs/-TalentXO-Backend
Hubilo is hiring for Backend.
Candidates should have 6-8 years of experience. Do apply and share with your friends who might be interested in the position.
Get more details of the job: https://practice.geeksforgeeks.org/jobs/-TalentXO-Backend
Problem Of The Day
"Alex Travelling"
Solve the problem to win points
Alex is very fond of traveling. There are n cities, labeled from 1 to n. You are also given flights, a list of travel flights as directed weighted edges flights[i] = (ui,vi,wi) where ui is the source node, vi is the target node, and wi is the price it takes for a person to travel from source to target.
Currently, Alex is in k'th city and wants to visit one city of his choice. Return the minimum money Alex should have so that he can visit any city of his choice from k'th city. If there is a city that has no path from k'th city, which means Alex can't visit that city, return -1.
Alex always takes the optimal path. He can any city via another city by taking multiple flights.
Example 1:
Input:
n: 4
k: 2
flights size: 3
flights: [[2,1,1],[2,3,1],[3,4,1]]
Output:
2
Explanation:
to visit 1 from 2 takes cost 1
to visit 2 from 2 takes cost 0
to visit 3 from 2 takes cost 1
to visit 4 from 2 takes cost 2,
2->3->4
So if Alex wants to visit city 4
from 2, he needs 2 units of money
Example 2:
Input:
n: 4
k: 3
flights size: 3
flights: [[2,1,1],[2,3,1],[3,4,1]]
Output: -1
Explanation:
There is no direct or indirect path
to visit city 2 and 1 from city 3
Your Task:
You don't need to print or input anything. Complete the function minimumCost() which takes a flights array, an integer n and an integer k as the input parameters and returns an integer, denoting the minimum money Alex should have so that he can visit any city of his choice from k'th city.
Expected Time Complexity: O((V+E) log V), here V is number of cities and E is number of flights.
Expected Auxiliary Space: O(V+E), here V is number of cities and E is number of flights.
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/alex-travelling/1
Powered by hirist.com
"Alex Travelling"
Solve the problem to win points
Alex is very fond of traveling. There are n cities, labeled from 1 to n. You are also given flights, a list of travel flights as directed weighted edges flights[i] = (ui,vi,wi) where ui is the source node, vi is the target node, and wi is the price it takes for a person to travel from source to target.
Currently, Alex is in k'th city and wants to visit one city of his choice. Return the minimum money Alex should have so that he can visit any city of his choice from k'th city. If there is a city that has no path from k'th city, which means Alex can't visit that city, return -1.
Alex always takes the optimal path. He can any city via another city by taking multiple flights.
Example 1:
Input:
n: 4
k: 2
flights size: 3
flights: [[2,1,1],[2,3,1],[3,4,1]]
Output:
2
Explanation:
to visit 1 from 2 takes cost 1
to visit 2 from 2 takes cost 0
to visit 3 from 2 takes cost 1
to visit 4 from 2 takes cost 2,
2->3->4
So if Alex wants to visit city 4
from 2, he needs 2 units of money
Example 2:
Input:
n: 4
k: 3
flights size: 3
flights: [[2,1,1],[2,3,1],[3,4,1]]
Output: -1
Explanation:
There is no direct or indirect path
to visit city 2 and 1 from city 3
Your Task:
You don't need to print or input anything. Complete the function minimumCost() which takes a flights array, an integer n and an integer k as the input parameters and returns an integer, denoting the minimum money Alex should have so that he can visit any city of his choice from k'th city.
Expected Time Complexity: O((V+E) log V), here V is number of cities and E is number of flights.
Expected Auxiliary Space: O(V+E), here V is number of cities and E is number of flights.
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/alex-travelling/1
Powered by hirist.com
practice.geeksforgeeks.org
Alex Travelling | Practice | GeeksforGeeks
Alex is very fond of traveling. There are n cities, labeled from 1 to n. You are also given flights, a list of travel flights as directed weighted edges flights[i] = (ui,vi,wi) where ui is the source node, vi is the tar
Must Do DSA Topics Day 66
Heap
Binomial Heap : The main application of Binary Heap is as implement a priority queue. Binomial Heap is an extension of Binary Heap that provides faster union or merge operation with other operations provided by Binary Heap.
Learn more : https://bit.ly/3BKyWxB
Fibonacci Heap : Heaps are mainly used for implementing priority queue. We have discussed the below heaps in previous posts.
Learn more : https://bit.ly/3Wa2YTA
Leftist Heap : K-ary heap when used in the implementation of priority queue allows faster decrease key operation as compared to binary heap ( O(log2n)) for binary heap vs O(logkn) for K-ary heap).
Learn more : https://bit.ly/3HMClzQ
Heap
Binomial Heap : The main application of Binary Heap is as implement a priority queue. Binomial Heap is an extension of Binary Heap that provides faster union or merge operation with other operations provided by Binary Heap.
Learn more : https://bit.ly/3BKyWxB
Fibonacci Heap : Heaps are mainly used for implementing priority queue. We have discussed the below heaps in previous posts.
Learn more : https://bit.ly/3Wa2YTA
Leftist Heap : K-ary heap when used in the implementation of priority queue allows faster decrease key operation as compared to binary heap ( O(log2n)) for binary heap vs O(logkn) for K-ary heap).
Learn more : https://bit.ly/3HMClzQ