Java Generics to Code Efficiently in Competitive Programming

0 0 7 minutes read

Templates are the foundation of generic programming, which involve writing code in a way that is independent of any particular type. These powerful tools can be used for writing our code effectively. Some cool tricks that may be used in Competitive Programming are given as follows:

Fast Input/Output:

This uses the time advantage of BufferedReader and StringTokenizer and the advantage of user-defined methods for less typing and therefore a faster input altogether. Below is the code to find the sum of N integers using fast reader and writer.

Java

// Java program to illustrate the fast 
// input output 
import java.io.*; 
import java.util.StringTokenizer; 
  
public class GFG { 
  
    // Driver Code 
    public static void main(String[] args) 
        throws IOException 
    { 
  
        // Initialize the reader 
        FastReader reader = new FastReader(); 
  
        // Initialize the writer 
        FastWriter writer = new FastWriter(); 
  
        // Your Code here 
  
        // Reads a single integer 
        int n = reader.readSingleInt(); 
  
        // Reads a array of N number 
        // in a line 
        int a[] = reader.readIntArray(n); 
  
        // Prints a string 
        writer.writeString("SUM OF :"); 
  
        // Print the array of number 
        // with spaces 
        writer.writeIntArrayWithSpaces(a); 
  
        int sum = 0; 
        for (int i = 0; i < n; i++) { 
            sum += a[i]; 
        } 
  
        // Prints a single number 
        writer.writeSingleInteger(sum); 
    } 
  
    // Fast Reader Class 
    public static class FastReader { 
  
        // Reader object 
        BufferedReader reader; 
  
        // Constructor 
        public FastReader() 
        { 
            // Initialize the reader 
            reader = new BufferedReader( 
                new InputStreamReader( 
                    System.in)); 
        } 
  
        // String tokenizer 
        StringTokenizer tokenizer; 
  
        // Function to read integer 
        public int readSingleInt() 
            throws IOException 
        { 
            return Integer.parseInt( 
                reader.readLine()); 
        } 
  
        // Function to read a single long 
        public long readSingleLong() 
            throws IOException 
        { 
            return Long.parseLong( 
                reader.readLine()); 
        } 
  
        // Function to read a array of 
        // numsInts integers in 1 line 
        public int[] readIntArray(int numInts) 
            throws IOException 
        { 
            int[] nums = new int[numInts]; 
            tokenizer 
                = new StringTokenizer( 
                    reader.readLine()); 
  
            // Input Numbers 
            for (int i = 0; i < numInts; i++) { 
                nums[i] = Integer.parseInt( 
                    tokenizer.nextToken()); 
            } 
            return nums; 
        } 
  
        // Function to read string 
        public String readString() 
            throws IOException 
        { 
            return reader.readLine(); 
        } 
    } 
  
    // Fast Writer Class 
    public static class FastWriter { 
  
        // Writer object 
        BufferedWriter writer; 
  
        // Constructor 
        public FastWriter() 
        { 
  
            // Initialize the writer 
            writer = new BufferedWriter( 
                new OutputStreamWriter( 
                    System.out)); 
        } 
  
        // Function to write single integer 
        public void writeSingleInteger(int i) 
            throws IOException 
        { 
            writer.write(Integer.toString(i)); 
            writer.newLine(); 
            writer.flush(); 
        } 
  
        // Function to write a single long 
        public void writeSingleLong(long i) 
            throws IOException 
        { 
            writer.write(Long.toString(i)); 
            writer.newLine(); 
            writer.flush(); 
        } 
  
        // Function to write a Integer 
        // of array with spaces in 1 line 
        public void writeIntArrayWithSpaces( 
            int[] nums) 
            throws IOException 
        { 
            for (int i = 0; i < nums.length; i++) { 
                writer.write(nums[i] + " "); 
            } 
            writer.newLine(); 
            writer.flush(); 
        } 
  
        // Function to write a Integer 
        // of array without spaces 
        // in 1 line 
        public void writeIntArrayWithoutSpaces(int[] nums) 
            throws IOException 
        { 
            for (int i = 0; 
                 i < nums.length; i++) { 
                writer.write( 
                    Integer.toString( 
                        nums[i])); 
            } 
            writer.newLine(); 
            writer.flush(); 
        } 
  
        // Function to write a String 
        public void writeString(String s) 
            throws IOException 
        { 
            writer.write(s); 
            writer.newLine(); 
            writer.flush(); 
        } 
    } 
}

