Thursday, April 14, 2016

[HACKERRANK] Problem analysis Manasa and Stone

Problem link:

Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either aa or bb. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 00, find all the possible values for the number on the last stone.
Note: The numbers on the stones are in increasing order.

Analysis: On this problem the questioner is asking for the possible combination of addition of a and b integer in an increasing series and the last number of the series. As it is an increasing series then it is must that either a or b will be added to the next number of the series. So possible combination for the n stone with 2 number (a and b) is 2^n number of solution. But as start stone is always 0, then you have 2^n-1 place. Now as your set consist of just 2 number you can get the number of solution by just increasing occurrence of a and decreasing the number of occurrence b. So at the end last number of the series is,

last num = a*num-occurrence + b * num-occurence

So for  n number of places iterate this equation for the all possible solution,

      last num = a*n + b*(max_place - 1 - n) //Where max_place is number of stone

N.B. Consider corner cases on input which is not added on the solution analysis.

No comments:

Post a Comment