Number of interesting numbers between two given numbers

Question

Please have a look into this problem:

Little Dipu is a small kid and like all the other kids, he likes to play, but he plays with numbers (he is extraordinary you know). Nowadays Dipu has some extra interest in odd numbers. So, he says that a number N is interesting if it has odd number of divisors. Now Dipu turns to you and asks you to tell him how many interesting numbers are there between two given numbers, L and R (both inclusive).

Input:

First line of input contains the number of test cases T. Each of the next T lines contains two space separated integers L and R.

Output:

For each test case, output an integer, denoting the count of interesting numbers between L and R (both inclusive).

Constraints:

• \$1 \le T \le 100000\$
• \$1 \le L \le R \le 1018\$

Sample input:

2
1 3
6 10

Sample output:

1
1

Below is a solution that I have come up with:

#include<stdio.h>
int main()
{

  long long int max,testcase,count,l,r;
  scanf("%lld",&testcase);

  while(testcase-->0)
  {
    max=0;
    scanf("%lld %lld",&l,&r);

    for(int i=l;i<=r;i++)
    {
      count=0;
      for(int j=1;j<=i;j++)
      {
        if(i%j==0)
        {
        count++;
        }
      }

      if(count%2!=0)
      {

          max=max+1;

      }
    }
    printf("%lld\n",max);


  }
}

The problem is the input constraint which is very large indeed, so my program will give the right outputs for some test cases but for larger inputs it will exceed the time allocated. Please help me to come up with another logic if possible which will make sure that the time allocated is not exceeded.

My program produces the right output but for larger inputs it takes more time than it should.

Answer 1

In that kind of problems, there is a solution a bit more interesting than a straight forward implementation of the logic described.

In your case, you could write a programme to generate the first numbers with the property you are looking for. You'll probably see a pattern that you could reuse (square numbers).

---

Update as this answer seems to be ignored so far.

Style

It's a good habit to move variable declaration as close as possible to where they are used.

Also, your code probably deserves a bit more spacing (this is how you avoid questions like this one) while a few things can be written in a slightly more concise way.

At this stage, my code looks like :

#include<stdio.h>

int main()
{
    long long int testcase;
    scanf("%lld",&testcase);

    while (testcase--)
    {
        long long int max = 0;
        long long int l, r;
        scanf("%lld %lld",&l,&r);

        for (int i = l ; i <= r; i++)
        {
            long long int count = 0;
            for (int j = 1; j <= i; j++)
            {
                if (i%j == 0)
                {
                    count++;
                }
            }

            if (count % 2)
            {
                max++;
            }
        }
        printf("%lld\n",max);
    }
}

Naming

max is a pretty poor name as it does not convey the right meaning. nb is probably better.

Types

Assuming 1≤L≤R≤10^18 (and not 1018), you will need a long type for i. However you don't need it for testcase.

Code organisation and tests

At the moment, all your code is in the main which makes things hard to test (and thus, to optimise). Let's decompose the code in small functions we'll be able to test and optimise.

At this stage, the code looks like :

#include<stdio.h>
#include<assert.h>

long long int nb_divisors(long long int i)
{
    long long int count = 0;
    for (int j = 1; j <= i; j++)
        if (i%j == 0)
            count++;
    return count;
}

int is_interesting(long long int i)
{
    return nb_divisors(i) % 2;
}

long long int nb_interesting(long long int l, long long int r)
{
    long long int nb = 0;
    for (long long int i = l ; i <= r; i++)
        if (is_interesting(i))
            nb++;
    return nb;
}

int main()
{
    if (0)
    {
        // stdio tests
        long long int testcase;
        scanf("%lld",&testcase);

        while (testcase--)
        {
            long long int l, r;
            scanf("%lld %lld",&l,&r);
            printf("%lld\n", nb_interesting(l, r));
        }
    }
    else
    {
        // automatic tests
        assert(nb_interesting(1, 3) == 1);
        assert(nb_interesting(6, 10) == 1);
    }
}

Algorithm

Here starts the interesting part. Your current algorithm considers all numbers from l to r and when checking if i is interesting or not, iterates all the way from 0 to i. For huge values of r, you'll have many calls to is_interesting and each of these calls will be slow.

A faster nb_divisors (from 0(n) to 0(sqrt(n)))

Let's try to see if we can make nb_divisors faster.

While trying to find divisors of i, you iterate from 1 to i. When you find a divisor d, you can consider d2 = n/d as another divisor. Then you have 3 situations : - either d < d2 - or d2 < d - or d == d2. You can limit yourself to divisors smaller than sqrt(n) and count them twice, then check if we have divisors alone.

my_int nb_divisors2(my_int i)
{
    my_int count = 0;
    my_int j;
    for (j = 1; j*j < i; j++)
        if (i%j == 0)
            count+=2;
    if (j*j == i)
        count++;
    return count;
}

Testing with :

    for (my_int i = 0; i < 1000; i++)
        assert(nb_divisors(i) == nb_divisors2(i)); 

This seems promising.

nb_divisors went from 0(n) to 0(sqrt(n)). This is particularly brilliant for big values of n.

A faster is_interesting (from 0(sqrt(n)) to 0(1))

Although making nb_divisors faster already makes is_interesting faster, we can make it even faster by re-using the insight we used : most divisors will be counted twice and a divisor will be counted once if and only if the number is a perfect square.

Reusing previous code, we can simply write :

int is_interesting2(my_int i)
{
    my_int j;
    for (j = 1; j*j < i; j++);
    return (j*j == i);
}

but it is still O(sqrt(n)). Using sqrt from math.h, you can write a 0(1) solution (solution taking a constant time):

int is_interesting2(my_int i)
{
    my_int root = sqrt(i);
    return (root && root*root == i);
}

A faster nb_interesting (from super-slow to O(1))

Altough making is_interesting faster already makes nb_interesting much faster, we can re-use what we've found to make it even faster.

First idea is just to count the number of perfect square between l and r. This is easy to write :

my_int nb_interesting2(my_int l, my_int r)
{
    my_int j;
    my_int nb = 0;
    for (j = 1; j*j < l; j++);
    for (     ; j*j <= r; j++)
            nb++;
    return nb;
}

(As usually, it comes along with unit tests to ensure we didn't break anything too badly).

This solution is O(sqrt(r)) as we go through all numbers up to sqrt(r).

We can go faster : let's assume we can compute the number of interesting up to a given number included nb_interesting_from_0(int i), then, we have nb_interesting_between(l, r) = nb_interesting_from_0(r) - nb_interesting_from_0(l - 1).

This fact only becomes interesting when we have a way to compute : nb_interesting_from_0(int i) and we have one, it is simply sqrt(i).

my_int nb_interesting2(my_int l, my_int r)
{
    return sqrt(r) - (my_int)sqrt(l-1);
}

This is 0(1) and pretty simple. Funny thing is that if you were to give me a simple calculator, I'd be able to provide you the number of interesting numbers between two limits very easily.