# Hackerrank - “Sherlock and the Beast”

I solved the problem but for two test cases, it's giving me timeout error. It's taking longer than 2 seconds on their servers. I tried using <ctime> to calculate the run time of the program and on my system, it's taking between 1.3-1.6 seconds. It's only giving me error for TestCases #9 and #10.

The question is to find the largest N-digit "decent" number, where a decent number consists only of the digits '3' and '5', and the number of threes is divisible by 5, and the number of fives is divisible by 3.

#include <iostream>
#include <string>

std::string decent_number(int, std::string);

int main() {
clock_t start = clock();
int numOfCases;

std::cin >> numOfCases;
int n;
for (int i = 0; i < numOfCases; ++i) {
std::string dn("-1");
std::cin >> n;
for (int j = n; j >= 0; --j) {
if (j % 3 == 0 && (n-j) % 5 == 0) {
dn = decent_number(j, "5");
dn += decent_number(n-j, "3");
break;
}
}
std::cout << dn << std::endl;
}
clock_t ends = clock();
std::cout << "Time: " << static_cast<double>(ends - start)/ CLOCKS_PER_SEC
<< std::endl;
return 0;
}

std::string decent_number(int repeatNum, std::string num) {
std::string dn;
for (int i = 0; i < repeatNum; ++i)
dn = dn + num;
return dn;
}


The code is simple, I check for the number of 3s and 5s which make the number and call a string builder function which builds the string.

• Related question – Flambino Dec 23 '15 at 6:12
• I don't remember this problem, but apparently I've solved it at some point. Just by looking at my accepted submission and cross-referencing I'd say you ditch all those string operations. You can easily solve the problem without them. – dragosht Dec 23 '15 at 9:16

Your problem is clearly caused by that decent_number function of yours. Once you have the number of '5' digits and the number of '3' digits, just dump the number to the console - building an std::string to hold it is totally redundant:
Your program currently takes Time: 1.71979 on my system when running Test 9 (which fails in the HackerRank test environment). If instead of building that string you simply print the digits it takes: Time: 0.026608.
Alternatively you could simply build the whole strings from the start (instead of using the loop to append one character at a time) - this works even faster: Time: 0.000818.
dn = std::string(j, '5');