Must Do DSA Topics Day 83
Greedy
Set cover problem : Given a universe U of n elements, a collection of subsets of U say S = {S1, S2…,Sm} where every subset Si has an associated cost. Find a minimum cost subcollection of S that covers all elements of U.
Learn more : https://bit.ly/3GfkY8h

Bin Packing Problem : Given n items of different weights and bins each of capacity c, assign each item to a bin such that number of total used bins is minimized. It may be assumed that all items have weights smaller than bin capacity.
Learn more : https://bit.ly/3VQBi50

Graph Coloring : As discussed in the previous post, graph coloring is widely used. Unfortunately, there is no efficient algorithm available for coloring a graph with minimum number of colors as the problem is a known NP Complete problem.
Learn more : https://bit.ly/3WMa0y7

Job Alert💼

kbx Digital is hiring for a Software Development Engineer role in Chennai. Candidates must have experience of over 1 to 7 years.

Click on the following link for more details and to apply, also, share the opportunity with your friends- https://practice.geeksforgeeks.org/jobs/KBXDigitalSDE

Problem Of The Day
"Shortest Prime Path"

Solve the problem to win points

You are given two four digit prime numbers Num1 and Num2. Find the distance of the shortest path from Num1 to Num2 that can be attained by altering only one single digit at a time. Every number obtained after changing a digit should be a four digit prime number with no leading zeros.


Example 1:
Input:
Num1 = 1033
Num2 = 8179
Output: 6
Explanation:
1033 -> 1733 -> 3733 -> 3739 -> 3779
-> 8779 -> 8179.
There are only 6 steps required to reach
Num2 from Num1, and all the intermediate
numbers are 4 digit prime numbers.

Example 2:
Input:
Num1 = 1033
Num2 = 1033
Output:
0

Your Task:
You don't need to read input or print anything. Your task is to

Complete the constructor of the class Solution to precompute a list of prime numbers.
Complete function shortestPath() which takes two integers Num1 and Num2 as input parameters and returns the distance of the shortest path from Num1 to Num2. If it is unreachable then return -1.

Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/1646a9b5169d7571cf672f2a31533af083d1f479/1

Powered by hirist.com

Must Do DSA Topics Day 84
Greedy
Split n into maximum composite numbers : Given n, print the maximum number of composite numbers that sum up to n. First few composite numbers are 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, ………
Learn more : https://bit.ly/3vI1zYE

Maximum trains for which stoppage can be provided : We are given n-platform and two main running railway track for both direction. Trains which needs to stop at your station must occupy one platform for their stoppage and the trains which need not to stop at your station will run away through either of main track without stopping.
Learn more : https://bit.ly/3ZgvnsP

Buy Maximum Stocks if i stocks can be bought on i-th day : In a stock market, there is a product with its infinite stocks. The stock prices are given for N days, where arr[i] denotes the price of the stock on the ith day.
Learn more : https://bit.ly/3GM482p

Get access to all the topics of Greedy : https://www.geeksforgeeks.org/greedy-algorithms/?ref=gcse

Hey Geeks! We won't let you give up on your resolutions this year.😃🤌

Resolution Days sale of 2023 is live now!!!✨

Click on the following link to avail exciting offers - https://practice.geeksforgeeks.org/courses?utm_source=telegram&utm_medium=marketingteam_gfgmain&utm_campaign=rd2023

Problem Of The Day
"Flattening a Linked List"

Solve the problem to win points

Given a Linked List of size N, where every node represents a sub-linked-list and contains two pointers:
(i) a next pointer to the next node,
(ii) a bottom pointer to a linked list where this node is head.
Each of the sub-linked-list is in sorted order.

Flatten the Link List such that all the nodes appear in a single level while maintaining the sorted order.

Note: The flattened list will be printed using the bottom pointer instead of next pointer.

Example 1:
Input:
5 -> 10 -> 19 -> 28
| | | |
7 20 22 35
| | |
8 50 40
| |
30 45
Output: 5-> 7-> 8- > 10 -> 19-> 20->
22-> 28-> 30-> 35-> 40-> 45-> 50.
Explanation:
The resultant linked lists has every
node in a single level.
(Note: | represents the bottom pointer.)

Example 2:
Input:
5 -> 10 -> 19 -> 28
| |
7 22
| |
8 50
|
30
Output: 5->7->8->10->19->22->28->30->50
Explanation:
The resultant linked lists has every
node in a single level.

(Note: | represents the bottom pointer.)

Your Task:
You do not need to read input or print anything. Complete the function flatten() that takes the head of the linked list as input parameter and returns the head of flattened link list.

Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/da62a798bca208c7a678c133569c3dc7f5b73500/1

Powered by hirist.com

Knock! Knock!😃
The New Year Party goes on with upto 25% off on your favourite courses and much more!🎊

Click on the following for more details - https://practice.geeksforgeeks.org/courses?utm_source=telegram&utm_medium=marketingteam_gfgmain&utm_campaign=rd2023

