Algorithm: Sherlock And The Beast

 SHERLOCK AND THE BEAST

Bismillahirrahmanirrahim, 

My name is Muhammad Fazril Bin Azam Busra,1917135

In this blog, I saw an Interesting problem from Hackerrank. Since I'm one of the Sherlock Holmes fans, I wanted to try this problem to be dedicated to him. It's called Sherlock and The Beast.

MY UNDERSTANDING

First of all, the problem stated that Sherlock Holmes is having a suspicion towards Professor Moriarty regarding the professor's diabolical plan. Moriarty had provided some clues regarding his plan to sabotage The Beast with a virus

The beast is a supercomputer owned by m16 which has been the subject of involvements of Moriarty.

From the letter, Sherlock able to figure out some clues that in order to kill the virus, they have to find the largest decent numbers. 

A Decent Number has the following properties:

1. Its digits can only be 3's and/or 5's.
2. The number of 3's it contains is divisible by 5.
3. The number of 5's it contains is divisible by 3.
4. It is the largest such number for its length

To make things clearer, 55533333 is a decent numbers because it has 3 fives and 5 threes. 3 fives is divisible to 3 while 5 threes is divisable to 5. Lastly, it is also the largest value for those length numbers as well.

SOLUTION

To solve this problem, I will use C++ as my main language.

Here is my flowchart on how the algorithm in the function works:

Firstly,  we can solve this problem through greedy algorithm which is choosing the next piece that offers the most obvious and immediate benefits

For the first step of the algorithm, we will create a new function named DecentNumber() specifically for the main algorithm itself and create a temporary variable called m so that n value can be stored in it. (Remember that n is the length of the decent number to create)

int m = n;

Secondly, we created a while loop with conditions where m must be divisibile to 3 in order to stop the loop that contains a negation to 5

while (m % 3 != 0){ //the number is divisible to 3

        m -= 5;

    }

Thirdly, we will make an if-else statement to check whether there is a decent number in it or not.

If there is no decent number, the program will print "-1". Else, it will print the number based on n

value.

if (m < 0){ //no  decent number (-ve number and 0)

        cout<<"-1"<<endl;

    }

    else{ //there is a number

        cout<<string(m, '5')<<string(n-m,'3')<<endl;

    }

}

The test case provided in the website has proved that the algorithm works

as I able to pass all 16 test cases.

Here's how the logic applies:

That is all from me. Assalaumualaikum.