Problem Of The Day
"GCD Array"

Solve the problem to win points

You are given an array, arr of length N, and also a single integer K . Your task is to split the array arr into K non-overlapping, non-empty subarrays. For each of the subarrays, you calculate the sum of the elements in it. Let us denote these sums as S1, S2, S3, ..., SK. Where Si denotes the sum of the elements in the ith subarray from left.

Let G = GCD( S1, S2 ,S3 , ..., SK).

Find the maximum value of G that can be obtained.
The array may contain duplicate elements.

Example 1:
Input:
N = 5
K = 4
arr[] = {6, 7, 5, 27, 3}
Output: 3
Explanation:
Since K = 4, you have to split the array into 4 subarrays.
For optimal splitting, split the array into
4 subarrays as follows: [[6], [7, 5], [27], [3]]
Therefore, S1 = 6, S2 = 7 + 5 = 12, S3 = 27, S4 = 3
Hence, G = GCD(S1, S2, S3, S4) = GCD(6, 12, 27, 3) = 3
It can be shown that 3 is the maximum value of G that can be obtained.
Thus, the answer is 3.

Example 2:
Input:
N = 3
K = 2
arr[] = {1, 4, 5}
Output: 5
Explanation:
Since K = 2, you have to split the array into 2 subarrays.
For optimal splitting, split the array into
2 subarrays as follows: [[1, 4], [5]]
Therefore, S1 = 1 + 4 = 5, S2 = 5
Hence, G = GCD(S1, S2) = GCD(5,5) = 5
It can be shown that 5 is the maximum value of G that can be obtained.
Thus, the answer is 5.

Your Task:
You don't need to read input or print anything. Your task is to complete the function solve() which takes the array arr[] and its size N and an integer K as input parameters and returns the required maximum GCD value.


Expected Time Complexity: O(N * x)
Expected Auxiliary Space: O(x), x is the number of factors of the sum of all elements.

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

Powered by hirist.com

Problem Of The Day

"Geeks And The String"

Solve the problem to win points

Our geek loves to play with strings, Currently, he is trying to reduce the size of a string by recursively removing all the consecutive duplicate pairs. In other words, He can apply the below operations any number of times.

Remove all the consecutive duplicate pairs and concatenate the remaining string to replace the original string.
Your task is to find the string with minimum length after applying the above operations.

Note: If the string length become zero after applying operations, return "-1" as a string.


Example 1:
Input:
aaabbaaccd
Output:
ad
Explanation:
Remove (aa)abbaaccd =>abbaaccd
Remove a(bb)aaccd => aaaccd
Remove (aa)accd => accd
Remove a(cc)d => ad

Example 2:
Input:
aaaa
Output:
Empty String
Explanation:
Remove (aa)aa => aa
Again removing pair of duplicates then (aa)
will be removed and we will get 'Empty String'.

Your Task:
This is a function problem. You only need to complete the function removePair() that takes a string as a parameter and returns the modified string. Return an empty string if the whole string is deleted.

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

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

Powered by hirist.com

Must Do DSA Topics Day 95
Segment Tree
Segment Tree introduction : A simple solution is to run a loop from l to r and calculate the sum of elements in the given range. To update a value, simply do arr[i] = x. The first operation takes O(n) time and the second operation takes O(1) time.
Learn more : http://bit.ly/3XwFZTf

Range Minimum Query : We have introduced segment tree with a simple example in the previous post. In this post, Range Minimum Query problem is discussed as another example where Segment Tree can be used.
Learn more : http://bit.ly/3ZXylDd

Persistent Segment Tree : Segment Tree is itself a great data structure that comes into play in many cases. In this post we will introduce the concept of Persistency in this data structure. Persistency, simply means to retain the changes.
Learn more : http://bit.ly/3GZzbGL

Must Do DSA Topics Day 95
Segment Tree
Segment Tree introduction : A simple solution is to run a loop from l to r and calculate the sum of elements in the given range. To update a value, simply do arr[i] = x. The first operation takes O(n) time and the second operation takes O(1) time. 
Learn more : http://bit.ly/3XwFZTf

Range Minimum Query : We have introduced segment tree with a simple example in the previous post. In this post, Range Minimum Query problem is discussed as another example where Segment Tree can be used.
Learn more : http://bit.ly/3ZXylDd

