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

  • RobertsN + 2 comments

    No need for repeated subtractions or loops. It's purely O(1) (just straightforward formula split in two parts, two calculations).

    int q = ((3-(N%3))%3) *5;
if (N-q < 0)
	cout << -1 << endl;
else
	cout << string(N-q,'5') << string(q,'3') << endl;
    • chava_jauregui + 0 comments

      This is the most simplistic, elegant and optimal solution.

    • ggorlen + 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 + 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 + 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.