HackerRank 'Sherlock and the Beast' Solution

by Srikant Padala on April 13, 2016, 1:48 pm


Explanation


Get all the valid combinations of 5s and 3s and maximize the number of 5s.


Sherlock and the Beast Problem Statement

Video

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

void getCombs(vector<pair<int,int>> &combs, int n) {
    int num_3=0, num_5=0;
    while(true) {
        num_5 = n - num_3;
        if(num_5 < 0) break;
        if(num_5 % 3 == 0) combs.push_back(make_pair(num_5, num_3));
        num_3+=5;
    }
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        vector<pair<int,int>> combs;
        getCombs(combs,n);
        if(combs.size() > 0) {
            pair<int,int> maximum = *max_element(combs.begin(), combs.end());
            for(int i=0; i < maximum.first; i++) {
                cout << 5;
            }
            for(int i=0; i < maximum.second; i++) {
                cout << 3;
            }
            cout << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

Coming Soon.