Google foobar challenge level 2 - Gearing Up for Destruction

Description

Gearing Up for Destruction

As Commander Lambda’s personal assistant, you’ve been assigned the task of configuring the LAMBCHOP doomsday device’s axial orientation gears. It should be pretty simple — just add gears to create the appropriate rotation ratio. But the problem is, due to the layout of the LAMBCHOP and the complicated system of beams and pipes supporting it, the pegs that will support the gears are fixed in place.

The LAMBCHOP’s engineers have given you lists identifying the placement of groups of pegs along various support beams. You need to place a gear on each peg (otherwise the gears will collide with unoccupied pegs). The engineers have plenty of gears in all different sizes stocked up, so you can choose gears of any size, from a radius of 1 on up. Your goal is to build a system where the last gear rotates at twice the rate (in revolutions per minute, or rpm) of the first gear, no matter the direction. Each gear (except the last) touches and turns the gear on the next peg to the right.

Given a list of distinct positive integers named pegs representing the location of each peg along the support beam, write a function solution(pegs) which, if there is a solution, returns a list of two positive integers a and b representing the numerator and denominator of the first gear’s radius in its simplest form in order to achieve the goal above, such that radius = a/b. The ratio a/b should be greater than or equal to 1. Not all support configurations will necessarily be capable of creating the proper rotation ratio, so if the task is impossible, the function solution(pegs) should return the list [-1, -1].

For example, if the pegs are placed at [4, 30, 50], then the first gear could have a radius of 12, the second gear could have a radius of 14, and the last one a radius of 6. Thus, the last gear would rotate twice as fast as the first one. In this case, pegs would be [4, 30, 50] and solution(pegs) should return [12, 1].

The list pegs will be given sorted in ascending order and will contain at least 2 and no more than 20 distinct positive integers, all between 1 and 10000 inclusive.

Languages

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases

Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

— Java cases —
Input:
Solution.solution({4, 17, 50})
Output:
-1,-1

Input:
Solution.solution({4, 30, 50})
Output:
12,1

— Python cases —
Input:
solution.solution([4, 30, 50])
Output:
12,1

Input:
solution.solution([4, 17, 50])
Output:
-1,-1

Idea

In problem we know

• each gear’s radius must be greater than or equal to 1
• raidus[0] is equals to radius[n] * 2
• can we use same raidus of each gear? (not sure but pretty yes)

So let’s find out how to get gear radius.

We know sum of two cosecutive gears as peg[i] - peg[i - 1].
peg[i] - peg[i - 1] means distance of peg[i - 1] to peg[i] and it also same as radius[i - 1] + radius[i]

Now we know distance peg[0] to peg[2] is radius[0] + radius[1] + radius[1] + radius[2]
It can say radius[0] + 2 * radius[1] + radius[2] and so on..

So back to problem we can mutate total distance from peg[0] to peg[n] as radius like
radius[0] + 2 * radius[1] + 2 * radius[2] ... + 2 * radius[n - 1] + radius[n]

And also we know radius[0] is equals to raidus[n] 2 so we can change the formula as `2 radius[1] + 2 radius[2] … 3 radius[n]also we can change to2 * (radius[1] + radius[2] … radius[n]) + radius[n]is equals topeg[n] - peg[0]`

Now we can find in two ways.
If number of pegs are odd, we can use formula 2 * (r[0] + r[1] ... r[n]) + r[n] = peg[n] - peg[0]
we can change r[0] + r[1] ... r[n] as peg[1] - peg[0] + peg[3] - peg[2] and so on.

If number of pegs are even, we can use formula 2 * (r[0] + r[1] ... r[n-1]) + 3 * r[n] = peg[n] - peg[0]
we can also change r[0] + r[1] .. r[n-1] as peg[1] - peg[0] + peg[3] - peg[2] ...

Now we can find r[n] as in two cases

• Odd : r[n] = (peg[n] - peg[0]) / 2 * (peg[1] - peg[0] + peg[3] - peg[2] ...)
• Even : 3 * r[n] = (peg[n] - peg[0]) / 2 * (peg[1] - peg[0] + peg[3] - peg[2] ...)

After we find r[n] we need to check every gear’s radius is valid for condition r[i] >= 1

Caution
If numerator can divide with denominator (in case 3 only) we should divide numerator.

• Time Complexity : O(n)
• Space Complexity : O(1)

Code

public class Solution {
    private static final int[] FALSE = new int[]{-1, -1};

    public static int[] solution(int[] pegs) {
        int sum = 0, totalDistance = pegs[pegs.length-1] - pegs[0];

        for(int i = 2; i < pegs.length; i+=2) {
            sum += pegs[i] - pegs[i - 1];
        }

        sum *= 2;

        int rn = totalDistance - sum;

        int numerator = rn * 2;
        int denominator = (pegs.length & 1) == 1 ? 1 : 3;

        return numerator < denominator ? FALSE : verify(pegs,new int[]{numerator, denominator});
    }

    private static int[] verify(int[] pegs, int[] ret) {
        int numerator = ret[0];

        for(int i = 0; i < pegs.length - 1; i++) {
            int distance = (pegs[i + 1] - pegs[i]) * ret[1];
            int nextNumerator = distance - numerator;

            if(numerator < ret[1]) {
                return FALSE;
            }

            numerator = nextNumerator;
        }

        return ret[0] % ret[1] == 0 ? new int[]{ret[0]/ret[1], 1} : ret;
    }
}