java - Find the greatest odd number with a limited number of bits -

i trying solve question automated judge returning "time limit exceeded" (tle).

on occasion of valentine day , adam , eve went on take part in competition.they cleared rounds , got finals. in final round, adam given number n , integer k , has find greatest odd number m less n such sum of digits in binary representation of m atmost k.

input format:

for each test case given number n , integer k

output format:

for each test case, output integer m if exists, else print -1

constraints:

• 1 ≤ t ≤ 10⁴

• 2 ≤ n ≤ 10⁹

• 0 ≤ k ≤ 30

sample input:

2   10 2   6 1  

sample output:

9  1 

this have done far.

    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 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");            }   }        

according updated question n can between 2 , 10^9. you're starting n-1 , looping down 2, 10^9 / 2 iterations of loop. not good.

starting m = n - 1 good. , using bitcount(m) good, to started. if initial bitcount <= k you're done.

but if it's not, do not loop step -2.

see number in mind binary, e.g. 110101011. bit count 6. let's k 4, means have remove 2 bits. right-most bit must stay on, , want largest number, clear 2 second-last 1-bits. result: 110100001.

now, figure out how write that. , without converting text.

note: n <= 10^9, fit in int. no need long.