Compare Two Integers

From programming_contest
Jump to: navigation, search

Introduction

You are given two very long integers a, b (leading zeroes are allowed). You should check what number a or b is greater or determine that they are equal.

The input size is very large so don't use the reading of symbols one by one. Instead of that use the reading of a whole line or token.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java. Don't use the function input() in Python2 instead of it use the function raw_input().

Solutions

Idea

This problem cannot be solved simply using "parseInt" and compareTo to return the greater integer, because the numbers can be too big for Java to process using Integer. So I went about solving the problem with the simplest way I could think of, which would be to compare the length of the two integers. Of course, this is after the two integers are processed to remove any leading zeroes to make sure the test of checking their lengths works and does not take the leading zeroes as actual digit-values. If one number is longer than another, it is automatically larger in value than the other one. If the two integers are the same length, I iterate through each digit and find the first point of difference. Because I start at the largest digit, the first point of difference will yield which integer is larger, without having to consider any subsequent digits (they are all smaller in value than the one currently being compared).

Runtime

Worst case runtime is O(n), where n is the length of the longer integer.

Code

Solution - Java

 1 import java.util.Scanner;
 2 
 3 /**
 4  * 
 5  * @author Created by harrisonsuh
 6  *
 7  */
 8 
 9 public class CompareTwoIntegers {
10 	public static void main(String[] args) {
11 		Scanner in = new Scanner(System.in);
12 		String a = in.next();
13 		String b = in.next();
14 		//remove any leading zeroes from first int
15 		for (int i = 0; i < a.length(); i++) {
16 			if (Integer.parseInt(a.substring(i, i+1)) != 0 || i+1 == a.length()) {
17 				a = a.substring(i);
18 				break;
19 			}
20 		}
21 		//remove any leading zeroes for second int
22 		for (int i = 0; i < b.length(); i++) {
23 			if (Integer.parseInt(b.substring(i, i+1)) != 0 || i+1 == b.length()) {
24 				b = b.substring(i);
25 				break;
26 			}
27 		}
28 		//compare lengths of the two integers
29 		if (a.length() < b.length()) {
30 			System.out.println('<');
31 		} else if (a.length() > b.length()) {
32 			System.out.println('>');
33 		//if they are the same length, iterate through each digit and find first point of difference
34 		} else if (a.length() == b.length()) {
35 			for (int i = 0; i < a.length(); i++) {
36 				if (a.charAt(i) > b.charAt(i)) {
37 					System.out.println('>');
38 					return;
39 				}
40 				if (a.charAt(i) < b.charAt(i)) {
41 					System.out.println('<');
42 					return;
43 				}
44 			}
45 		//if all tests pass (all digits are equal), return they are equal.
46 		System.out.println('=');
47 		return;
48 		}
49 	}
50 }