java - 用有限的位数找到最大的奇数

Question

我试图解决这个问题，但自动判断返回“超出时间限制”(TLE)。

值此情人节之际，亚当和夏娃继续参加了一场比赛，他们通过了所有的关卡，进入了 final 。在最后一轮中，给 Adam 一个偶数 N 和一个整数 K，他必须找到小于 N 的最大奇数 M，使得 M 的二进制表示的数字之和至多为 K。

输入格式:

For each test case you are given an even number N and an integer K

输出格式:

For each test case, output the integer M if it exists, else print -1

约束:

• 1 ≤ T ≤ 10⁴

• 2≤N≤10⁹

• 0≤K≤30

示例输入:

2  
10 2  
6 1 

示例输出:

9 
1

这是我到目前为止所做的。

    static long play(long n, int k){
      if(k==0) return -1;
      if(k==1) return 1;
      long m=n-1;      
      while(m>0){                      
              long value=Long.bitCount(m); //built in function to count bits
              if(value<=k ){                  
                  return m;
              }
              m=m-2;          
      }     
        return -1;
    }

    public void solve(InputReader in, OutputWriter out) {
       long start=System.currentTimeMillis(); 
       int t=in.readInt();
       while(t-->0){                
          long n=in.readLong();         
          int k=in.readInt();
          long result=play(n,k);         
          out.printLine(result);
       }
       long end=System.currentTimeMillis();
       out.printLine((end-start)/1000d+"ms");       
    } 
 }       

Answer 1

根据更新的问题 N可以在 2 到 10^9 之间。您从 N-1 开始并向下循环 2，所以你得到大约 10^9 / 2循环的迭代。 不好。

以 M = N - 1 开头很好。并使用 bitCount(M)很好，开始。如果初始位数为 <= K你完成了。

但如果不是，不要以步骤 -2 循环.

将你脑海中的数字看成二进制，例如110101011 .位数是 6。假设 K 是 4，这意味着您必须删除 2 位。最右边的位必须保留，并且您想要最大的数字，因此清除倒数第二个 1 位。结果:110100001 .

现在，您知道如何编写它了。并且无需转换为文本即可执行此操作。

注意:用N <= 10^9 , 它将适合 int .不需要 long .