Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Problem 1900. GJam 2014 China Rd A: Rational Number Tree (Large Values)

Created by Richard Zapor

This Challenge is derived from GJam 2014 China Rational Number Tree.

The Goal is to determine the tree node if given [P,Q] or provide the [P,Q] if given a node. This is the Large Challenge with a Max of 64 Tree levels. Processing of uint64 size data requires extra care.

Consider an infinite complete binary tree where the root node is 1/1 and the left and right children of node P/Q are P/(P+Q) and (P+Q)/Q, respectively.

The Tree looks like:

    |           |
   1/2         2/1
 ___|___     ___|___
 |     |     |     |
1/3   3/2   2/3   3/1

The nodes are 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1,...

Input: [N] or [P,Q] where N is a uint64 integer node or [P,Q] (double) are terms of a Node

Output: [P,Q](double) or [N](uint64) depends on Input type


[Input]  [Output]
  [2] [1 2]
  [1 2] [2]
  [5] [3 2]
  [3 2] [5]

Contest Performance: Best Delta Time of 14 minutes with only 368 able to process the large data set in less than 3 hours.


1) Matlab has issues with uint64 for dec2bin and matrix multiplies.

2) Example of uint64 read is provided in test suite comments

3) Bitshift and bitget work on uint64


Problem Group

2 solvers submitted 8 solutions (4.0 solutions/solver).

Loading Solution Map...