hackProblem 1: Marble cut
Link to the problem: https://www.hackerrank.com/contests/101hack22/challenges/marble-cut
My solution:
Actually I was unable to solve this problem completely during the contest and till now I couldn’t understand what my mistake was. I present my solution below and people who have solve this problem completely are kindly requested to write their logic in the comments.
My solution was, if the product l and b is a multiple of 3 then the answer is “YES”. Else the answer is “NO” and the remaining area is (l*b)%3.
Problem 2: Permutation of Natural numbers
Link to the problem:
https://www.hackerrank.com/contests/101hack22/challenges/permutation-of-natural-numbers
My solution:
Imagine for a moment that the string contained only ‘I’ and NO ‘D’ atall. For.ex : consider the following string:
S= III…..’n’ times.
The answer to the above string is 1 2 3 ……. n n+1.
This follows from the fact that if s[i]=’I’ then X[i]<X[i+1]
Now let us add only one ‘D’ to the above string.
Now S = III….D…..III (length of the string is n)
My claim is that the position where ‘D’ resides will contain the maximum value in the answer i.e here n+1. ( readers are asked to verify it by themselves)
Let us assume maxm=n+1
Now we can fill the positions which to the left of ‘D’ in the following manner:
We move from ‘D’ towards the left decrementing the value of maxm each time. Hence the answer will look like below.
……n-2 n-1 n n+1 ……
Next, the right side of ‘D’ looks similar to the sub problem which we have solved earlier. So start by filling with ‘1’ from the rightside of ‘D’
Thus the final answer will look like:
….n-2 n-1 n n+1 1 2 3 ……
The final algorithm to the question is below:
1. Initialise the value of maxm=n+1 and array x = { 0 }
2. Scan through your string till you reach ‘D’. Put the value of maxm in this position in ‘X’ and move backward till X[i] = 0, and decrement the value of maxm each time & store it at X[i].
3. Continue step 2 till no value of X[i] is 0.
4. Finally, Print X[i]
Happpppy Coding guys!! :) :)
Link to the problem: https://www.hackerrank.com/contests/101hack22/challenges/marble-cut
My solution:
Actually I was unable to solve this problem completely during the contest and till now I couldn’t understand what my mistake was. I present my solution below and people who have solve this problem completely are kindly requested to write their logic in the comments.
My solution was, if the product l and b is a multiple of 3 then the answer is “YES”. Else the answer is “NO” and the remaining area is (l*b)%3.
Problem 2: Permutation of Natural numbers
Link to the problem:
https://www.hackerrank.com/contests/101hack22/challenges/permutation-of-natural-numbers
My solution:
Imagine for a moment that the string contained only ‘I’ and NO ‘D’ atall. For.ex : consider the following string:
S= III…..’n’ times.
The answer to the above string is 1 2 3 ……. n n+1.
This follows from the fact that if s[i]=’I’ then X[i]<X[i+1]
Now let us add only one ‘D’ to the above string.
Now S = III….D…..III (length of the string is n)
My claim is that the position where ‘D’ resides will contain the maximum value in the answer i.e here n+1. ( readers are asked to verify it by themselves)
Let us assume maxm=n+1
Now we can fill the positions which to the left of ‘D’ in the following manner:
We move from ‘D’ towards the left decrementing the value of maxm each time. Hence the answer will look like below.
……n-2 n-1 n n+1 ……
Next, the right side of ‘D’ looks similar to the sub problem which we have solved earlier. So start by filling with ‘1’ from the rightside of ‘D’
Thus the final answer will look like:
….n-2 n-1 n n+1 1 2 3 ……
The final algorithm to the question is below:
1. Initialise the value of maxm=n+1 and array x = { 0 }
2. Scan through your string till you reach ‘D’. Put the value of maxm in this position in ‘X’ and move backward till X[i] = 0, and decrement the value of maxm each time & store it at X[i].
3. Continue step 2 till no value of X[i] is 0.
4. Finally, Print X[i]
Happpppy Coding guys!! :) :)