WHY this code is not giving correct binary #JULY LUNCHTIME BINFUN

help
,
1 
#include<vector>
#include<cmath>
#include <iostream>

using namespace std;

long long int diff(long long int a,long long int b)
{
    long long int fakea=a,fakeb=b;
    vector <long long int>num1,num2;
 
    while(a)
    {
        if(a&1)
        num1.insert(num1.begin(),1);
        else
        num1.insert(num1.begin(),0);
        
        a=a>>1;
    }
  
  
  
    while(b)
    {
        num1.insert(num1.begin(),b&1);
        b=b>>1;
    }
    
    while(fakeb)
    {
        num2.insert(num2.begin(),fakeb&1);
        fakeb=fakeb>>1;
    }
    
    while(fakea)
    {
        num2.insert(num2.begin(),fakea&1);
        fakea=fakea>>1;
    }
    
 
 /*************************************XXxxxxXXXXXXXXXXxxxxxxXXXXXX********************/   
    
    
    long long int ans=0;
    
    
    long long int x=0,y=0,k=1;
    
    
    for(int i=num1.size()-1;i>=0;i--)
     {
        x+=num1[i]*k;
        k*=2;
     }
    
    
    for(int i=num2.size()-1,k=1;i>=0;i--)
     {
         y+=num2[i]*k;
        k*=2;
     }
    
    ans=x-y;
   return ans;
    
    
  
  
}


int main()
{
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    
   int t;cin>>t;
   while(t--)
   {
       
    int n;cin>>n;
    
    long long int arr[n];
    
    for(int i=0;i<n;i++)
    cin>>arr[i];
    
    
    long long int max= 0;
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(max<diff(arr[i],arr[j]) )
            {
                max=diff(arr[i],arr[j]);
              
            }
        }
    }
    
   cout<<max<<endl;
    
  
    
   }

    return 0;
}

Link to the problem : BINFUN Problem - CodeChef

my code is not generating the binary for big numbers ie value of x is not correct.
solving only for partial points right now

2

Can you format your code as code

Use three backticks ``` before and three backticks after your code section. This will make sure that there is syntax highlighting and that the forum doesn’t apply it’s own formatting to your code

2 Likes
3

When looking at your submission page I see you have a submission that got partially accepted. It took a while to figure out why that one worked and this one doesn’t. To find the issue try compiling with -Wshadow. This will give a compiler warning when you re-declare a variable in an inner scope when it was already defined in a larger scope.
In this case:

binfun_sushant2001_2.cpp: In function ‘long long int diff(long long int, long long int)’:
binfun_sushant2001_2.cpp:31:29: warning: declaration of ‘k’ shadows a previous local [-Wshadow]
   31 |     for(int i=num2.size()-1,k=1;i>=0;i--) {
      |                             ^
binfun_sushant2001_2.cpp:26:27: note: shadowed declaration is here
   26 |     long long int x=0,y=0,k=1;
      |                           ^

This means that in the second for loop k is an int instead of an long long int.

As to the TLE on the second subproblem: A different approach is needed. However some general tips that might be useful for other problems

num1.insert(num1.begin(),a&1);

Insertion at the start of a vector is in general very slow. It has to shift over each element, thus taking \mathcal{O}(n). It could be more efficient to build up the reverse array and after all elements have been inserted reverse the array.

if (max < diff(arr[i],arr[j]) ) {
    max = diff(arr[i],arr[j]);
}

This will calculate diff(arr[i],arr[j]) twice. Better will be

maxValue = max(maxValue, diff(arr[i], arr[j]));

Note that I have changed the variable name not to shadow the max function from #include<algorithm>

1 Like
4

Thanx it worked :+1: :+1: :+1: