Algorithm
Problem link- https://www.spoj.com/problems/BITPLAY/
BITPLAY - PLAYING WITH BITS
The problem is very simple.
You are given a even number N and an integer K and you have to find the greatest odd number M less than N such that the sum of digits in binary representation of M is at most K.
Input
For each testcase, you are given an even number N and an integer K.
Output
For each test case, output the integer M if it exists, else print -1.
Constraints
1 <= T <= 10^4
2 <= N <= 10^9
0 <= K <= 30
Example
Input: 2 10 2 6 1 Output: 9 1
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
T = int(input())
for _ in range(T):
N, K = map(int, input().split())
if K == 0 or N == 1:
print(-1)
continue
result = 1
K -= 1
for i in range(30, -1, -1):
if K > 0 and result + (1 << i) < N:
K -= 1
result += (1 << i)
print(result)Input
2
10 2
6 1
10 2
6 1
Output
9
1
1
#2 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int k;
unsigned long n;
cin>>n>>k;
if(k==0)
{
printf("-1\n");
}
else
{
n=n-1;
bitset<32>b(n);
int c=b.count();
if(c<=k)
{
printf("%d\n",n);
}
else
{
string s=b.to_string();
// cout<<s;
int i=30;
while(c>k && i>=0)
{
if(s[i]=='1')
{
s[i]='0';
c--;
}
i--;
}
bitset<32> a(s);
cout<<a.to_ulong()<<endl;
}
}
}
return 0;
}Input
2
10 2
6 1
10 2
6 1
Output
9
1
1
Demonstration
SPOJ Solution-PLAYING WITH BITS-Solution in C, C++, Java, Python