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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