Get ready for some DSA lectures with Mr. Sandeep Jain (Mentor of DSA Self Paced , CEO & Founder) as he will join you LIVE for the next 3 months! So if you were looking for a reason to join, now’s the time!

You can attend his LIVE community classes by enrolling in any one of the 2 courses-


DSA Self Paced: https://practice.geeksforgeeks.org/courses/dsa-self-paced


Complete Interview Preparation: https://practice.geeksforgeeks.org/courses/complete-interview-preparation

——————————————-

So start today! 💯

Problem Of The Day
"Absolute difference divisible by K"

Solve the problem to win points

Given an array of integers of size n and an integer k, find all the pairs in the array whose absolute difference is divisible by k.

Example 1:
Input:
n = 3
arr[] = {3, 7, 11}
k = 4
Output:
3
Explanation:
(11-3) = 8 is divisible by 4
(11-7) = 4 is divisible by 4
(7-3) = 4 is divisible by 4

Example 2:
Input:
n = 4
arr[] = {1, 2, 3, 4}
k = 2
Output :
2
Explanation:
Valid pairs are (1,3), and (2,4).

Your Task:
You don't need to read input or print anything. Your task is to complete the function countPairs() which takes integers n, array arr[ ], integer k as input parameters and returns the number of pairs whose absolute difference is divisible by k.
Note: The answer may be large so use 64-bit integer.


Expected Time Complexity: O(n + k)
Expected Auxiliary Space: O(k)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/e0059183c88ab680b2f73f7d809fb8056fe9dc43/1

Powered by hirist.com

Problem Of The Day
"Last modified ball"

Solve the problem to win points

Samwell laid out N bowls in a straight line and put a few marbles randomly in each bowl, ith bowl has A[i] marbles. A bowl can never have more than 9 marbles at a time. A bowl can have zero marbles. Now Samwells friend adds one more marble to the last bowl, after this addition all the bowls must still be aligned with the rules mentioned above. Adding a marble follows the same rules as of addition with carryover. You are given the initial list of the number of marbles in each bowl find the position of the bowl which was last modified. It is guaranteed that there is at least one bowl which has at least one space left.

Note: Consider one-based indexing.

Input:
N = 4
A[] = {3, 1, 4, 5}
Output:
4
Explanation:
The last bowl has 5 marbels, we can just
add the marbel here.

Example 2:
Input:
N = 3
A[] = {1, 9, 9}
Output:
1
Explanation:
When we add the marbel to last bowl we
have to move one marbel to 2nd bowl,
to add the marbel in 2nd bowl we have
to move one marbel to 1st bowl.
Hence the last modified bowl is 1.

Your Task:
You don't need to read input or print anything. Your task is to complete the function solve( ) which takes N and A[ ] as input parameters and returns the position of the last modified bowl.

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/33af95e5935f1f2a0c3f5083c4b9d0db68e97bd4/1

Powered by hirist.com

Must Do DSA Topics Day 85
Backtracking
Introduction to Backtracking – Data Structure and Algorithm Tutorials : Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time.
Learn more : https://bit.ly/3GsupRI

Backtracking Algorithms : Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.
Learn more : https://bit.ly/3GZl3yF

Word Break Problem using Backtracking : Given a valid sentence without any spaces between the words and a dictionary of valid English words, find all possible ways to break the sentence into individual dictionary words.
Learn more : https://bit.ly/3CwcUPe

Resolution Days 2023 are keeping the spirit of skills up with upto 25% off on your favourite courses.

Today's special offer includes GFG Premium Plus' subscription worth INR 2000 for free.

For more details, click on the following link- https://practice.geeksforgeeks.org/courses?utm_source=telegram&utm_medium=marketingteam_gfgmain&utm_campaign=rd2023

🚨Job Alert 🚨

QUOLAM BUSINESS is hiring for Node JS Developer role in Mahape, Navi Mumbai.

Get more details in the following link and also share the opportunity with your friends - https://practice.geeksforgeeks.org/jobs/Quolam-Nodejs

Problem Of The Day
"Transform to Sum Tree"

Solve the problem to win points

Given a Binary Tree of size N , where each node can have positive or negative values. Convert this to a tree where value of each node will be the sum of the values of all the nodes in left and right sub trees of the original tree. The values of leaf nodes are changed to 0.
Note: You have to modify the given tree in-place.


Example 1:

Input:
10
/ \
-2 6
/ \ / \
8 -4 7 5
Output:
20
/ \
4 12
/ \ / \
0 0 0 0
Explanation:
(4-2+12+6)
/ \
(8-4) (7+5)
/ \ / \
0 0 0 0

Example 2:

Input:
10
/ \
-2 6
/ \ / \
8 -4 7 5
/ \ / \ / \ / \
2 -2 3 -5 9 -8 2 8
Output:
29
/ \
2 23
/ \ / \
0 -2 1 10
/ \ / \ / \ / \
0 0 0 0 0 0 0 0
Explanation:
(2+6+8-4+7+5+2-2+3-5+9-8+2+8)
/ \
(8-4+2-2+3-5) (7+5+9-8+2+8)
/ \ / \
(2-2) (3-5) (9-8) (2+8)
/ \ / \ / \ / \
0 0 0 0 0 0 0 0

