BigInteger

BigInteger Overview

Frequently, in your competitive programming travels, you will come across problems that require you to calculate integers that are larger than can be held by a primitive int variable. For these cases, we need to use a different type of integer called BigInteger. As the capitalization implies, it is a class (just as Integer is a class). BigInteger is different from int (and Integer) in that it can hold integers of arbitrary size (which means that you can make them as big as you want). Using BigInteger has its own complications which we will study here. Note that operations on BigIntegers take much more time than primitive ints or even the class-based Integer. Thus, we tend to use BigIntegers only when necessary - when the problem dictates that the answers are going to be really large. The Java libraries also provide a BigDecimal class. But we will not study it here.

"BigInteger represents immutable arbitrary-precision integers. It is similar to the primitive integer types but allows arbitrary large values. It is used when integers involved are larger than the limit of long type.

For example, the factorial of 50 is 30414093201713378043612608166064768844377641568960512000000000000.

BigInteger provides analogues to all of Java's primitive integer operators, and all relevant methods from java. lang. Math. Additionally, BigInteger provides operations for modular arithmetic, GCD calculation, primality testing, prime generation, bit manipulation, and a few other miscellaneous operations." - Oracle

BigInteger Example: Calculating Large Fibonacci Numbers

BigInteger Practice #1

Do the String-to-Integer problem in leetcode. The link is here.

Hints:

1. You will need BigInteger to cap your answer to Integer.MAX_VALUE or Integer.MIN_VALUE as described in the problem.

2. You will also need to import the java.math.BigInteger library as the first line of your solution in leetcode.

3. As always, be sure to set the language to java.

Try to do the problem initially without looking at the algorithm, below. If you cannot solve the problem, go ahead and implement the algorithm shown to arrive at your solution.

import java.math.BigInteger;

class Solution {

public int myAtoi(String s) {

// first, get rid of all leading and trailing whitespace from s

// if the resulting string has zero length, return a zero immediately.

// create a sign variable and set it equal to 1. if the first character of s is '-', set the sign variable to -1.

// check to see if the first character of s is '+' or '-'. if it is, skip this character in the analysis that follows.

// create a string variable that will hold the digits in s. set it to be the empty string initially.

// go through s (left to right) and check to see if each character is a digit. if so, concatenate it to your string variable.

// if you reach the end of the string s or find a character that is not a digit, stop concatenating to your string variable.

// if your string variable (that now contains the digits of string s) is of zero length return a zero immediately.

// convert your string variable to a BigInteger

// if your sign variable is -1, negate your BigInteger

// check your BigInteger to see if it is larger than Integer.MAX_VALUE. If it is, cap it at MAX_VALUE;

// check your BigInteger to see if is smaller than Integer.MIN_VALUE. If it is, cap it at MIN_VALUE;

// convert your BigInteger to an integer and return it as the answer.

}

}