Skip to main content

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

Labels:

Comments

Post a Comment

Popular posts from this blog

Makarov's Ambition - Mindstormer April 20

 Makarov's Ambition - Mindstormer April 20  Question Brief   :            Two numbers s (number of states) and d (number of districts) followed by a series of 'n' numbers (0 and 1) will be given to you such that s*d=n. All you have to do is check that is there any way to divide the series into n parts such that in majority of states, the guild is victorious. The guild wins if more than half of the districts are won by the guild. Also the division will be consecutive. For example: if s=3, d=2 and series is a1, a2, a3, a4, a5, a6. so division can be made in only these two ways : (a1, a2), (a3, a4), (a5, a6) (a2, a3), (a4, a5), (a6,a1) Prequisite   :   Basic Programming Approach   :         We have to take two arrays, one to store the series and other stores the sum of series till that index. There can be only that number of ways to divide the states as many district...
Post a Comment
Read more

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  :
Post a Comment
Read more

PRIME DISTANCE : MINDSTORMER - APR20

PRIME DISTANCE - MINDSTORMER QUESTION BRIEF : In the question A number X(secret no) was given to you, and you had to recursively do following things. Represent X in the form of  2 n -z  Find Nearest Prime no(y) to z Assign x=y Repeat the process, untill x becomes less than or equal to 2, because there is no prime no less than 2. Prerequisite  : Preprocessing, Recursion,Brute Force Approach : According to constraint, x may be upto 500000 and the no of queries asked for x might be upto 100000. So for perfect solution , all the three points must be done not more than O(1) for a step and for any starting value of x , it will converge to 2 very quickly. Preprocessing : For number ranging from 1 to 1000000, we will store these three calculations already  Prime no just less than it Bool (True or False) if current no is a prime Just next big Power of 2 Do Recursion and do each iteration in O(1) only. Algorithm : Intiali...
Post a Comment
Read more