Thursday, 26 March 2015

Hackerrank Manasa and Stones Solution

Problem Statement
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 aor b. 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 0, find all the possible values for the number on the last stone.
Note: The numbers on the stones are in increasing order.

Source Code:

 #include <cmath>  
 #include <cstdio>  
 #include <vector>  
 #include <iostream>  
 #include <algorithm>  
 #include <string.h>  
 using namespace std;  
 int main() {  
   /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
   int t;  
   cin>>t;  
   while(t--){  
     int n,a,b,gt,lw;  
     cin>>n>>a>>b;  
     if(a>b){  
       gt =a ;  
       lw = b;  
     }else{  
       lw = a;  
       gt = b;  
     }  
     int ans = lw*(n-1);  
     n--;  
     int dif = gt-lw;  
     cout<<ans<<" ";  
     if(dif>0){  
       while(n--){  
         ans += dif;  
         cout<<ans<<" ";  
       }  
     }  
     cout<<endl;  
   }  
   return 0;  
 }  

** The above solution is my own code and it may not be the optimal solution or optimal way to approach the problem but it passes all the testcases in Hackerrank. So if you have any optimal approaches feel free to paste the code as the comment below..... :) :) :)

2 comments:

  1. My way (just takes a loop):
    for(int i = 0 ; i <= n; ++i)
    sortedSet.add(A*i + B*(n-i));

    ReplyDelete
  2. I love your solution (the guy who commented above) but it's a little wrong, the for loop is supposed be:
    ```for(int i = 1; i <= n; i++) // 0 -> n = n + 1 elements! and 0 is always 0 (given)```
    and your inside condition is supposed to be ```a*(i - 1) + b*(n - i);```

    ReplyDelete