Persistent Segment Tree : Segment Tree is itself a great data structure that comes into play in many cases. In this post we will introduce the concept of Persistency in this data structure. Persistency, simply means to retain the changes.
Learn more : http://bit.ly/3GZzbGL

🚨Job Alert 🚨
Midland Credit Management is hiring for Engineer III in Gurgaon.

Hurry up! The last date to apply is 31st January.

Apply via the following link and share it with your friends - https://practice.geeksforgeeks.org/jobs/mcmencore-SEIII

Problem Of The Day

"Convert an array to reduced form"

Solve the problem to win points

Given an array with N distinct elements, convert the given array to a reduced form where all elements are in range from 0 to N-1. The order of elements is same, i.e., 0 is placed in place of smallest element, 1 is placed for second smallest element, N-1 is placed for largest element.

Note: You don't have to return anything. You just have to change the the given array.

Example 1:
Input:
N = 3
Arr[] = {10, 40, 20}
Output: 0 2 1
Explanation: 10 is the least element so it
is replaced by 0. 40 is the largest
element so it is replaced by 3-1 = 2. And
20 is the 2nd smallest element so it is
replaced by 1.

Example 2:
Input:
N = 5
Arr[] = {5, 10, 40, 30, 20}
Output: 0 1 4 3 2
Explanation: As 5 is smallest element,
it's replaced by 0. Then 10 is 2nd
smallest element, so it's replaced by 1.
Then 20 is 3rd smallest element, so it's
replaced by 2. And so on.
Your Task:
You don't need to read input or print anything. Your task is to complete the function convert() which takes the array of integers arr and n as parameters and make changes in the given array.

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

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/convert-an-array-to-reduced-form1101/1

Powered by hirist.com

Must Do DSA Topics Day 96
Segment Tree
Min-Max Range Queries in Array : Given an array arr[0 . . . n-1]. We need to efficiently find the minimum and maximum value from index qs (query start) to qe (query end) where 0 <= qs <= qe <= n-1.
Learn more : http://bit.ly/3D5vqhV

Range LCM Queries : Given an array arr[] of integers of size N and an array of Q queries, query[], where each query is of type [L, R] denoting the range from index L to index R, the task is to find the LCM of all the numbers of the range for all the queries.
Learn more : http://bit.ly/3XKL76c

Maximum Occurrence in a Given Range : Given an array of n integers in non-decreasing order. Find the number of occurrences of the most frequent value within a given range.
Learn more : http://bit.ly/3R3QoDv

Get access to all the topics of Segment Tree : https://www.geeksforgeeks.org/segment-tree-data-structure/?ref=gcse

Problem Of The Day

"Type it!"

Solve the problem to win points

Geek is extremely punctual but today even he is not feeling like doing his homework assignment. He must start doing it immediately in order to meet the deadline. For the assignment, Geek needs to type a string s.
To reduce his workload, he has decided to perform one of the following two operations till he gets the string.

Append a character at the end of the string.
Append the string formed thus far to the end of the string. (This can not be done more than once.)
Help Geek find the minimum operations required to type the given string.

Example 1:
Input:
s = abcabca
Output: 5
Explanation: a -> ab -> abc -> abcabc
-> abcabca

Example 2:
Input:
s = abcdefgh
Output: 8
Explanation: a -> ab -> abc -> abcd
-> abcde -> abcdef -> abcdefg -> abcdefgh

Your Task:
You don't need to read input or print anything. Your task is to complete the function minOperation() which takes a string s as input parameter and returns the minimum operations required to type it.

Expected Time Complexity: O(N2)
Expected Auxiliary Space: O(1)

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

Powered by hirist.com

Must Do DSA Topics Day 97
Disjoint Set
Introduction to Disjoint Set Data Structure or Union-Find Algorithm : A disjoint-set data structure is defined as a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
Learn more : http://bit.ly/3wp3IZP

Disjoint Set Union on trees : Given a tree, and the cost of a subtree is defined as |S|*AND(S) where |S| is the size of the subtree and AND(S) is bitwise AND of all indices of nodes from the subtree, task is to find maximum cost of possible subtree.
Learn more : http://bit.ly/40e857N

Dynamic Disjoint Set Data Structure for large range values : Disjoint Set data structure is used to keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
Learn more : http://bit.ly/3DfgMEN

