Google foobar challenge level 3 - Bomb, Baby!

Description

Bomb, Baby!

You’re so close to destroying the LAMBCHOP doomsday device you can taste it! But in order to do so, you need to deploy special self-replicating bombs designed for you by the brightest scientists on Bunny Planet. There are two types: Mach bombs (M) and Facula bombs (F). The bombs, once released into the LAMBCHOP’s inner workings, will automatically deploy to all the strategic points you’ve identified and destroy them at the same time.

But there’s a few catches. First, the bombs self-replicate via one of two distinct processes:
Every Mach bomb retrieves a sync unit from a Facula bomb; for every Mach bomb, a Facula bomb is created;
Every Facula bomb spontaneously creates a Mach bomb.

For example, if you had 3 Mach bombs and 2 Facula bombs, they could either produce 3 Mach bombs and 5 Facula bombs, or 5 Mach bombs and 2 Facula bombs. The replication process can be changed each cycle.

Second, you need to ensure that you have exactly the right number of Mach and Facula bombs to destroy the LAMBCHOP device. Too few, and the device might survive. Too many, and you might overload the mass capacitors and create a singularity at the heart of the space station - not good!

And finally, you were only able to smuggle one of each type of bomb - one Mach, one Facula - aboard the ship when you arrived, so that’s all you have to start with. (Thus it may be impossible to deploy the bombs to destroy the LAMBCHOP, but that’s not going to stop you from trying!)

You need to know how many replication cycles (generations) it will take to generate the correct amount of bombs to destroy the LAMBCHOP. Write a function solution(M, F) where M and F are the number of Mach and Facula bombs needed. Return the fewest number of generations (as a string) that need to pass before you’ll have the exact number of bombs necessary to destroy the LAMBCHOP, or the string “impossible” if this can’t be done! M and F will be string representations of positive integers no larger than 10^50. For example, if M = “2” and F = “1”, one generation would need to pass, so the solution would be “1”. However, if M = “2” and F = “4”, it would not be possible.

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(‘2’, ‘1’)
Output:
1

Input:
Solution.solution(‘4’, ‘7’)
Output:
4

— Python cases —
Input:
solution.solution(‘4’, ‘7’)
Output:
4

Input:
solution.solution(‘2’, ‘1’)
Output:
1

Idea

이 문제같은 경우에는 탑다운으로 내려가면서 손으로 직접 공식을 풀어나가다 보면 몇가지 규칙이 보인다.

• x, y중 큰 수 에서 작은수를 빼야 한다.
• 큰 수 에서 작은 수를 뺄 때 n회를 빼야 한다.
  • 큰 수에서 작은수를 빼나가야 하니까 다음과 같이 같은 작업이 반복된다.
  • (10, 2) -> (8, 2) -> (6, 2)

N을 구하는 식은 나눗셈 연산을 통해 몫과 나머지를 구하고 대체해주면 된다.
x / y의 나머지가 0이 되어 다음 결과가 (y, 0)이 되는 케이스에서 "impossible"을 반환하면 된다.

Code

public class Solution {
    private static final String IMPOSSIBLE = "impossible";
    public static String solution(String x, String y) {
        if(x == "1" && y == "1") return "0";
        if(x == y) return IMPOSSIBLE;
        BigInteger bx = new BigInteger(x), by = new BigInteger(y);
        BigInteger res = BigInteger.ZERO;
        if(bx.compareTo(by) < 0) {
            BigInteger temp = bx;
            bx = by;
            by = temp;
        }

        while(!by.equals(BigInteger.ONE)) {
            BigInteger[] result = bx.divideAndRemainder(by);
            if(result[1].equals(BigInteger.ZERO)) return IMPOSSIBLE;
            res = res.add(result[0]);
            bx = result[1];

            if(bx.compareTo(by) < 0) {
                BigInteger temp = bx;
                bx = by;
                by = temp;
            }
        }

        return res.add(bx.subtract(BigInteger.ONE)).toString();
    }
}