hackerrank终止到期超时

Question

我的代码位于C++ 当前正试图完成任务。媒体

我的算法工作正常，18出20个测试用例：下面

难度链接给出。 其他2个终止到期超时。

我知道这意味着什么，但现在我没有想法提高我的算法的效率。

我已经给了我下面的代码，任何人都可以请帮助我解决这个 https://www.hackerrank.com/challenges/and-product

#include <cmath> 
    #include <cstdio> 
    #include <vector> 
    #include <iostream> 
    #include <algorithm> 
    using namespace std; 

    int main() 
    { 
     int t; 
     unsigned long int x,y,a; 
     cin>>t; 
     while(t) 
     {  
      cin>>x>>y; 
      a=x; 
       for(;x<=y;x++) 
       a=a&(x); 

      cout<<a<<"\n"; 
      t--; 
     } 

    return 0; 
    } 

Answer 1

” ......总有一个众所周知的解决方案，每个人的问题 - 整齐， 。合理的，和错误的” - 孟肯

在计算机科学中，我们可以另一种方式：

“对于每一个计算问题存在一个解决方案，简单，优雅和错误的。”像hackerrank网站

问题，在面试时，牵线搭桥，在一场比赛中的行动者，画在3D宇宙飞船舰队实际上，在涉及筛选数据的任何生产系统中，决不会考虑是否有解决方案。

真正的问题始终是这样的：

“找到一个方法来减少为了这个看似简单的任务的复杂性的。”

从a计数到b而安定的值加在一起是线性时间算法 - O（B-A）。当a和b接近时这很好。但是这个问题告诉你他们被允许有一个高达2^32-1的间隔，大约是40亿次测试。

碰巧，这个问题可以归结为O（log2（b-a）），因为我们知道b比a大。

请看下面二进制表示的最高位：

a 01001 (9) 
b 11001 (25) 

有一些共同的比特，从而直观地想象我们这些位是在回答剩下1秒的候选人。

但是，b有点是一个值，它比a的最高位大一个数量级。

为了从a到b进行计数，低于这个最高位的每一位都必须存在于1和0的每个置换中 - 因为这是二进制表示的工作方式。

如果我们在每个置换中置换一个二进制位字段，那么最终该字段中的每个位都将在某个点包含一个0.这意味着将位字段的每个置换“与”在一起的结果为零。

所以现在我们发现在B 1位，是不是在一，我们可以简单地从屏蔽掉幅度较低的所有位。

现在的问题就变成了：

查找B中不存在一个从一个屏蔽掉所有低阶位的最高位。返回结果。

我们刚刚减少了搜索空间从0 <Ñ< 2^32），以0 <Ñ< = 32。换言之，复杂度可以由O（N）减小到O（LOG2（ N））。

这里有一个naiive的解决方案 - 它甚至不打扰优化位掩码的计算 - 这传递hackerrank所有测试。

#define TESTING 0 

#include <iostream> 
#include <string> 
#if TESTING 
    #include <sstream> 
#endif 
#include <cstdint> 

using namespace std::literals; 

#if TESTING 

const char test_data[] = 
R"__(
3 
12 15 
2 3 
8 13 
)__"; 
#endif 

bool has_bit(const std::uint32_t x, int bitnum) 
{ 
    return (x & (1 << bitnum)) != 0; 
} 

constexpr std::uint32_t mask_here_down(int bitnum) 
{ 
    std::uint32_t result = 0; 
    while (bitnum--) 
    { 
     result |= std::uint32_t(1) << bitnum; 
    } 
    return result; 
} 

void algo(std::istream& in, std::ostream& out) 
{ 
    std::uint32_t a,b; 
    in >> a >> b; 

    for (int bit = 32 ; bit-- ;) 
    { 
     if (has_bit(b, bit) and not has_bit(a, bit)) 
     { 
      std::cout << (a & ~mask_here_down(bit)) << std::endl; 
      break; 
     } 
    } 
} 

void run_tests(std::istream& in, std::ostream& out) 
{ 
    int n; 
    in >> n; 

    while (n--) 
    { 
     algo(in, out); 
    } 
} 

int main() 
{ 
    #if TESTING 
    auto in = std::istringstream(test_data); 
    #else 
    auto& in = std::cin; 
    #endif 

    run_tests(in, std::cout); 
}