Twitter OA prepare: Rational Sum - neverlandly - 博客园


Twitter OA prepare: Rational Sum - neverlandly - 博客园
In mathematics, a rational number is any number that can be expressed in the form of a fraction p/q , where p & q are two integers, and the denominator q is not equal to zero. Hence, all integers are rational numbers  where denominator, in the most reduced form, is equal to 1.
You are given a list of N rational number, {a1/b1, a2/b2, ..., aN/bN}. Print the sum ( = a1/b1 + a2/b2 + ... + aN/bN = num/den) in the most reduced form.
Input
The first line of input contains an integer, N, the number of rational numbers.  N lines follow. ithline contains two space separated integers, ai bi, where aiis the numerator and bi is the denominator for the ith rational number.
Output
You have to print two space separated integers, num den, where num and den are numerator and denominator of the sum respectively.
Constraints
1 <= N <= 15
1 <= ai <= 10
1 <= bi <= 10
Notes
Make sure the sum displayed as output is in the most reduced form.
If sum is an integer, you have to print 1 as denominator.
Sample Input
4
4 2
2 4
2 4
2 3
Sample Output
11 3

Explanation
Sum is 4/2 + 2/4 + 2/4 + 2/3 = (24 + 6 + 6 + 8)/12 = 44/12 = 11/3. So you have to print "11 3", which is the most reduced form.
  5  *  Immutable ADT for Rational numbers. 
  6  * 
  7  *  Invariants
  8  *  -----------
  9  *   - gcd(num, den) = 1, i.e, the rational number is in reduced form
 10  *   - den >= 1, the denominator is always a positive integer
 11  *   - 0/1 is the unique representation of 0
 12  *
 13  *  We employ some tricks to stave of overflow, but if you
 14  *  need arbitrary precision rationals, use BigRational.java.
 15  *
 16  *************************************************************************/
 17 
 18 public class Rational implements Comparable<Rational> {
 19     private static Rational zero = new Rational(0, 1);
 20 
 21     private int num;   // the numerator
 22     private int den;   // the denominator
 23 
 24     // create and initialize a new Rational object
 25     public Rational(int numerator, int denominator) {
 26 
 27         // deal with x/0
 28         //if (denominator == 0) {
 29         //   throw new RuntimeException("Denominator is zero");
 30         //}
 31 
 32         // reduce fraction
 33         int g = gcd(numerator, denominator);
 34         num = numerator   / g;
 35         den = denominator / g;
 36 
 37         // only needed for negative numbers
 38         if (den < 0) { den = -den; num = -num; }
 39     }
 40 
 41     // return the numerator and denominator of (this)
 42     public int numerator()   { return num; }
 43     public int denominator() { return den; }
 44 
 45     // return double precision representation of (this)
 46     public double toDouble() {
 47         return (double) num / den;
 48     }
 49 
 50     // return string representation of (this)
 51     public String toString() { 
 52         if (den == 1) return num + "";
 53         else          return num + "/" + den;
 54     }
 55 
 56     // return { -1, 0, +1 } if a < b, a = b, or a > b
 57     public int compareTo(Rational b) {
 58         Rational a = this;
 59         int lhs = a.num * b.den;
 60         int rhs = a.den * b.num;
 61         if (lhs < rhs) return -1;
 62         if (lhs > rhs) return +1;
 63         return 0;
 64     }
 65 
 66     // is this Rational object equal to y?
 67     public boolean equals(Object y) {
 68         if (y == null) return false;
 69         if (y.getClass() != this.getClass()) return false;
 70         Rational b = (Rational) y;
 71         return compareTo(b) == 0;
 72     }
 73 
 74     // hashCode consistent with equals() and compareTo()
 75     public int hashCode() {
 76         return this.toString().hashCode();
 77     }
 78 
 79 
 80     // create and return a new rational (r.num + s.num) / (r.den + s.den)
 81     public static Rational mediant(Rational r, Rational s) {
 82         return new Rational(r.num + s.num, r.den + s.den);
 83     }
 84 
 85     // return gcd(|m|, |n|)
 86     private static int gcd(int m, int n) {
 87         if (m < 0) m = -m;
 88         if (n < 0) n = -n;
 89         if (0 == n) return m;
 90         else return gcd(n, m % n);
 91     }
 92 
 93     // return lcm(|m|, |n|)
 94     private static int lcm(int m, int n) {
 95         if (m < 0) m = -m;
 96         if (n < 0) n = -n;
 97         return m * (n / gcd(m, n));    // parentheses important to avoid overflow
 98     }
 99 
100     // return a * b, staving off overflow as much as possible by cross-cancellation
101     public Rational times(Rational b) {
102         Rational a = this;
103 
104         // reduce p1/q2 and p2/q1, then multiply, where a = p1/q1 and b = p2/q2
105         Rational c = new Rational(a.num, b.den);
106         Rational d = new Rational(b.num, a.den);
107         return new Rational(c.num * d.num, c.den * d.den);
108     }
109 
110 
111     // return a + b, staving off overflow
112     public Rational plus(Rational b) {
113         Rational a = this;
114 
115         // special cases
116         if (a.compareTo(zero) == 0) return b;
117         if (b.compareTo(zero) == 0) return a;
118 
119         // Find gcd of numerators and denominators
120         int f = gcd(a.num, b.num);
121         int g = gcd(a.den, b.den);
122 
123         // add cross-product terms for numerator
124         Rational s = new Rational((a.num / f) * (b.den / g) + (b.num / f) * (a.den / g),
125                                   lcm(a.den, b.den));
126 
127         // multiply back in
128         s.num *= f;
129         return s;
130     }
131 
132     // return -a
133     public Rational negate() {
134         return new Rational(-num, den);
135     }
136 
137     // return a - b
138     public Rational minus(Rational b) {
139         Rational a = this;
140         return a.plus(b.negate());
141     }
142 
143 
144     public Rational reciprocal() { return new Rational(den, num);  }
145 
146     // return a / b
147     public Rational divides(Rational b) {
148         Rational a = this;
149         return a.times(b.reciprocal());
150     }
151 
152 
153     // test client
154     public static void main(String[] args) {
155         Rational x, y, z;
156 
157         // 1/2 + 1/3 = 5/6
158         x = new Rational(1, 2);
159         y = new Rational(1, 3);
160         z = x.plus(y);
161         System.out.println(z);
162 
163         // 8/9 + 1/9 = 1
164         x = new Rational(8, 9);
165         y = new Rational(1, 9);
166         z = x.plus(y);
167         System.out.println(z);
168 
169         // 1/200000000 + 1/300000000 = 1/120000000
170         x = new Rational(1, 200000000);
171         y = new Rational(1, 300000000);
172         z = x.plus(y);
173         System.out.println(z);
174 
175         // 1073741789/20 + 1073741789/30 = 1073741789/12
176         x = new Rational(1073741789, 20);
177         y = new Rational(1073741789, 30);
178         z = x.plus(y);
179         System.out.println(z);
180 
181         //  4/17 * 17/4 = 1
182         x = new Rational(4, 17);
183         y = new Rational(17, 4);
184         z = x.times(y);
185         System.out.println(z);
186 
187         // 3037141/3247033 * 3037547/3246599 = 841/961 
188         x = new Rational(3037141, 3247033);
189         y = new Rational(3037547, 3246599);
190         z = x.times(y);
191         System.out.println(z);
192 
193         // 1/6 - -4/-8 = -1/3
194         x = new Rational( 1,  6);
195         y = new Rational(-4, -8);
196         z = x.minus(y);
197         System.out.println(z);
198     }
199 
Read full article from Twitter OA prepare: Rational Sum - neverlandly - 博客园

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts