# Divisible Numbers - Amazon Top Interview Questions

### Problem Statement :

```You are given integers n, a, b, and c. Return the nth (0-indexed) term of the sorted sequence of integers divisible by a, b or c.

Note that by convention the first term of any sequence always starts with 1.

Example 1

Input

n = 8
a = 2
b = 5
c = 7

Output

12

Explanation

The first 9 terms of the sequence are [1, 2, 4, 5, 6, 7, 8, 10, 12]```

### Solution :

```                        ```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

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:

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)

```

## Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element