Your Task:
You dont need to read input or print anything. Complete the function toSumTree() which takes root node as input parameter and modifies the given tree in-place.

Note: If you click on Compile and Test the output will be the in-order traversal of the modified tree.


Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/d7e0ce338b11f0be36877d9c35cc8dfad6636957/1

Powered by hirist.com

Must Do DSA Topics Day 86
Backtracking
Difference between Backtracking and Branch-N-Bound technique : Algorithms are the methodical sequence of steps which are defined to solve complex problems. In this article, we will see the difference between two such algorithms which are backtracking and branch and bound technique. 
Learn more : https://bit.ly/3QrZGc8

m Coloring Problem | Backtracking-5 : Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with the same color.
Learn more : https://bit.ly/3GtLPO2

Travelling Salesman Problem implementation using BackTracking : Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns back to the starting point.
Learn more : https://bit.ly/3GqwzBz

Tik! Tik! Tik!⏱️

Last Day Today!!!🎊
It's the last day of the Resolution Days sale, 2023.

Hurry up and avail upto 25% off on your favourite courses.

Click here for more details - https://practice.geeksforgeeks.org/courses?utm_source=telegram&utm_medium=marketingteam_gfgmain&utm_campaign=rd2023

Problem Of The Day
"Make array elements unique"

Solve the problem to win points

Given an array arr[ ] of N elements, your task is to find the minimum number of increment operations required to make all the elements of the array unique. ie- no value in the array should occur more than once. In an operation a value can be incremented by 1 only.

Example 1:
Input:
N = 3
arr[] = {1, 2, 2}
Output:
1
Explanation:
If we increase arr[2] by 1 then the resulting
array becomes {1, 2, 3} and has all unique values.
Hence, the answer is 1 in this case.

Example 2:
Input:
N = 4
arr[] = {1, 1, 2, 3}
Output:
3
Explanation:
If we increase arr[0] by 3, then all array
elements will be unique. Hence, the answer
is 3 in this case.
Your Task:
You dont need to read input or print anything. Complete the function minIncrements() which takes the array arr[ ] and its size N as the input parameters, and returns the minimum increment operations required to make all elements of the array unique.

Expected Time Complexity: O(N*log(N))
Expected Auxiliary Space: O(1)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/6e63df6d2ebdf6408a9b364128bb1123b5b13450/1

Powered by hirist.com

Must Do DSA Topics Day 87
Backtracking
Rat in a Maze | Backtracking using Stack : A Maze is given as N*M binary matrix of blocks and there is a rat initially at (0, 0) ie. maze[0][0] and the rat wants to eat food which is present at some given block in the maze (fx, fy).
Learn more : https://bit.ly/3WYtEaa

Perl | Backtracking in Regular Expression : In Perl, a Regular expression(a.k.a regexes or regexps or REs) is a way of describing a set of strings without having to list all strings in your program or simply we can say that it is a sequence of characters that are used for pattern matching.
Learn more : https://bit.ly/3k2eORn

C/C++ Backtracking Programs : Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that “works”. Problems that are typically solved using the backtracking technique have the following property in common.
Learn more : https://bit.ly/3X3hEUY

Problem Of The Day
"Minimize the sum"

Solve the problem to win points

You are given N elements, you can remove any two elements from the list, note their sum, and add the sum to the list. Repeat these steps while there is more than a single element in the list. The task is to minimize the sum of these chosen sums.

Example 1:
Input:
N = 4
arr[] = {1, 4, 7, 10}

Output:
39

Explanation:
Choose 1 and 4, Sum = 1 + 4 = 5.
arr[] = {5, 7, 10}
Choose 5 and 7, Sum = 5 + (5 + 7) = 17.
arr[] = {12, 10}
Choose 12 and 10, Sum = 17 + (12 + 10) = 39.
arr[] = {22}


Example 2:
Input:
N = 5
arr[] = {1, 3, 7, 5, 6}

Output:
48


Your Task:

You don't need to read input or print anything. The task is to complete the function minimizeSum() which takes N as size of arr array and a arr array. Your task is to minimize the sum of these chosen sums and return it.

Expected Time Complexity: O(N * log(N))
Expected Auxiliary Space: O(N)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/86e609332c9ef4f6b8aa79db11a6c0808c4a1bca/1

Powered by hirist.com

Must Do DSA Topics Day 88
Backtracking
Split a string into maximum number of unique substrings : Given string str, the task is to split the string into the maximum number of unique substrings possible and print their count.
Learn more : https://bit.ly/3keY7Cc

Print all possible ways to split an array into K subsets : Given an array arr[] of size N and an integer K, the task is to print all possible ways to split the given array into K subsets.
Learn more : https://bit.ly/3X2qIt6

Print all root to leaf paths of an N-ary tree : Given an N-Ary tree, the task is to print all root to leaf paths of the given N-ary Tree.
Learn more : https://bit.ly/3X8Iyee