8
\$\begingroup\$

I've exceeded the time limit on Sherlock and Squares on hackerrank.com.

Problem

Given the number of test cases and a range (inclusive), find the number of numbers within that range that are perfect squares.

Sample Input

  • 2 (number of test cases)
  • 3 9 (first test case)
  • 17 24 (second test case)

Sample Output

  • 2 (in range [3,9], there are two perfect square numbers)
  • 0 (in range [17, 24], there are no perfect square numbers)

My code in C++

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main()
{
  unsigned test_cases, low_range, high_range, count = 0;
  vector<unsigned> sherlock_squares;
  cin >> test_cases;
  while(test_cases != 0)
  {
    cin >> low_range >> high_range;
    for(unsigned i = low_range; i <= high_range; ++i)
    {
      if(sqrt(i) == floor(sqrt(i)))
        count += 1;
    }
    sherlock_squares.push_back(count);
    count = 0;
    --test_cases;
  }
  for(unsigned i = 0; i < sherlock_squares.size() - 1; ++i)
    cout << sherlock_squares.at(i) << endl;
  cout << sherlock_squares.at(sherlock_squares.size() - 1);
  return 0;
}

I'd appreciate it if an explanation is provided in your response, since I'm new to programming and Stack Exchange.

\$\endgroup\$
  • 5
    \$\begingroup\$ @tachma Hint: There's a constant time solution to this problem. Remember, if you have a range of numbers from [x,y] then the square roots of all the numbers lie between [sqrt(x), sqrt(y)]. The number of perfect squares is the number of whole numbers between sqrt(x) and sqrt(y). \$\endgroup\$ – Aayush Agrawal Jul 2 '16 at 19:36
  • \$\begingroup\$ @Aayush Agrawal, thanks for the comment! I improved my code. :D \$\endgroup\$ – tachma Jul 2 '16 at 20:31
  • 1
    \$\begingroup\$ Aayush Agrawal has given you a way to REALLY speed up your program. Try it out on the first sample of 3,9: If you take the square roots of those numbers, you get about 1.7 and 3 - the only integers between 1.7 and 3 (inclusive) are 2 and 3 - or two perfect squares (2*2 and 3*3). Using this, you only have to take the square roots of your inputs, and find all the integers between them - MUCH faster than the sqrt() in a loop! \$\endgroup\$ – Dave P. Jul 4 '16 at 3:01
10
\$\begingroup\$
using namespace std;

Why is “using namespace std;” considered bad practice?

Personally, I find code more readable if it says what namespace is being used. E.g. std::sqrt.

  unsigned test_cases, low_range, high_range, count = 0;

Three of these variables are only used inside the loop, so you can simplify by just saying

  unsigned test_cases;

As a general rule, you should declare variables at the smallest scope where they are needed.

  while(test_cases != 0)
  {
    cin >> low_range >> high_range;

Some people prefer for loops for this kind of situation.

  for (; test_cases > 0; --test_cases)
  {
     uint32_t count = 0;
     uint32_t low_range, high_range;
     std::cin >> low_range >> high_range;

Also added declarations inside the loop for variables that are only used inside the loop. Note how this also takes care of resetting the count on each iteration. This saves clearing the count after it's no longer used, which your original code does.

Note that unsigned is not guaranteed to be a 32-bit integer, although it almost always will be. Using uint32_t guarantees 32 bits and is found in #include <stdint.h>.

    for(unsigned i = low_range; i <= high_range; ++i)
    {
      if(sqrt(i) == floor(sqrt(i)))
        count += 1;
    }

First, why not say

      {
        count++
      }

That's simpler than count += 1;.

I am unsure of how I can simplify my code for this HackerRank activity:

But you are experiencing a timeout. You don't need to make it simpler. You need to make it faster.

Rather than calculating the square root on every iteration, calculate them only once.

    // +1 because both ends are inclusive
    // floor to keep within the high end (inclusive)
    // ceil to keep within the low end (inclusive)
    int32_t count = (unsigned)std::floor(std::sqrt(high_range)) - (unsigned)std::ceil(std::sqrt(low_range)) + 1;
    if (count < 0)
    {
      count = 0;
    }
    sherlock_squares.push((uint32_t)count);

I was originally going to do a for loop where I only calculated the squares, but I realized that I didn't have to do so. This will get the right answer consistently. It counts the number of integers from the square root of A to the square root of B. That will correspond to the number of squares between A and B, since we're only counting the squares of integers.

  for(unsigned i = 0; i < sherlock_squares.size() - 1; ++i)
    cout << sherlock_squares.at(i) << endl;
  cout << sherlock_squares.at(sherlock_squares.size() - 1);

Rather than subtracting 1 from the end, add 1 to the beginning. That saves math operations.

  std::cout << sherlock_squares.at(0);
  for (unsigned i = 1; i < sherlock_squares.size(); ++i)
  {
    std::cout << '\n' << sherlock_squares.at(i);
  }

Switching from std::endl to '\n' is faster, as std::endl triggers a flush, which you don't need here. Probably not the performance bottleneck in this case, but it can be in some cases.

Always using the block form of control structures is more reliable and simplifies source control if you add statements in the future.

But I actually think that what the challenge wanted was

  for (auto sherlock_square : sherlock_squares)
  {
    std::cout << sherlock_square << '\n';
  }

with new lines after every line rather than only between them.

It may even have wanted you to interleave input and output. But that's uncertain.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your detailed post! I'll try to edit my code and see if the re-submission works. \$\endgroup\$ – tachma Jul 2 '16 at 19:38
1
\$\begingroup\$

One big observation is that you don't need to check all of the numbers in the range given, but rather you need to check the set of perfect squares that fit in that range.

In other words, instead of iterating over the range, you can start with the smallest perfect square outside the range, and keep going up by perfect squares until you exceed it, counting as you go. For your first example you would start with 2 (square inside the range), 3 (inside) and so on until the square is outside the range (4). For example:

int i = std::ceil(std::sqrt(low_range));
while(i*i <= high_range){
   count++;
   i++;
}

Additionally, since this is a challenge with a known domain, you can precompute the squares so you can have an array of squares that you iterate over (so your while statement would be squares[i] <= high_range.

\$\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.