Divisible Numbers - Amazon Top Interview Questions

                        Solution in C++ :

class Solution {
    public:
    int lcm(int x, int y) {
        return x * y / __gcd(x, y);
    }

    int a, b, c;

    int lesser(int n) {
        // how many elements less than it?
        return n / a + n / b + n / c - n / lcm(a, b) - n / lcm(b, c) - n / lcm(a, c) +
               n / lcm(a, lcm(b, c));
    }

    int solve(int n, int a, int b, int c) {
        this->a = a, this->b = b, this->c = c;

        int l = 1, r = INT_MAX;

        while (l < r) {
            int guess = l + (r - l) / 2;

            // i want the first value with >=n elements lesser than it!
            if (lesser(guess) >= n) {
                r = guess;
            } else {
                l = guess + 1;
                // guess is not the answer! +1 it
            }
        }

        return l;
    }
};

int solve(int n, int a, int b, int c) {
    return (new Solution())->solve(n, a, b, c);
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int n, int a, int b, int c) {
        int x = 1, y = 1, z = 1;
        int ans = 1;

        while (n-- > 0) {
            int xx = a * x;
            int yy = b * y;
            int zz = c * z;

            ans = Math.min(xx, Math.min(yy, zz));

            if (ans == xx) {
                x++;
            }

            if (ans == yy) {
                y++;
            }

            if (ans == zz) {
                z++;
            }
        }

        return ans;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def find_points(self, goal, a, b, c, ab, ac, bc, abc):
        total = 0

        for item in (a, b, c, abc):
            total += goal // item

        for item in (ab, ac, bc):
            total -= goal // item

        return total

    def solve(self, n, a, b, c):

        if n == 0:
            return 1

        lcm_ab = a * b // gcd(a, b)
        lcm_ac = a * c // gcd(a, c)
        lcm_bc = b * c // gcd(b, c)
        lcm_abc = lcm_ab * c // gcd(lcm_ab, c)

        points = self.find_points(lcm_abc, a, b, c, lcm_ab, lcm_ac, lcm_bc, lcm_abc)
        total = n // points * lcm_abc

        if n % points == 0:
            return total

        goal = n % points

        approx = int(lcm_abc / points * goal)
        approx -= min(approx % a, approx % b, approx % c)
        calc = 0

        while calc != goal:
            calc = self.find_points(approx, a, b, c, lcm_ab, lcm_ac, lcm_bc, lcm_abc)

            if calc > goal:
                approx -= 1
                approx -= min(approx % a, approx % b, approx % c)
            if calc < goal:
                approx += min(a - approx % a, b - approx % b, c - approx % c)

        return total + approx