Discussion on Sherlock and The Beast Challenge

ggorlen 2 years ago+ 1 comment

I didn't downvote since this is a perfectly fine answer, but are you sure string() isn't using a loop under the hood? The solutions using a while loop in these examples will only iterate twice at most, which is O(1). Solutions on this page are pretty much all O(n) because of the string multiplication loops which are the most expensive part of the function. Correct me if I'm mistaken!

RobertsN 2 years ago+ 1 comment

I've no idea how the string constructor is built under the hood. From the user code perspective it is O(1). Likewise many other solutions when written in Python or other higher level languages probably do have hidden loops in the language implementation. BTW someone else did downvote (not that I really care) but didn't say why...

ggorlen 2 years ago+ 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 1 year ago+ 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.