Mirror Reflection Solutions in C++

// Source : https://leetcode.com/problems/mirror-reflection/description/
// Author : Hao Chen
// Date   : 2018-06-27



/*
 *  Solution 
 *  --------
 *  
 *  We know the following things:
 *  1）every reflection will increase the step of `q`.  
 *  2) when reach the top, the reflection would go down, when reach the bottom the reflection would go up.
 *  
 *  So, we can image if there have two walls, left one and right one, then the reflection can go up instanstly, 
 *
 *   - the reflection points on left wall would be even times of `q`.
 *   - the reflection points on right wall would be odd times of `q`.
 *
 *  And in the right wall, the receptors `#0` would be the times of `2p`.
 *
 *  So, we need find the least common multiple of `p` and `q`, then we can have the answer.    
 */


class Solution {
private:
    //GCD -  greatest common divisor  最大公因数
    int greatestCommonDivisor (int a, int b) {
        if(b) while((a %= b) && (b %= a));
        return a + b;
    }
    //LCM - least common multiple 最小公倍数
    int leastCommonMultiple(int a, int b) {
        return a * b / greatestCommonDivisor(a, b);
    }
public:
    int mirrorReflection(int p, int q) {
        int lcm = leastCommonMultiple(p, q);
        if (lcm % (2*p) == 0 ) return 0;
        
        int nq = lcm / q; 
        
        if (nq % 2 == 0 ) return 2;
        return 1;
    }
};

/// Source : https://leetcode.com/problems/mirror-reflection/description/
/// Author : liuyubobobo
/// Time   : 2018-06-25

#include <iostream>
#include <cassert>

using namespace std;

/// Simulation
/// Time Complexity: O(p)
/// Space Complexity: O(1)
class Solution {
public:
    int mirrorReflection(int p, int q) {

        int d = 1;
        bool left = true;
        int y = 0;
        while(true){

            y += d * q;
            left = !left;
            if(y == p && left)
                return 2;
            else if(y == p && !left)
                return 1;
            else if(y == 0)
                return 0;

            if(y > p){
                assert(d == 1);
                y = p - (y - p);
                d = -1;
            }
            else if(y < 0){
                assert(d == -1);
                y = -y;
                d = 1;
            }
        }

        assert(false);
        return -1;
    }
};


int main() {

    cout << Solution().mirrorReflection(2, 1) << endl; // 2
    cout << Solution().mirrorReflection(4, 3) << endl; // 2
    cout << Solution().mirrorReflection(3, 2) << endl; // 0
    cout << Solution().mirrorReflection(3, 1) << endl; // 1

    return 0;
}

/// Source : https://leetcode.com/problems/mirror-reflection/description/
/// Author : liuyubobobo
/// Time   : 2018-06-23

#include <iostream>
#include <cassert>

using namespace std;

/// Mathematics
/// Time Complexity: O(log(max(p, q)))
/// Space Complexity: O(1)
class Solution {
public:
    int mirrorReflection(int p, int q) {

        int g = gcd(p, q);
        int k = p / g;

        int x = p * k;
        int y = q * k;
        assert(y % p == 0);

        if(isEven(y / p))
            return 0;

        if(isEven(x / p))
            return 2;
        return 1;
    }

private:
    bool isEven(int x){
        return x % 2 == 0;
    }

    int gcd(int a, int b){
        if(a > b)
            swap(a, b);

        if(b % a == 0)
            return a;
        return gcd(b % a, a);
    }
};


int main() {

    cout << Solution().mirrorReflection(2, 1) << endl; // 2
    cout << Solution().mirrorReflection(4, 3) << endl; // 2
    cout << Solution().mirrorReflection(3, 2) << endl; // 0
    cout << Solution().mirrorReflection(3, 1) << endl; // 1

    return 0;
}