Labels

Project Euler #73: Counting fractions in a range

Question
Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

Answer : 7295372

Hacker Rank Problem

Solution 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Scanner;

public class Solution {
    private static int A;
    
    private static long rank(int n, long d) {
        long[] data = new long[A + 1];
        for(int i = 0; i < data.length; i++) {
            data[i] = i * n / d;
        }
        for(int i = 1; i < data.length; i++) {
            for(int j = 2 * i; j < data.length; j+= i) {
                data[j] -= data[i];
            }
        }
        long sum = 0;
        for(long x : data) {
            sum += x;
        }
        return sum;
    }
    
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)) {
            long D = sc.nextInt();
            A = sc.nextInt();
            long fromD = D + 1;
            System.out.println(rank(1, D) - rank(1, fromD) - 1);
        }
    }
}
Labels:

Comments

Post a Comment

Popular Posts