Question

Java Recursion (Timelimit: 3 seconds)

Problem Description

Write a Java program to solve the following problem.

Recursion may appear in various contexts and in different forms. For fast implementation, we should always aim at transforming recursions into a simpler form of computation. In this assignment, the task is to evaluate X(·), which is defined as follows:

              |0,if m = 0 or n = 0

              | X(m,n−1),if n is odd and m is even

X(m,n) = | X(m−1,n),if m is odd and n is even

              | X(m−1,n−1) + m + n, otherwise.

Input:

The input is in ‘recursion.txt’. The first line of the input contains the line count c (1 ≤ c ≤ 1,000), which is the number of lines that follows the first line. Each of the following lines contains a pair of integers m,n (1 ≤ m,n ≤ 10,000).

Sample input: (with periods at the end)

3.

102,21.

10000,10000.

Output:

The output consists of c lines. Each line prints X(m,n) to a file ‘output.txt’.

Sample output:

2060.

100010000.

Information:

1. The expected complexity is O(1).

2. Write a code ‘A.java’ that reads ‘recursion.txt’ and writes the output in a file called ‘output.txt’.

3. The score will be 0 if your program does not terminate within 3 seconds.

Answer 1

//----------- A.java ------------

import java.io.*;
class A
{
   //function recursion definded in code.
   public static int X(int m,int n)
   {
       //System.out.println(m+" "+n);
       if(m == 0 || n== 0)
       {
           return 0;
       }
       //if m is even and n is odd
       if(m % 2==0 && n % 2 == 1)
       {
           return X(m,n-1);
       }
       //if m is odd and n is even
       else if(m % 2==1 && n % 2 == 0)
       {
           return X(m-1,n);
       }
       else
       {
           int res = X(m-1,n-1) + m + n;
           //System.out.println("--> "+res);
           return res;
       }
   }
   //answer for given recursion in terms of Time complexity of O(1)
   //function to return the sum of first n natural numbers.
   public static int sumOfFirstN(int n)
   {
       return n * (n+1) /2;
   }
   //equivalent function for X(m,n)
   public static int getRes(int m,int n)
   {
       //if m is less than n
       if(m<n)
       {
           //then the result will be sum of below terms.
           return sumOfFirstN(m) + sumOfFirstN(n) - sumOfFirstN(n-m);
       }
       //if n is less than m.
       else
       {
           //then the result will be sum of below terms.
           return sumOfFirstN(n) + sumOfFirstN(m) - sumOfFirstN(m-n);
       }
   }
   public static void main(String[] args)
   {
       //file input
       File f = new File("recursion.txt");
       //if the file exists are not.
       if(!f.exists())
       {
           System.out.println("recursion.txt is not found");
           return ;
       }
      
       try
       {
           //open file for reading
           //another file for writing.
           BufferedReader br = new BufferedReader(new FileReader(f));
           BufferedWriter bw = new BufferedWriter(new FileWriter(new File("output.txt")));
           //read a line from input file.
           String line = br.readLine();
           int m,n;
           //read number of lines to be read.
           int len = Integer.parseInt(line.trim());
           //read next line.
           line = br.readLine();
           //till file ended or length > 0
           while(line!=null && len>0)
           {
               line = line.trim();
               //split the data.
               String[] data = line.split(",");
               try
               {
                   //convert m,n
                   m = Integer.parseInt(data[0]);
                   n = Integer.parseInt(data[1]);
                   //call function that takes the O(1) time complexity to
                   //complete the task done by X(m,n) method.
                   bw.write(getRes(m,n)+"\n");
               }
               catch(Exception e)
               {
                   System.out.println("Invalid numbers m,n in line: "+line);
               }
               line = br.readLine();
               len--;
           }
           bw.close();
           br.close();
       }
       catch(Exception e)
       {
           System.out.println("Error occured while reading recursion.txt"+e);
       }
      
   }
}

//----------- recursion.txt -------
3
102,21
10000,10000
10,20
//output.txt ------------

2163
100010000
210