Divisible by 3

 

Problem

Stack likes the number $3$ a lot.

He has two non-negative integers $A$ and $B$.
In one operation, Stack can do either of the following:

• $A:=|A-B|$ (change $A$ to $|A-B|$)
• $B:=|A-B|$ (change $B$ to $|A-B|$)

Note that $|X|$ denotes absolute value of $X$. For example $|-7| = 7$ and $|4| = 4$.

Find the minimum number of operations after which at least one integer out of $A$ and $B$ becomes divisible by $3$.

Input Format

• The first line of input contains a single integer $T$, denoting the number of test cases. The description of $T$ test cases follows.
• The only line of each test case contains two integers $A$ and $B$.

Output Format

For each test case, output in a single line the minimum number of operations after which at least one integer out of $A$ and $B$ becomes divisible by $3$.

Constraints

• $1 \leq T \leq 10^5$
• $0 \leq A, B \leq 10^9$

Sample 1:

Input

Output

2
0 343
1 1

0
1

Explanation:

Test case $1$: $A=0$ is already divisible by $3$.

Test case $2$: In the only operation, Stack can change $A=1$ to $A = |A-B| = |1-1| = 0$. Now $A=0$ is divisible by $3$.

Elements in the Range

 Given an array arr[] containing positive elements. A and B are two numbers defining a range. The task is to check if the array contains all elements in the given range.

Example 1:

Input: N = 7, A = 2, B = 5
arr[] =  {1, 4, 5, 2, 7, 8, 3}
Output: Yes
Explanation: It has elements between 
range 2-5 i.e 2,3,4,5

Example 2:

Input: N = 7, A = 2, B = 6
arr[] = {1, 4, 5, 2, 7, 8, 3}
Output: No
Explanation: Array does not contain 6.

Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function check_elements() that takes array arr, integer N, integer A, and integer B  as parameters and returns the boolean True if array elements contain all elements in the given range else boolean False.

Note: If the array contains all elements in the given range then driver code outputs Yes otherwise, it outputs No

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ N ≤ 107

Code:

class Solution

{

public:

    bool check_elements(int arr[], int n, int A, int B)

    {

        // Your code goes here

        map<int, int> mp;

        for (int i = 0; i < n; i++)

        {

            mp[arr[i]]++;

        }

        for (int i = A; i <= B; i++)

        {

            if (mp[i] > 0)

            {

                continue;

            }

            else

            {

                return 0;

            }

        }

        return 1;

    }

};