P Binary:
My solution:
I was giving a virtual contest for this. The question before this one took 1 hour (ughh), and thus I couldn't solve this in time. So I solved this later.
So you're given a number n, which we need to check how many p-binary numbers are needed to make this n number.
What are you gonna do?
So basically let's say we have n which we describe using m p-binary numbers. That will look like:
n = (2^{x_1}+p)+(2^{x_2}+p)+...+(2^{x_m}+p)
That can be made to look like:
n = (\sum_{i=1}^{m} 2^{x_i})+m*p
That is equal to:
n - m*p = (\sum_{i=1}^{m} 2^{x_i})
We do not know the value of m here. So,we can create an array with:
n-i*p where i goes from {1,...,100}, because you don't need more than that.
Now, check the number of set bits for each number in the array, starting from the left. Once you reach a point, where \text{number of set bits} <= i, you stop. As you can create i such elements in the expansion given above, from a lesser number of bits. Just remember that you can create 2 elements from one set bit if the number is not 1.
For example if you have a 2 (10), you can have two 1s (01). Similarly, you can see that you can the same for 4,8, et cetera. But you can't divide 1. So remember to check that n-i*p>=i, which means that the number can create i elements.
The logic here is that a number j can, at max, be divided into j elements.
It's a good question.
Here's the code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
using namespace std ; | |
#define f(i,s,n) for(int i=s;i<n;i++) | |
typedef long long ll ; | |
int bits(ll n) | |
{ | |
int count = 0 ; | |
while(n) n=n&(n-1),count++ ; | |
return count ; | |
} | |
int main() | |
{ | |
ll n ; | |
ll p ; | |
cin>>n>>p ; | |
ll arr[30] ; | |
arr[0] = p ; | |
f(i,1,30) arr[i] = arr[i-1]+p ; | |
f(i,0,30) arr[i] = n-arr[i] ; | |
int minn = 33 ; | |
f(i,0,30) | |
{ | |
int b = bits(arr[i]) ; | |
if(arr[i]>=i+1 && b!=0 && bits(arr[i])<=i+1) | |
{ | |
cout<<i+1<<endl ; | |
return 0; | |
} | |
} | |
cout<<"-1"<<endl ; | |
//cout<<minn<<endl ; | |
} |