🚨Job Alert 🚨
Gainsight is hiring Senior/ Software Engineer in Hyderabad.

Last date to apply - Jan 31, 2023

Hurry up!

Apply via the following link and share the opportunity with your friends - https://practice.geeksforgeeks.org/jobs/Gainsight_backend

Kya Bolti Re-Public?

Happy Republic Day! 🇮🇳

Problem Of The Day
"Case-specific Sorting of Strings"

Solve the problem to win points

Given a string S consisting of only uppercase and lowercase characters. The task is to sort uppercase and lowercase letters separately such that if the ith place in the original string had an Uppercase character then it should not have a lowercase character after being sorted and vice versa.

Example 1:
Input:
N = 12
S = defRTSersUXI
Output: deeIRSfrsTUX
Explanation: Sorted form of given string
with the same case of character as that
in original string is deeIRSfrsTUX

Example 2:
Input:
N = 6
S = srbDKi
Output: birDKs
Explanation: Sorted form of given string
with the same case of character will
result in output as birDKs.
Your Task:
You only need to complete the function caseSort that takes a string str and length of the string n and returns sorted string.

Expected Time Complexity: O(Nlog(N)).
Expected Auxiliary Space: O(N).

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/case-specific-sorting-of-strings4845/1

Powered by hirist.com

Problem Of The Day
"Total Decoding Message"

Solve the problem to win points

A top secret message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
You are an FBI agent. You have to determine the total number of ways that message can be decoded, as the answer can be large return the answer modulo 109 + 7.
Note: An empty digit sequence is considered to have one decoding. It may be assumed that the input contains valid digits from 0 to 9 and If there are leading 0s, extra trailing 0s and two or more consecutive 0s then it is an invalid string.

Example 1:
Input: str = "123"
Output: 3
Explanation: "123" can be decoded as "ABC"(123),
"LC"(12 3) and "AW"(1 23).

Example 2:
Input: str = "90"
Output: 0
Explanation: "90" cannot be decoded as it's an invalid string and we cannot decode '0'.

Your Task:
You don't need to read or print anything. Your task is to complete the function CountWays() which takes the string as str as input parameter and returns the total number of ways the string can be decoded modulo 109 + 7.

Expected Time Complexity: O(n)
Expected Space Complexity: O(n) where n = |str|

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/total-decoding-messages1235/1

Powered by hirist.com

Must Do DSA Topics Day 98
Disjoint Set
Job Sequencing Problem using Disjoint Set : Given a set of n jobs where each job i has a deadline di >=1 and profit pi>=0. Only one job can be scheduled at a time. Each job takes 1 unit of time to complete.
Learn more : http://bit.ly/3kDcXmi

Python Set isdisjoint() Method : Python set isdisjoint() function check whether the two sets are disjoint or not, if it is disjoint then it returns True otherwise it will return False. Two sets are said to be disjoint when their intersection is null.
Learn more : http://bit.ly/3kOregh

Disjoint Set Union (Randomized Algorithm) : Overall, the disjoint set union algorithm is a useful tool for efficiently managing a collection of disjoint sets. It can be used in a variety of applications, including clustering, graph coloring, and image segmentation.
Learn more : http://bit.ly/3Rf0ulg

Get access to all the topics of Disjoint Set : https://www.geeksforgeeks.org/tag/disjoint-set/?ref=gcse

🚨Job Alert 🚨

NCode Technologies is hiring MEAN Stack Developer in Ahmedabad, Gujarat.

Experience - 2+ Years
Last date to apply - Feb 28, 2023

Hurry Up!

Apply via the following link and share the opportunity with your friends - https://practice.geeksforgeeks.org/jobs/NCode-Mean

Problem Of The Day
"Scrambled String"

Solve the problem to win points

Given two strings S1 and S2 of equal length, the task is to determine if S2 is a scrambled form of S1.

Scrambled string: Given string str, we can represent it as a binary tree by partitioning it into two non-empty substrings recursively.
Below is one possible representation of str = coder:

To scramble the string, we may choose any non-leaf node and swap its two children.
Suppose, we choose the node co and swap its two children, it produces a scrambled string ocder.
Similarly, if we continue to swap the children of nodes der and er, it produces a scrambled string ocred.

