BITSY - Editorial

editorial
,
1

PROBLEM LINK:

Contest

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

  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.
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;
}
1 Like