Wonder String-1 - Mindstormer April 20

Wonder String

Question Breif

Given a string containing just the characters 'a', 'b', 'c', 'd', 'e' and 'f', determine if the input string is wonder or not.

Pairs are known as (opening element,closing element) : (a,b), (c,d), (e,f)

An input string is wonder if:

First(opening element) element of pair must be closed by the second(closing element) element of the pair
Opening element must be closed by respective closing element in the correct order
Note that an empty string is also considered wonder string:

Link To Question:
https://www.hackerrank.com/contests/mindstormer-apr20/challenges/wonder-string-1

Approach:
Hint: Use Stack
If an opening element occurs we push it into stack and when the closing element occurs, we check if the element at the top of stack is corresponding opening element . If its some other element then we return false. Else we pop out the top most element. If at the end of string stack is empty then we return true.

Another way to think : We can have (), {}, [] instead of ab , cd , ef.

Here is the Solution:

Comments

Brilliant Mind - Mindstormer April 20 (Product Of All Perfect Square Term Upto A Given No 'n')

Product Of All Perfect Square Term Upto n Question Brief : A Number 'n' is given to you , you are said to find the product of all the perfect square term less than or equal to n. Prequisite : Basic Mathematics, Preprocessing Approach : Perfect Square numbers upto any number n are only these: (1 2 ,2 2 ,........,(√n) 2 ) In Question it was asked to find the product of all perfect square numbers.i.e. ans = (1 2 x 2 2 x....... x (√n) 2 ) it can be easily transformed to: ans = (1 x 2 x....... x √n ) 2 ans= (√n!) 2 So, in each query , for given value of any n, we had to print the square of factorial of square root of n. This can be easily answered in O(1) if we already preprocess the number 1 to sqrt(N) and store their factorial already. SETTER CODE :

Happy Group - Mindstormer April 20

Happy Group Question Breif A group of blocks is said to be connected if we can reach from any given block to any other block in the same group, and this group is known as happy group . Given N blocks (numbered from 1 to N) and two lists of size M (u and v) denoting block u[i] is connected to block v[i] and vice versa . Can you count the number of happy groups. Note: A block is always connected to himself Link to question: https://www.hackerrank.com/contests/mindstormer-apr20/challenges/happy-group Approach: Graph- BFS we keep arrays u and v as given in the question. We create a 2D array-edges(ed) which keep record of whichblocks are connected with each other. We maintain visited array(vis) that keep record of which block is visited and which is left. Further explanation is in the comments with the code. The main thing used is BFS and graph to solve this problem

The Thinker's Thesaurus - Mindstormer April 20

Satisfy the condition: x*p^x ≡ q (mod r) Problem Brief : Tanu is a pre final year cs student. She has been given an integer I. And has been asked to compute how many integers x ( 1 <= x <= I) satisfy the below condition:- x*p x ≡ q (mod r) Prerequisite : Basic Mathematics Approach : Brute force solution won't work as 'I' is in range of 10^10 . So we need to find out some features of that given equation. We have p r-1 ≡1(mod r) where r is a prime number by Fermat's Little Theorem , it is obvious that p z mod r falls into a loop and the looping section is r−1. Also, z mod r has a looping section r .We can try to list a chart to show what x*p x is with some specific i,j. (In the chart shown below, x is equal to i*(r-1) + j. Proof for the chart shown above: For a certain i,j we can see that x *p^x mod r= ((i*(r−1)+j)mod r)* x ^ (i...

SSDC - HIVE OF DEVELOPERS

Search This Blog