Note: Scrambled string is not the same as an Anagram.

Print "Yes" if S2 is a scrambled form of S1 otherwise print "No".

Example 1:
Input: S1="coder", S2="ocder"
Output: Yes
Explanation: ocder is a scrambled
form of coder.

ocder
/ \
oc der
/ \
o c

As "ocder" can represent it
as a binary tree by partitioning
it into two non-empty substrings.
We just have to swap 'o' and 'c'
to get "coder".

Example 2:
Input: S1="abcde", S2="caebd"
Output: No
Explanation: caebd is not a
scrambled form of abcde.

Your Task:
You don't need to read input or print anything. You only need to complete the function isScramble() which takes two strings S1 and S2 as input and returns a boolean value.

Expected Time Complexity: O(N2)
Expected Auxiliary Space: O(N2)

Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/scrambled-string/1

Powered by hirist.com

Problem Of The Day
"Min operations"

Solve the problem to win points

Given two numbers a and b. In one operation you can pick any non negative integer x and either of a or b. Now if you picked a then replace a with a&x else if you picked b then replace b with b&x.

Return the minimum number of operation required to make a and b equal.

Note: Here & represents bitwise AND operation.

Example 1:
Input:
a = 5, b = 12
Output:
2
Explanantion:
In first operation replace
a = a&4 = 4
after that replace
b = b&6 = 4
Hence both are same after applying two
operations.

Example 2:
Input:
a = 100, b = 100
Output:
0
Explanation:
Already same.

Your Task:
You don't need to read, input, or print anything. Your task is to complete the function solve( ), which takes two integers a and b as input parameters and returns the answer.

Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)

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

Powered by hirist.com

Problem Of The Day
"Select Nodes"

Solve the problem to win points

Given N nodes of a tree and a list of edges. Find the minimum number of nodes to be selected to light up all the edges of the tree.
An edge lights up when at least one node at the end of the edge is selected.

Example 1:
Input:
N = 6
edges[] = {(1,2), (1,3), (2,4), (3,5), (3,6)}
Output: 2
Explanation: Selecting nodes 2 and 3 lights
up all the edges.

Example 2:
Input:
N = 3
arr[] = {(1,2), (1,3)}
Output: 1
Explanation: Selecting Node 1
lights up all the edges.

Your Task:
You don't need to read input or print anything. Your task is to complete the function countVertex() which takes the number of nodes N, and the list of edges as input parameters and returns the minimum number of nodes selected.


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

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

Powered by hirist.com

Must Do DSA Topics Day 99
Projects
OpenCV C++ Program for Face Detection : This program uses the OpenCV library to detect faces in a live stream from webcam or in a video file stored in the local machine. This program detects faces in real time and tracks it. It uses pre-trained XML classifiers for the same.
Learn more : http://bit.ly/3HgV44C

OpenCV C++ Program to blur an image : The idea is to first use a function called cvtColor to convert the input image into Grayscale image, then we will convert that Grayscale image to Blurred Image using a function GaussianBlur.
Learn more : http://bit.ly/40dO1SC

Creating a PortScanner in C : Ports are numbered for consistency and programming. The most commonly used and best known ports are those numbered 0 to 1023 dedicated for Internet use, but they can extend far higher for specialized purposes.
Learn more : http://bit.ly/40oShz9

Problem Of The Day

"Minimum times A has to be repeated such that B is a substring of it"

Solve the problem to win points

Given two strings A and B. Find minimum number of times A has to be repeated such that B is a Substring of it. If B can never be a substring then return -1.

Example 1:
Input:
A = "abcd"
B = "cdabcdab"
Output:
3
Explanation:
Repeating A three times (abcdabcdabcd),
B is a substring of it. B is not a substring
of A when it is repeated less than 3 times.

Example 2:
Input:
A = "ab"
B = "cab"
Output :
-1
Explanation:
No matter how many times we repeat A, we can't
get a string such that B is a substring of it.

Your Task:
You don't need to read input or print anything. Your task is to complete the function minRepeats() which takes 2 strings A, and B respectively and returns the minimum number of times A has to be repeated such that B is a substring of it. Return -1 if it's not possible.


Expected Time Complexity: O(|A| * |B|)
Expected Auxiliary Space: O(|B|)

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

Powered by hirist.com