# PROBLEM LINK:

* Author:* Rahul Sharma

* Tester:* Sumukh Bhardwaj

* Editorialist:* Rahul Sharma

# DIFFICULTY:

Easy

# PREREQUISITES:

Bits, Simple math

# PROBLEM:

Given a positive integer number N and non-negative integer K. Following conversion is done on N

- First the bits from rightmost set bit till end are flipped
- Then K is subtracted from the above new number.

Tell the smallest non-negative number that will be left if above conversion is applied repeatedly and also the number of conversions.

# QUICK EXPLANATION:

This two step conversion is eventually subtracting K+1. Least positive integer will be N \mod (K+1) and number of conversions will be N/(K+1).

# EXPLANATION:

If you observe carefully the first step i.e. flipping the bits from right most set bit is actually subtracting 1 from the N because after subtracting 1, bits from right most set bit till end gets flipped.

Thus in each conversion we are subtracting K+1 from current N.

Hence answer will be

Least positive integer: N \mod (K+1)

Number of conversions: N/(K+1)

# COMPLEXITIES:

**Time Complexity:** O(1) for each test case

**Space Complexity:** O(1) for each test case

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int n, k;
cin >> n >> k;
long long int smallestResult = n % (k+1);
long long int steps = n / (k+1);
cout << smallestResult << ' ' << steps;
}
```