Inti Sets: Hackerank 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&lt;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&lt;=b; i++){

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


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

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

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

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

}
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 &lt; 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 &lt;= 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&lt;Long&gt; primeFactors(long n) {
    List&lt;Long&gt; factors = new ArrayList&lt;Long&gt;();
    long md = 2;
    if (n % md == 0) {
        factors.add(md);
        do {
            n /= md;
        } while (n % md == 0);
    }
    md = 3;
    while (md &lt;= java.lang.Math.sqrt(n) + 1) {
        if (n % md == 0) {
            factors.add(md);
            do {
                n /= md;
            } while (n % md == 0);
        }
        md += 2;
    }
    if (n &gt; 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&lt;Long&gt; 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 &lt; 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&lt;Long&gt; primes = primeFactors(n);

    long sum = inclExcl(a, b, 1, primes) % MOD;
    if (sum &lt; 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.