In order to change the input and output stream based on the environment to text files or to standard input as usually done while using sublime text or other IDEs use the below code as template of FastIO.

Java

// Java program to illustrate the 
// fast input output 
import java.io.*; 
import java.util.StringTokenizer; 
  
public class GFG { 
    public
  
        // Driver Code 
        static void main(String[] args) throws IOException 
    { 
  
        // Initialize the reader 
        FastReader reader = new FastReader(); 
  
        // Initialize the writer 
        FastWriter writer = new FastWriter(); 
  
        // Your Code here 
    } 
  
    // Fast Reader Class 
    public static class FastReader { 
  
        // Reader object 
        BufferedReader reader; 
  
        // Constructor 
        public FastReader() 
        { 
  
            // Initialize the reader 
            reader = new BufferedReader( 
                new InputStreamReader( 
                    System.in)); 
  
            if (System.getProperty( 
                    "ONLINE_JUDGE") 
                == null) { 
                try { 
                    reader = new BufferedReader( 
                        new InputStreamReader( 
                            new FileInputStream( 
                                "input.txt"))); 
                } 
                catch (Exception e) { 
                } 
            } 
        } 
  
        // String tokenizer 
        StringTokenizer tokenizer; 
  
        // Function to read a 
        // single integer 
        public int readSingleInt() 
            throws IOException 
        { 
            return Integer.parseInt( 
                reader.readLine()); 
        } 
  
        // Function to read a 
        // single long 
        public long readSingleLong() 
            throws IOException 
        { 
            return Long.parseLong( 
                reader.readLine()); 
        } 
  
        // Function to read a array 
        // of numsInts integers 
        // in one line 
        public int[] readIntArray(int numInts) 
            throws IOException 
        { 
            int[] nums = new int[numInts]; 
            tokenizer 
                = new StringTokenizer( 
                    reader.readLine()); 
  
            for (int i = 0; 
                 i < numInts; i++) { 
                nums[i] = Integer.parseInt( 
                    tokenizer.nextToken()); 
            } 
            return nums; 
        } 
  
        // Function to read string 
        public String readString() 
            throws IOException 
        { 
            return reader.readLine(); 
        } 
    } 
  
    // Fast Writer Class 
    public static class FastWriter { 
  
        // Writer object 
        BufferedWriter writer; 
  
        // Constructor 
        public FastWriter() 
        { 
  
            // Initialize the writer 
            writer = new BufferedWriter( 
                new OutputStreamWriter( 
                    System.out)); 
            if (System.getProperty( 
                    "ONLINE_JUDGE") 
                == null) { 
                try { 
                    writer = new BufferedWriter( 
                        new OutputStreamWriter( 
                            new FileOutputStream( 
                                "output.txt"))); 
                } 
                catch (Exception e) { 
                } 
            } 
        } 
  
        // Function to write the 
        // single integer 
        public void writeSingleInteger(int i) 
            throws IOException 
        { 
            writer.write(Integer.toString(i)); 
            writer.newLine(); 
            writer.flush(); 
        } 
  
        // Function to write single long 
        public void writeSingleLong(long i) 
            throws IOException 
        { 
            writer.write(Long.toString(i)); 
            writer.newLine(); 
            writer.flush(); 
        } 
  
        // Function to write a Integer of 
        // array with spaces in one line 
        public void writeIntArrayWithSpaces(int[] nums) 
            throws IOException 
        { 
            for (int i = 0; 
                 i < nums.length; i++) { 
                writer.write(nums[i] 
                             + " "); 
            } 
            writer.newLine(); 
            writer.flush(); 
        } 
  
        // Function to write Integer of 
        // array without spaces in 1 line 
        public void writeIntArrayWithoutSpaces(int[] nums) 
            throws IOException 
        { 
            for (int i = 0; 
                 i < nums.length; i++) { 
                writer.write( 
                    Integer.toString( 
                        nums[i])); 
            } 
            writer.newLine(); 
            writer.flush(); 
        } 
  
        // Function to write String 
        public void writeString(String s) 
            throws IOException 
        { 
            writer.write(s); 
            writer.newLine(); 
            writer.flush(); 
        } 
    } 
}

Note: For Information above Fast Input/Output in Java please refer to this post.

Functions commonly used in Competitive Programming:

Below are the functions that are commonly used during competitive programming, one can include them in the code to avoid wastage of time implementing it during the contest.

Pairs in Java:

Pairs are commonly used in competitive programming. It is an easy way to use pairs in JAVA. Below is the implementation of the same:

