In this Problem there is one point to observe. I will explain that with the help of example.
Assume there are tw numbers a and b. we are given a=5 and OR(a ,b) =9.
5=0101
OR(a,b) = 9 =1101
Here b’s binary form will be mnop. Here o can not be 1 as in OR(a,b) these bits are equal to zero.
And ‘m’ has to be 1 since in OR(a,b) this bit is 1 but in ‘a’ this bit is 0.
So there is only one case left when in OR(a,b) and a, bit is 1. This case represents n and p in above example. Here n and p can be zero or one. So by Multiplication Rule of Probability there are total 4 possibilities of b.
If we need to find the number of possible values of b then we have to find the number of set bits which are at same position in a and OR(a,b).
This can be done by counting set bits in (a & OR(a,b)).
At last you need to check if given array is sorted or not. If array is sorted then There is no possibility of sequence.
Here you need to check one more condition that b[i]&b[i+1])!=b[i].
My code is here
-
#include < iostream>
-
#include < algorithm>
-
#include < string>
-
#include < cmath>
-
#include < cstdlib>
-
#include < set>
-
#include < vector>
-
#include < sstream>
-
#include < queue>
-
#include < iomanip>
-
-
constexpr auto INF = 9223372036854775807;
-
typedef long long int ll;
-
typedef unsigned long long int ull;
-
typedef unsigned long int ul;
-
-
using namespace std;
-
vector a;
-
int main()
-
{
-
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
-
ull test;
-
cin >> test;
-
for (ull i = 0; i < test; i += 1)
-
{
-
ull n = 0;
-
cin >> n;
-
ull ans = 1;
-
vector<ull> arr(n, 0);
-
for (ull j = 0; j < n; j += 1)
-
{
-
cin >> arr[j];
-
if ((j>0)&&arr[j]>=arr[j-1])
-
{
-
// Count set bit in arr[j]&arr[j-1]
-
ull ad = arr[j] & arr[j - 1];
-
ull count = 0;
-
while (ad)
-
{
-
count += ad & 1;
-
ad >>= 1;
-
}
-
ans *= (ull)(pow(2, count));
-
ans %= 1000000007;
-
}
-
if ((j > 0)&&(arr[j] <arr[j-1]) )
-
{
-
ans = 0;
-
}
-
if ((j>0) && ((arr[j] & arr[j - 1]) != arr[j - 1]))
-
{
-
ans = 0;
-
> }
-
}
-
cout << ans << "\n";
-
}
-
return 0;
-
}
I think there might be a mistake.
Say, what’s the answer for this test case?
1
2
7 8
1 Like
hi @udit5656 firstly thanks for sharing your approach
but i think for solution to exist
one condition is mission from your solution
//check that b[i] is subset of b[i+1]
for(int i=0; i+1<n; ++i) {
if((b[i]&b[i+1])!=b[i]) {
cout << “0\n”;
return;
}
}
// CodeChef: Practical coding for everyone tmwilliamlin
@everule1
1 Like
Just Look at My Solution.It simple and Fast
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl “\n”
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
ll t = 1;
cin >> t;
while (t--)
{
ll n;
cin>>n;
vector<ll> v(n);
for(auto &x:v)cin>>x;
ll ans=1;
ll mod=1000000007;
for(int i=1;i<n;i++){
ll pro=1;
bool ok=0;
for(int j=0;j<32;j++){
if((v[i]&(1<<j)) && (v[i-1]&(1<<j))){
pro*=2;
}
if(!(v[i]&(1<<j)) && (v[i-1]&(1<<j)))ok=1;
}
if(ok)ans=0;
ans=(ans*pro)%mod;
}
cout<<ans<<endl;
}
return 0;
}
You seriously need to format your code !
Can you give an example of a possible sequence A?
Which is equivalent to finding x such that
7|x =8 where | denotes bitwise or.
It’s not. The question very clearly states
Note that it is not guaranteed that the given sequence B was generated from some sequence A.
Okay I was again wrong. That’s why my answers were wrong in both questions. Here is my solution CodeChef: Practical coding for everyone. You just need to check two conditions then to make a valid sequence.
If a[i]&a[i-1]== a[i-1] then a[i-1] is lesser than equal to a[i]. Therefore you don’t need to check both conditions.
1 Like
Sorry, Actually when I was writing this post ,codechef website was not opening that’s why I was not able to give link to my formated code link in post.
I have mentioned at last that given array should be sorted. If given array is not sorted then answer will be zero.
Try
1
2
7 8
The array is sorted, but the answer is nonetheless 0.
Here x has only one value i.e. 8
Sorry you are right ,here answer will be 0. Thanks for pointing it out.
What is the bitwise or of 7 and 8?
7 is 0111 and 8 is 1000
Thanks @ketan_mehta . Due to missing of this condition my code was giving wrong answer on array{7,8} which was pointed out by @everule1.
1 Like
Can someone help me finding an error in this?
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
inline int mul(int x, int y){
return (x * 1ll* y)%mod;
}
inline int bitcount( int a){
int count =0;
while(a){
if(a&1) count++;
a>>=1;
}
return count;
}
inline int binpow(int x, int y){
int z=1;
while(y){
if(y&1) z=mul(z,x);
x=mul(x,x);
y>>=1;
}
return z;
}
int main(){
int t; cin>>t;
for(int i=0; i<t; i++){
int n; cin>>n;
int a; int b;
cin>>a;
int ansbit=0;
bool check=1;
for (int i=1; i<n; i++){
cin>>b;
if(check){
if((a&b)!=a) {
check=0;
break;
}
ansbit+=bitcount(a);
a=b;
}
}
if(check)
cout<<binpow(2,ansbit)<<endl;
else cout<<0<<endl;
}
}
Write cin.ignore(); before the break. If you break early, you haven’t inputted some values which you’ll input in the next test case erraneously.
cin.ignore(); takes the reader to the next line.
Also instead of bitcount(a) you can use __builtin_popcount(a) which is up to 14% faster than your implementation.
I think you counting extra bits. You should count bits of ( a & b) . But you are counting bit of a.