LeetCode 2020-11-17: Mirror Reflection

Mirror Reflection (medium) の挑戦メモ。

問題の概要

• 四方が鏡に囲まれた部屋の、西南の角からレーザー光が放たれる
  • 壁の幅は p、レーザー光が最初の鏡にたどり着いたときの南の鏡の壁からの距離は q で表される
• そのレーザー光が鏡で反射されながら行き着いた先が、他の３つの角のどこにたどり着くかを求める

考え方

• これは愚直に光の反射をシミュレートすることでも解けそうではあるが、時間効率が悪そう 😨
• 数学的に解けそうな気がするんだけどどうかしら？ 🤔
  • お絵かきしてみたらなんとなく思いついたのだが、これは p と　q の最小公倍数を求める問題に相当するのではなかろうか？
  • p と　q の最小公倍数を lcm とすると、レーザー光が左右の壁を反射する回数は lcm / q で求められるはず
  • 同様に縦方向に反射する回数は lcm / p になる
  • 左右方向の反射回数が偶数回の場合は北西の角 (2) が答えになる
  • 縦方向の反射回数が偶数回の場合は南東の角 (0) になる
  • どちらも奇数回の場合は北東の角 (1) になる
• では、最小公倍数を求めるにはどうしたらいいか？
  • 最大公約数を用いる方法 があるようだ
  • 最大公約数は ユークリッドの互除法 を使えば求められるね 👍
• 実装 → submit → 一回 wrong answer 💦 → accept 🤗
  • Runtime 0ms 達成 🎉

コード

class Solution {
    public int mirrorReflection(int p, int q) {
        if (q == 0) {
            return 0;
        }
        if (p == q) {
            return 1;
        }

        int gcd = gcd(p, q);
        int lcm = p * q / gcd;
        if (((lcm / p) & 1) == 0) {
            return 0;
        }
        if (((lcm / q) & 1) == 0) {
            return 2;
        }

        return 1;
    }

    int gcd(int a, int b) {
        while (b > 0) {
            int t = a;
            a = b;
            b = t % b;
        }
        return a;
    }
}