Inti Sets: Hackerank

Question

Here is the original question.

In order to motivate his Peruvian students, a teacher includes words in the Quechua language in his math class.

Today, he defined a curious set for a given positive integer N. He called this set, an Inti set, and defined it as the set of all positive integer numbers that have the number 1 as their single common positive divisor with number N.

The math class about Inti sets was amazing. After class, the students try to challenge to teacher. They each ask questions like this: "Could you tell me the sum of all numbers, between A and B (inclusive), that are in the Inti set of N?"

Since the teacher is tired and he's sure that you are the best in class, he wants to know if you can help him.

Input Format

The first line of input contains an integer Q, 1 ≤ Q ≤ 20, representing the number of students. Each of the next Q lines contain three space-separated integers N, A and B, which represent a query.

Constraints

1 ≤ A ≤ B ≤ N ≤ 10^12

Output Format

The output is exactly Q lines, one per student query. For each query you need to find the sum of all numbers between A and B, that are in the Inti set of N, and print the sum modulo 1000000007.

Sample Input

2 
12 5 10 
5 1 4

Sample Output

12 10

Explanation

In the sample input, Q = 2, so you have to answer two questions:

In the first question N = 12, A = 5 and B = 10. So you have to find the sum of all numbers between 5 and 10, that are in the Inti set of 12.

Inti set ( 12 ) = { 1, 5, 7, 11, 13, ... }

2 and 4 are not in the Inti set (12) because 12 and these numbers are also divisible by 2.

3 and 9 are not in the Inti set (12) because 12 and these numbers are also divisible by 3.

The numbers in the Inti set, which are in the query's range, are 5 and 7, so answer is ( 5 + 7 ) MOD 1000000007 = 12

In the second question, the numbers in the Inti set of 5 between 1 and 4 are: 1, 2, 3, 4; so the answer is ( 1 + 2 + 3 + 4 ) MOD 1000000007 = 10

My code keep getting timeout. Is there any approach to tackle this question?

Here the A, B, N values can be very large. It can be upto 10^12

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

        Scanner console = new Scanner(System.in);

        int queries = Integer.parseInt(console.nextLine());
        int[][] qArr = new int[queries][];

        for (int i=0; i<queries; i++){
            int N = console.nextInt();
            int A = console.nextInt();
            int B = console.nextInt();
            int[] singleLine = new int[3];
            singleLine[0] = N;
            singleLine[1] = A;
            singleLine[2] = B;
            qArr[i] = singleLine;
            console.nextLine();

        }

        for(int[] line : qArr){

            int N = line[0];
            int A = line[1];
            int B = line[2];


            //calculate sum
            long result = sumBetweenRange(A, B, N);
            System.out.println(result);

        }
    }


    private static long sumBetweenRange(int a, int b, int n){
        long sum = 0l;

        for(int i=a; i<=b; i++){

            if(!isCommonFactorAvailable(i, n)){
                sum += i;
            }
        }
        return sum;
    }


    private static boolean isCommonFactorAvailable(int no1, int no2){

        if(no1 != 1 && no2%no1 == 0){
            return true;
        }

        for(int i=2; i<no1/2; i++){

            if(no1%i == 0 && no2%i == 0){
                return true;
            }
        }
        return false;
    }

}

Answer 1

The input numbers \$ A, B, N \$ can be as large as \$ 10^{12} \$, which means that a Java int (which is a 32-bit signed integer) is not large enough to hold all possible values, you should use long instead.

You also do not reduce the sum modulo 1000000007, as required.

The main function can be simplified by calculating the output for each input line as it is read, this makes the queries array obsolete.

The function sumBetweenRange does not describe what the function actually does. Something like sumOfIntiNumbersInRange or – using the mathematical term – sumOfCoprimeNumbersInRange might be a better choice.

The main function would then look like this:

public static void main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

    Scanner console = new Scanner(System.in);

    int queries = Integer.parseInt(console.nextLine());

    for (int i = 0; i < queries; i++) {
        long N = console.nextLong();
        long A = console.nextLong();
        long B = console.nextLong();

        long result = sumOfCoprimeNumbersInRange(A, B, N);
        System.out.println(result);
    }
}

Your method to determine if two numbers have a common factor is very slow, it does trial division for all numbers between 2 and no1/2. That can be improved slightly by using sqrt(no1) as the upper bound, but one can do much better.

