TopCoder problem "FractionSplit" used in SRM 234 (Division I Level One , Division II Level Two)



Problem Statement

    Unit fractions are defined by having 1 in the numerator position. Any positive fraction of the form n/d can be rewritten as a finite sum of distinct unit fractions. When n<d, such a sum can be found by repeatedly subtracting the largest possible unit fraction until you reach 0.



For example, if you begin with 4/5 then the largest unit fraction you can subtract is 1/2. You are then left with 3/10. The largest unit fraction you can subtract from 3/10 is 1/4. You are then left with 1/20. The largest unit fraction you can subtract is 1/20 leaving you with 0. You should return a String[] giving the sequence of fractions you subtract, in the order you subtract them. Each should be given in the form "1/q" where q is a positive integer with no leading zeros. In the example just given, you would return 
 {"1/2","1/4","1/20"}
 

Definition

    
Class:FractionSplit
Method:getSum
Parameters:int, int
Returns:String[]
Method signature:String[] getSum(int n, int d)
(be sure your method is public)
    
 

Constraints

-d will be between 2 and 16 inclusive.
-n will be between 1 and d-1 inclusive.
 

Examples

0)
    
4
5
Returns: {"1/2", "1/4", "1/20" }
The example above.
1)
    
2
3
Returns: {"1/2", "1/6" }
1/2 is the largest unit fraction that can be subtracted from 2/3. The unit fraction 1/6 remains after the subtraction.
2)
    
1
2
Returns: {"1/2" }
1/2 is the largest unit fraction you can subtract.
3)
    
15
16
Returns: {"1/2", "1/3", "1/10", "1/240" }
4)
    
14
15
Returns: {"1/2", "1/3", "1/10" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3055

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6533&pm=3055

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom

Problem categories:

Simple Math, Simulation