# PROBLEM LINK:

Division 1

Division 2

Video Editorial

* Author:* Aryan Agarwala

*Данило Мочернюк*

**Tester:***Ritesh Gupta*

**Editorialist:**# DIFFICULTY:

CakeWalk

# PREREQUISITES:

NONE

# PROBLEM:

You are given two numbers A and B. You can perform several operations on it. In one operation:

- Update A = A - B
- Update B = B/2

If at any point of time A becomes non-positive before B then print **1** else **0**.

# QUICK EXPLANATION:

Since B becomes half in one operation, that implies in log B operations, it will become zero. Hence, we can optimally iterate over the value of B to find the answer.

# EXPLANATION:

We just need to implement the process. Iterate over the number of operations and at each operation, first, A is decreased by B and then B becomes half of the current value.

- A = A - B
- B = B/2

Keep on iterating until B is greater than or equal to the A. So, if after this A becomes zero then answer is **1** else answer is **0**.

# TIME COMPLEXITY:

**TIME:** O(Log N)

**SPACE:** O(1)

# SOLUTIONS:

## Setter's Solution

## Tester's Solution

```
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(a) ((int)(a.size()))
using namespace std;
const int mod = 1000 * 1000 * 1000 + 7;
int main()
{
int T;
cin >> T;
while(T--)
{
int p , h;
cin >> h >> p;
int ans = 0;
while(p != 0)
{
ans += p;
p >>= 1;
}
cout << (ans >= h) << endl;
}
}
```

## Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int a,b;
cin >> a >> b;
while(a > 0 && b > 0)
{
a -= b;
b /= 2;
}
cout << (a <= 0 ? 1 : 0) << endl;
}
}
```