Codechef long challenge

Question

Q-You are given an integer N. Consider the sequence containing the integers 1,2,…,N in increasing order (each exactly once). Find the length of the longest subarray in this sequence such that the bitwise AND of all elements in the subarray is positive.

i tried the following code to solve the problem but it is not working can anyone tell why or give a test case where it fails

#include <bits/stdc++.h>
using namespace std;

int main()
{
   int t,n,i,c;

   cin>>t;

   while (t--)
   {
       i = 1;
       cin>>n;

       while(i)
       {
           if(pow(2,i)<n)
           {
               i++;
           }
           else if (pow(2,i)==n)
           {
               break;
           }
           else
           {
               i--;
               break;
           }
       }
      
       if(n-pow(2,i)+1>pow(2,i)-pow(2,i-1))
       {          
           cout<<n-pow(2,i)+1<<endl;
       }
       else{
           cout<<pow(2,i)/2<<endl;
       }
   }
}

Obligatory: [Why should I not #include ?](https://stackoverflow.com/q/31816095/10077) — Fred Larson, Oct 04 '21 at 17:43
All those `pow(2,i)` are unlikely to be a good idea. Could you explain what your algorithm is supposed to do? — Bob__, Oct 04 '21 at 17:49
Edit the question to provide a [mre]. That includes example input that reproduces the problem, the observed output, and the output desired instead. Also, stop using `pow` to generate powers of two. Some `pow` implementations are badly implemented and return inexact results for powers of integers. Use shifts for powers of two. — Eric Postpischil, Oct 04 '21 at 17:49
@Bob__: The algorithm finds the largest power of two, 2^i, such that 2^i ≤ n. Then there are two candidate subsequences: All the numbers from 2^i to n, inclusive (whose AND is non-zero because they share bit i) and all the numbers from 2^(i−1) to 2^i−1, inclusive (whose AND is non-zero because they share bit i-1). Any earlier subsequences are shorter because no subsequence can cross a power of two (because 2^p−1 AND 2^p is zero). Whichever of those has the larger length, n+1−2^i or 2^(i−1), is output. That should work, so an inaccurate `pow` implementation is a likely culprit. — Eric Postpischil, Oct 04 '21 at 17:58
@EricPostpischil Got it, but I'd aim to a slightly different [target](https://godbolt.org/z/ec3aszKPY), though. — Bob__, Oct 04 '21 at 18:12
I recommend calculating `(1 << i)` (a.k.a. `pow(2,i)` once and placing into a temporary variable. Some compilers may place this into a register and only calculate once (depending on the optimization level). — Thomas Matthews, Oct 04 '21 at 19:02

Bob__ · Answer 1 · 2021-10-04T19:24:03.743

Online judges like Codechef usually require the output to be exactly as expected, to validate a solution.

cout << n-pow(2,i)+1 << endl;
//        ^^^^^^^^ This returns a double.

In the previous line and the likes, the expression is evaluated as a double and printed with the standard format, so that a big enough value like e.g. 463129089 is printed in exponential format as 4.63129e+08. That is unlikely the expected result.

You shouldn't have used pow in the first place. To calculate a simple¹ power of 2 you can just use bit shifting: 1u << i is equal to 2ⁱ.

If C++20 is an option, you could write the following:

#include <iostream>
#include <algorithm>  // std::max
#include <bit>        // std::bit_floor

int main()
{
    int t;
    std::cin >> t;

    while ( t-- )
    {
        int n;
        std::cin >> n;

        auto floor = std::bit_floor(static_cast<unsigned>(n));
        std::cout << std::max(n - floor + 1, floor / 2) << '\n'; 
    }
}

(1) The constraints of the problem don't require a type bigger than 32-bit int, so there's no reason to switch to a floating-point type which could also introduce unwanted rounding errors.

Codechef long challenge

1 Answers1