4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Related question \$\endgroup\$ – Flambino Dec 23 '15 at 6:12
  • \$\begingroup\$ 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. \$\endgroup\$ – dragosht Dec 23 '15 at 9:16
3
\$\begingroup\$

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');
if (n-j) {
    dn += std::string(n-j, '3');
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.