Labels

Project Euler #71: Ordered fractions

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 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

Answer :

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.Scanner;

public class Solution {
    private static long R1_HIGH = 0;
    private static long R1_LOW = 0;
    private static long R2_HIGH = 0;
    private static long R2_LOW = 0;
    private static void multiply(long a, long b, int i) {
        long shift = 4 * Long.SIZE;
        long mask = (long)~0 >> shift;
        
        long a_high = a >> shift;
        long a_low = a & mask;
        long b_high = b >> shift;
        long b_low = b & mask;
        
        long c_0 = a_low * b_low;
        long c_1a = a_high * b_low;
        long c_1b = a_low * b_high;
        long c_2 = a_high * b_high;
        
        long carry = ((c_0 >> shift) + (c_1a & mask) + (c_1b & mask)) >> shift;
        if(i == 1) {
            R1_HIGH = c_2 + (c_1a >> shift) + (c_1b >> shift) + carry;
            R1_LOW = c_0 + (c_1a << shift) + (c_1b << shift);
        } else if(i == 2) {
            R2_HIGH = c_2 + (c_1a >> shift) + (c_1b >> shift) + carry;
            R2_LOW = c_0 + (c_1a << shift) + (c_1b << shift);
        }
    }
    
    private static boolean isLess(long a, long b, long c, long d) {
        multiply(a, d, 1);
        multiply(c, b, 2);
        if(R1_HIGH < R2_HIGH) {
            return true;
        }
        if(R1_HIGH > R2_HIGH) {
            return false;
        }
        return (R1_LOW < R2_LOW);
    }
    
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)) {
            int T = sc.nextInt();
            while(T > 0) {
                long a = sc.nextLong();
                long b = sc.nextLong();
                long N = sc.nextLong();
                long leftN = 0;
                long leftD = 1;
                long rightN = 1;
                long rightD = 1;
                while((leftD + rightD) <= N) {
                    long mediantN = leftN + rightN;
                    long mediantD = leftD + rightD;
                    if(isLess(mediantN, mediantD, a, b)) {
                        leftN = mediantN;
                        leftD = mediantD;
                    } else {
                        rightN = mediantN;
                        rightD = mediantD;
                        if(rightN == a && rightD == b) {
                            break;
                        }
                    }
                }
                if(N >= (leftD + rightD)) {
                    long difference = N - (leftD + rightD);
                    long repeat = 1 + difference / rightD;
                    leftN += repeat * rightN;
                    leftD += repeat * rightD;
                }
                System.out.println(leftN + " " + leftD);
                T--;
            }
        }
    }
}
Labels:

Comments

Post a Comment

Popular Posts