Java

// Java program to illustrate the 
// use Pairs 
import java.io.*; 
  
class GFG { 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        // Initialize a pair 
        Pair<Integer, Integer> x 
            = new Pair<Integer, Integer>(1, 2); 
  
        // Print pair 
        System.out.println(x.first + ", "
                           + x.second); 
    } 
  
    // Pair class 
    static class Pair<A, B> { 
        A first; 
        B second; 
  
        // Constructor 
        public Pair(A first, B second) 
        { 
            this.first = first; 
            this.second = second; 
        } 
    } 
}

Fast Exponential using mod:

Java

// Function to find x ^ n using p as mod 
static long power(long x, long y, long p) 
{ 
  
    // Initialize result 
    long res = 1; 
  
    // Update x if it is more than or 
    // equal to p 
    x = x % p; 
  
    while (y > 0) { 
  
        // If y is odd, multiply x 
        // with result 
        if (y % 2 == 1) 
            res = (res * x) % p; 
  
        // y must be even now 
        y = y >> 1; // y = y/2 
        x = (x * x) % p; 
    } 
  
    return res; 
}

nCr using Fermat Little Theorem:

Java

// Function to find x ^ n using p as mod 
static long power(long x, long y, long p) 
{ 
  
    // Initialize result 
    long res = 1; 
  
    // Update x if it is more than or 
    // equal to p 
    x = x % p; 
  
    while (y > 0) { 
  
        // If y is odd, multiply x 
        // with result 
        if (y % 2 == 1) 
            res = (res * x) % p; 
  
        // y must be even now 
        y = y >> 1; // y = y/2 
        x = (x * x) % p; 
    } 
  
    return res; 
} 
  
// Returns n^(-1) mod p 
static long modInverse(long n, long p) 
{ 
    return power(n, p - 2, p); 
} 
  
// Returns nCr % p using Fermat's 
// little theorem. 
static long nCrModPFermat(int n, int r, long p) 
{ 
  
    // Base case 
    if (r == 0) 
        return 1; 
  
    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r 
    long[] fac = new long[n + 1]; 
    fac[0] = 1; 
  
    for (int i = 1; i <= n; i++) 
        fac[i] = fac[i - 1] * i % p; 
  
    return (fac[n] * modInverse(fac[r], p) % p 
            * modInverse(fac[n - r], p) % p) 
        % p; 
}

Binomial Coefficient:

Binomial coefficient is mostly used to find the value of [n * (N – 1) *—* (N – K + 1)] / [K * (K – 1) *—-* 1]). Below is the program to implement the same:

Java

// Function to implement the 
// binomial coefficient 
static long binomialCoeff(long n, 
                          long k, 
                          long MOD) 
{ 
    long res = 1; 
  
    // Since C(n, k) = C(n, n-k) 
    if (k > n - k) 
        k = n - k; 
  
    // Find the value of 
    // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1] 
    for (int i = 0; i < k; ++i) { 
        res *= (n - i); 
        res /= (i + 1); 
        res %= MOD; 
    } 
  
    // Return the result 
    return res; 
}

Modular Arithmetic:

Java

const int mod = 1000000007; 
  
// Function to implement the modular 
// arithmetic addition 
private static long modular_add(long a, long b) 
{ 
    return ((a % mod) + (b % mod)) % mod; 
} 
  
// Function to implement the modular 
// arithmetic subtraction 
private static long modular_sub(long a, long b) 
{ 
    return ((a % mod) - (b % mod) + mod) % mod; 
} 
  
// Function to implement the modular 
// arithmetic multiplication 
private static long modular_mult(long a, long b) 
{ 
    return ((a % mod) * (b % mod)) % mod; 
}

Sort an array:

Java

// Function to sort an integer array 
static void sort(int[] a) 
{ 
    // Stores the element in arraylist 
    ArrayList<Integer> l = new ArrayList<>(); 
    for (int i : a) 
        l.add(i); 
  
    // Use collection.sort() method 
    Collections.sort(l); 
  
    // Update the original array 
    // with the sorted array elements 
    for (int i = 0; i < a.length; i++) 
        a[i] = l.get(i); 
}

GCD and LCM:

Java

static long lcm(int a, int b) 
{ 
    return (a / gcd(a, b)) * b; 
} 
  
private static long gcd(long a, long b) 
{ 
    if (b == 0) { 
        return a; 
    } 
    return gcd(b, a % b); 
}

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!