java - Programming Algorithmic Thinking Improvement for Competitions -

i new community , have got lot of -1 votes trying best improve way can ask question.

recently tried problem @ codechef. problem definition.

this easiest task of problem set. understand task let define 2 key functions: f(n,k), (with k <= n) gives number of ways can draw sample of k objects set of n-distinct objects order of drawing not important , not allow repetition. g(x1, x2, x3, ... , xn) largest integer divides of {x1, x2, x3, ... , xn}. given integer n, task compute value of y y = g( f(2*n,1), f(2*n,3), f(2*n,5), ... , f(2*n,2*n-1)).

input

the first line of input contains integer t denoting number of test cases. description of t test cases follows. first , line of each test case contains single integer denoting given n described in problem statement.

output

for each test case, output single line containing value of y. constraints

1 ≤ t ≤ 10000 2 ≤ n ≤ 10¹¹

example

input:

3

6

5

4

output:

4

2

8

now wrote code in java works fine codechef online judge give tle error, tried couple of different ways no success. checked solution others had posted , didnt have clue algorithm did magically came right answer concern books should refer improve way these algorithms written . p.s. yes have read corman

some other solution did normal addition , subtraction , bang!! answer correct 1 such solution

   import java.util.*;     class main   {      public static void main(string[] args) {  //public static void main(string[] args) {     scanner scan=new scanner(system.in);     long t=scan.nextlong();     long fin;     while(t>0){         t--;         long n=scan.nextlong();         fin=-(-n^n);         system.out.println(fin); } }  } 

i showing had attempted :-

           import java.io.bufferedreader;          import java.io.ioexception;          import java.io.inputstreamreader;           import java.util.arraylist;          class code1         { static arraylist<long> combvalues=new arraylist<long>(); static arraylist<long> input=new arraylist<long>(); static arraylist<long> output=new arraylist<long>(); public static void main(string args[])throws ioexception {     bufferedreader br=new bufferedreader(new inputstreamreader(system.in));     //system.out.println("enter values of 't' ");     //system.out.println("input:");     int t=integer.parseint(br.readline());     //system.out.println("enter value of 'n' ");     for(int i=1;i<=t;i++)     {         input.add(long.parselong(br.readline()));     }     for(int i=0;i<t;i++)     {         output.add(computefx(input.get(i)));     }     //system.out.println("output:");     for(long i:output)     {         system.out.println(i);     } } public static long computefx(long n) {     combvalues=new arraylist<long>();     for(int i=1;i<=2*n-1;i+=2)     {         combvalues.add( factorial(2*n)/(factorial(2*n-i)*factorial(i)));     }     return computegx(); } public static long computegx() {     boolean flag=false;     long tempy=0;     long limit=combvalues.get(0);     outer:for(int i=new long(limit).intvalue();i>=1;i--)     {         inner:for(int j=0;j<(combvalues.size()/2)+1;j++)         {             if(combvalues.get(j)%i!=0)             {                    flag=false;                 break inner;             }             else             {                 flag=true;             }         }         if(flag)         {             tempy=i;             break outer;         }     }     return tempy; } public static long factorial(long n) {     long fact=1l;     for(int i=1;i<=n;i++)     {         fact*=i;     }     return fact; }     } 

okay question may subjective suggestion start from.

you find magic in given solution when try solving simple solution on piece of paper.

try 6 input. want find g(f(12,1), f(12,3), f(12,5), ... , f(12,11)). calculate fs, get: 12, 220, 792,... convert them binary.

the result should divide these values, can't greater smallest 1 (in case 12). in binary representations, @ 4 right-most bits (since 12 has 4 bits). in e.g. values greater other twelve have "1000" 4 right-most bits in binary representation.

so need find gcd of 12 , 8 ("1000" in binary)! ta da! have simpler question title of problem referes (the easiest problem). rest done in multiple ways solutions on code chef shows.

about question on how improve algorithms skills, beside books introduction algorithms, need solve lot of problems one. place start project euler. book can grasp lot of knowledge algorithms book called: algorithm design manual steven skiena.