We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Algorithms
  3. Greedy
  4. Sherlock and The Beast
  5. Discussions

Sherlock and The Beast

  • ggorlen + 1 comment

    O(1) means that this method runs just as fast on n = 1,000,000,000 as it does on n = 10, which isn't the case. The string multiplication is the performance bottleneck causing the algorithm to be O(n) rather than O(1). Here's some test code showing that the code is O(n) due to the string() call (I'm not a C++ programmer, so pardon any mistakes):

    #include <ctime>
#include <iostream>
#include <sstream>
using namespace std;

void sherlock(int N) {
  clock_t begin = clock();
  int q = ((3-(N%3))%3) *5;
  if (N-q < 0) {
	  cout << -1 << endl;
  }
  else {
    std::stringstream buffer;
    buffer << string(N-q,'5') << string(q,'3') << endl;
  }
  clock_t end = clock();
  cout << double(end - begin) << endl;
}

int main() {
  cout << "N = 5: ";
  sherlock(5);
  cout << "N = 100000000: ";
  sherlock(100000000);
  return 0;
}

/*
gcc version 4.6.3

N = 5: 29
N = 100000000: 143633
*/

    My main point is that a lot of folks are mistakenly assuming the while loop solution is not O(1). The loop in this case is O(1) because regardless of how large n is, the loop body will never execute more than twice at most, so from an efficiency standpoint there is no difference as advertised. See the below code:

    #include <ctime>
#include <iostream>
#include <sstream>
using namespace std;

void sherlock(int N) {
  clock_t begin = clock();
  int t = 0;
  while (N % 3 != 0) {
    N -= 5;
    t += 5;
  }
  std::stringstream buffer;
  buffer << string(N, '5') << string(t, '3') << endl;
  clock_t end = clock();
  cout << double(end - begin) << endl;
}

int main() {
  cout << "N = 5: ";
  sherlock(5);
  cout << "N = 100000000: ";
  sherlock(100000000);
  return 0;
}

/*
gcc version 4.6.3
   
N = 5: 18
N = 100000000: 109843
*/
    • amdokamal + 0 comments

      You are right, there is a but. The author of Editorial and other people simply neglect "multiplying strings" and other operations because the performance difference in comparison with the Sherlock algorithm O(1) is extremely small at the level of 1 <= n <= 100000.