# BITSY - Editorial

Contest

Author: Rahul Sharma

Tester: Sumukh Bhardwaj

Editorialist: Rahul Sharma

Easy

# PREREQUISITES:

Bits, Simple math

# PROBLEM:

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

1. First the bits from rightmost set bit till end are flipped
2. 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.
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;
}
``````
1 Like