An efficient method is the Euclidean algorithm which determines the greatest common divisor of two integers. Two integers \$ a, b \$ have no common divisor exactly if \$ \gcd(a, b) = 1 \$.

There are many known Java functions for calculation the greatest common divisor, see for example https://rosettacode.org/wiki/Greatest_common_divisor#Java. Here is a simple (tail-recursive) implementation:

public static long gcd(long a, long b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

Then sumOfCoprimeNumbersInRange() can be implemented as

private static final int MOD = 1000000007;

// Compute the sum (modulo MOD) of all numbers in the range a...b which are coprime to N.
private static long sumOfCoprimeNumbersInRange(long a, long b, long n) {
    long sum = 0;

    for(long i = a; i <= b; i++){
        if (gcd(i, n) == 1) {
            sum = (sum + i) % MOD;
        }
    }
    return sum;
}

This is already much faster than your original implementation: For \$ N=100000, A=10000, B=90000 \$ I measured on a 1.2 GHz Intel Core m5 MacBook:

• Your code: 3 seconds.
• GCD-based solution: 0.165 seconds.

But it may be not fast enough for the full range of numbers up to \$ 10^{12} \$. A very elegant and efficient approach using the Inclusion-Exclusion Principle is explained in

• How to count co-prime to n in a range [1,x] where x can be different from n?

on Stack Overflow. Let us consider \$ N = 300 = 2^2 \cdot 3 \cdot 5^2 \$ as an example. The distinct prime factors are \$ 2, 3, 5 \$, and to compute the sum of all numbers in some range which are coprime to \$ N \$ one proceeds as follows:

• Compute the sum of all numbers in the range.
• Subtract the sum of all multiples of \$ 2, 3 \$, and \$ 5 \$ in the range.
• Add the sum of all multiples of \$ 2 \cdot 3, 2 \cdot 5 \$, and \$ 3 \cdot 5 \$ in the range.
• Subtract the sum of all multiples of \$ 2 \cdot 3 \cdot 5 \$ in the range.

Note that apart from the factorization, no trial divisions are required anymore, only multiplications.

First we need a function to get the distinct prime factors of a given number, e.g. the function in Finding out the prime factors of a number, modified slightly to return only distinct prime factors:

// List of all distinct prime factors of n.
static List<Long> primeFactors(long n) {
    List<Long> factors = new ArrayList<Long>();
    long md = 2;
    if (n % md == 0) {
        factors.add(md);
        do {
            n /= md;
        } while (n % md == 0);
    }
    md = 3;
    while (md <= java.lang.Math.sqrt(n) + 1) {
        if (n % md == 0) {
            factors.add(md);
            do {
                n /= md;
            } while (n % md == 0);
        }
        md += 2;
    }
    if (n > 1) {
        factors.add(n);
    }
    return factors;
}

Now the "challenge" is to translate the Inclusion-Exclusion approach to a recursive function, and that could look as follows:

// Sum of all numbers 1...k, computed modulo MOD.
private static long sumUpTo(long k) {
    k = k % MOD; // Otherwise the following multiplication can overflow.
    let sum = k * (k+1) / 2;
    return sum % MOD;
}

// Sum of all numbers (modulo MOD) in a...b which are divisible by k, but not
// by any multiple of k with factors in the primes list: 
private static long inclExcl(long a, long b, long k, List<Long> primes) {

    // Sum of all numbers in 1...b which are divisible by k:
    long s1 = sumUpTo(b / k) * k;
    // Sum of all numbers in 1...(a-1) which are divisible by k:
    long s2 = sumUpTo((a-1) / k) * k;

    long sum = (s1 - s2) % MOD;

    for (int idx = 0; idx < primes.size(); idx++) {
        // The magic recursion!
        sum = (sum - inclExcl(a, b, k * primes.get(idx), primes.subList(idx + 1, primes.size()))) % MOD;
    }

    return sum;
}

private static long sumOfCoprimeNumbersInRange(long a, long b, long n) {

    List<Long> primes = primeFactors(n);

    long sum = inclExcl(a, b, 1, primes) % MOD;
    if (sum < 0) {
        sum += MOD;
    }
    return sum;
}

For a (hopefully) better understanding of the implementation, here is how the inclExcl function is called recursively if \$ N = 300 = 2^2 \cdot 3 \cdot 5^2 \$ as above (showing only the relevant arguments):

k=1, primes=[2, 3, 5]
    k=2, primes=[3, 5]
        k=6, primes=[5]
            k=30, primes=[]
        k=10, primes=[]
    k=3, primes=[5]
        k=15, primes=[]
    k=5, primes=[]

This is again much faster, because we have to iterate and recurse only over the distinct prime factors of \$ N \$ (and there can be no more than \$ 11 \$ prime factors if \$ N \le 10^{12} \$). There is no iteration over the range \$ A \ldots B \$ anymore.

Benchmark: For \$ N=96996900, A=100, B=96996000 \$:

• GCD-based solution: 26 seconds.
• Inclusion/exclusion-based solution: 0.181 seconds.

Answer 2

private static long sumBetweenRange(int a, int b, int n){
    long sum = 0l;

    for(int i=a; i<=b; i++){

        if(!isCommonFactorAvailable(i, n)){
            sum += i;
        }
    }
    return sum;
}


private static boolean isCommonFactorAvailable(int no1, int no2){

    if(no1 != 1 && no2%no1 == 0){
        return true;
    }

    for(int i=2; i<no1/2; i++){

        if(no1%i == 0 && no2%i == 0){
            return true;
        }
    }
    return false;
}

You constantly refactor N. You shouldn't do this - just factor N once, then compare each number with the factors of N.

Additionally, your factorization algorithm doesn't use primes, it just counts up from 2. If something is not divisible by 2, it's not going to be divisible by 4 or by 6 or by 8, so you should only check primes.

Therefore, I think you should use a different algorithm:

First, create a list of primes from 1 to sqrt(n). You can cache this list of primes.

Then, factorize N using the list of primes.

Then compare the factors of N with the factors of each of the numbers in the range A to B, failing fast as you have done right now, stopping once you see a match (you don't factorize the number into all of it's factors first, you stop the moment you find a matching factor).

Afterwards, sum the results.

---

So let's talk about big O notation. It's what we use to show the order of things - specifically, the order of growth of execution time of an algorithm.

\$O(n)\$ is "scales linearily as n grows". This would be things like iterating over a list - the larger the list, the longer it takes. More importantly, make the list twice as big, and the iterating takes twice as long.

\$O(n^2)\$ is "scales exponentially as n grows". This would be things like iterating over two lists or a 2D array. Make a board from 4x4 to 8x8, and you go from 16 to 64 - a 4x growth.

When we look at the performance of your code, we notice this:

    for(int i=a; i<=b; i++){

First, you iterate over all the numbers in the range. So as the range grows, your algorithm takes longer. That's \$O(n)\$.

But in this loop, you check for the greatest common divisor...

 if(!isCommonFactorAvailable(i, n)){

Which is done by iterating over all the possible factors.

The worst case for that algorithm is, again, iteration, making this \$O(n^2)\$. That means that if A, B and N are very large, you might need to do 1e24 iterations ((B - A) * N).

What my suggested algorithm would do is first factor N properly.

Prime factorization using a sieve can take \$O(n \log \log n)\$ if done properly. "log" here means "grows by 1x as N grows by 10x". So 1 = 1, 10 = 2, 100 = 3...

This makes large numbers not matter, because 1e3 = 3, 1e12 = 12, and these are small numbers.

Next, since it only uses a smaller list of factors to compare with, finding the greatest common divisor takes a lot less time. For comparison, here's a site that shows the amount of primes in a number range. Relevant for our case: in 1e12, there are 3.7e10 primes (3.7%). But since we only need to check for divisors, we only care about primes that could reach N, and thus we only need the primes that are up to 1e7. That's 664,579 primes, and that's better than the 499,999,999,999 iterations you currently make for checking if a number has a common factor with N.

But since we don't need to check all the primes, just the prime factors of N, it's very possible that N just has 10 prime factors or so. Cutting the checks down to 10 iterations. For example, 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 = 200,560,490,130. That's the 11 lowest prime factors, and we can't add one more without going over 1e12.

The resulting speed of the algorithm would first be making a list of primes (n log log n), then iterating over B - A (n), then comparing this with the prime factors of n (log n). Making the algorithm pretty much take \$O(n)\$ in terms of speed.