I used the same approach as that of editorials and sample test cases are also passing. It would be a great help for me if anyone can debug my code please…
Problem link:DOR Problem - CodeChef
My solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll countBits( ll n)
{
ll count = 0;
while (n)
{
count++;
n >>= 1;
}
return count;
}
ll pow(ll a,ll b){
ll ans=1;
for(ll i=1;i<=b;i++){
ans*=a;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;cin>>t;
while(t–){
bool flag=false;
ll l,r;
cin>>l>>r;
if(l==r){
cout<<l<<“\n”;
continue;
}
ll a=countBits(l);
ll b=countBits(r);
if(a!=b){
cout<<(pow(2,b)-1)<<“\n”;
continue;
}
ll binaryNum1[64];
ll x1= 0;
while (l > 0) {
binaryNum1[x1] = l % 2;
l = l / 2;
x1++;
}
ll bin2[x1];
for (ll j = x1- 1; j >= 0; j--) {
bin2[x1-j-1]= binaryNum1[j];
}
ll binaryNum2[64];
ll x2= 0;
while (r > 0) {
binaryNum2[x2] = r % 2;
r = r / 2;
x2++;
}
ll bin1[x2];
for (ll j = x2 - 1; j >= 0; j--) {
bin1[x2-j-1]= binaryNum2[j];
}
ll sorry=pow(2,x1-1);
for(ll j=1;j<x1;j++){
if(bin1[j]==1 && bin2[j]==0){
ll ok=x1-j-1;
while(ok>=0){
sorry+=pow(2,ok);
ok--;
}
cout<<sorry<<"\n";
flag=true;
break;
}
else if(bin1[j]==1){
sorry+=pow(2,x1-j-1);
continue;
}
}
if(!flag)
cout<<sorry<<"\n";
}
return 0;
}
We need to type cast pow as long long int(pow)
include <bits/stdc++.h>
using namespace std;
long long int mask_off(long long int x){
int bit_no = log2(x);
long long int pow_no = (long long int)(pow(2,bit_no));
return x^pow_no;
}
long long int recurValue(long long int base_num, long long int l, long long int r){
l = mask_off(l);
r = mask_off(r);
int l_digits = log2(l);
int r_digits = log2(r);
if(l==r){
return base_num+l;
}
else if(l_digits<r_digits){
long long value = (long long int)(pow(2,r_digits))-1;
return base_num+(long long int)(pow(2,r_digits))+value;
}
else
return recurValue(base_num+(long long int)(pow(2,r_digits)), l,r);
}
int main(){
long long int t;
cin>>t;
while(t>0){
long long int l,r;
cin>>l>>r;
int l_digits = log2(l);
int r_digits = log2(r);
if(l==r){
cout<<l<<"\n";
}
else if(l_digits<r_digits){
long long int value =(long long int)pow(2,r_digits)-1;
cout<<value+(long long int)(pow(2,r_digits))<<"\n";
}
else
cout<<recurValue((long long int)(pow(2,l_digits)),l,r)<<"\n";
t--;
}
}
solution:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
int t; cin >> t;
while(t--){
long long int l,r; cin >> l >> r;
long long numl = l, numr = r;
long long int power = 1;
long long int num = 0;
while(r){
int a,b;
a = r&1;
b = l&1;
if(a|b == 1){
num += power;
}
else{
if(b == 0){
if(numl + power <= numr){
num += power;
}
}
}
power <<= 1;
r >>= 1;
l >>= 1;
}
cout << num << '\n';
}
return 0;
}
Thanks but why it needs to be typecasted? As I have not used inbuilt pow function. My function already returns long long int…
Can you post the code in correct format.
use <```> (without the angle brackets to wrap your code)
eg:
<```>
<code here>
<```>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll countBits( ll n)
{
ll count = 0;
while (n)
{
count++;
n >>= 1;
}
return count;
}
ll pow(ll a,ll b){
ll ans=1;
for(ll i=1;i<=b;i++){
ans*=a;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;cin>>t;
while(t--){
bool flag=false;
ll l,r;
cin>>l>>r;
if(l==r){
cout<<l<<"\n";
continue;
}
ll a=countBits(l);
ll b=countBits(r);
if(a!=b){
cout<<(pow(2,b)-1)<<"\n";
continue;
}
ll binaryNum1[64];
ll x1= 0;
while (l > 0) {
binaryNum1[x1] = l % 2;
l = l / 2;
x1++;
}
ll bin2[x1];
for (ll j = x1- 1; j >= 0; j--) {
bin2[x1-j-1]= binaryNum1[j];
}
ll binaryNum2[64];
ll x2= 0;
while (r > 0) {
binaryNum2[x2] = r % 2;
r = r / 2;
x2++;
}
ll bin1[x2];
for (ll j = x2 - 1; j >= 0; j--) {
bin1[x2-j-1]= binaryNum2[j];
}
ll sorry=pow(2,x1-1);
for(ll j=1;j<x1;j++){
if(bin1[j]==1 && bin2[j]==0){
ll ok=x1-j-1;
while(ok>=0){
sorry+=pow(2,ok);
ok--;
}
cout<<sorry<<"\n";
flag=true;
break;
}
else if(bin1[j]==1){
sorry+=pow(2,x1-j-1);
continue;
}
}
if(!flag)
cout<<sorry<<"\n";
}
return 0;
}
I changed your pow func name to myPow thats all.
I think pow was still calling the c++ inbuilt pow which has tobe typecasted as explained in above comment. Anyways your solution gets accepted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll countBits( ll n)
{
ll count = 0;
while (n)
{
count++;
n >>= 1;
}
return count;
}
ll myPow(ll a,ll b){
ll ans=1;
for(ll i=1;i<=b;i++){
ans*=a;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;cin>>t;
while(t--){
bool flag=false;
ll l,r;
cin>>l>>r;
if(l==r){
cout<<l<<"\n";
continue;
}
ll a=countBits(l);
ll b=countBits(r);
if(a!=b){
cout<<(myPow(2,b)-1)<<"\n";
continue;
}
ll binaryNum1[64];
ll x1= 0;
while (l > 0) {
binaryNum1[x1] = l % 2;
l = l / 2;
x1++;
}
ll bin2[x1];
for (ll j = x1- 1; j >= 0; j--) {
bin2[x1-j-1]= binaryNum1[j];
}
ll binaryNum2[64];
ll x2= 0;
while (r > 0) {
binaryNum2[x2] = r % 2;
r = r / 2;
x2++;
}
ll bin1[x2];
for (ll j = x2 - 1; j >= 0; j--) {
bin1[x2-j-1]= binaryNum2[j];
}
ll sorry=myPow(2,x1-1);
for(ll j=1;j<x1;j++){
if(bin1[j]==1 && bin2[j]==0){
ll ok=x1-j-1;
while(ok>=0){
sorry+=myPow(2,ok);
ok--;
}
cout<<sorry<<"\n";
flag=true;
break;
}
else if(bin1[j]==1){
sorry+=myPow(2,x1-j-1);
continue;
}
}
if(!flag)
cout<<sorry<<"\n";
}
return 0;
}