Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1351
Question Name: Numbers Appear Once
Question Description: in an int array, every number appears even count of times, except two numbers, which appear only once. Find the two numbers.
Input: the input might contain multiple test cases. Inside each test case, the first line includes one integer N (1 <= N <= 10^6), saying the number of items in the array. The second line contains N integers as the content of the array.
Output: print the two numbers, with the smaller one firstly.
1 2 3 4 5 | Input: 8 2 4 3 6 3 2 5 5 Output: 4 6 |
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/08/2014 * Last updated: 09/08/2014 * * Filename: NumbersAppearOnce.java * Compilation: javac NumbersAppearOnce.java * Execution: java NumbersAppearOnce * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * An utility to find the two numbers ,which appear once in the array, * while the other numbers appear twice. * @author Sheng Yu codesays.com */ public class NumbersAppearOnce { /** * In the given integer array, two and only two numbers appear once. * And all other numbers appear even number of times. Find out the two * numbers and show them. * @param input the array to find the two numbers, which appear once. */ public static void showNumbersAppearOnce(int[] input) { // Find the lowest bit, where the two numbers are different. int distinguisher = 0; for (int i : input) distinguisher ^= i; distinguisher &= ~(distinguisher - 1); // According to the distinguisher, divide the input into two groups. // And the two numbers must be in different group. int first = 0; int second = 0; for (int i: input) { if ((i & distinguisher) == 0) first ^= i; else second ^= i; } // Print the two numbers System.out.print(Math.min(first, second)); System.out.print(" "); System.out.println(Math.max(first, second)); return; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int[] input = null; while (st.nextToken() != StreamTokenizer.TT_EOF) { input = new int[(int) st.nval]; for (int i = 0; i < input.length; ++i) { st.nextToken(); input[i] = (int) st.nval; } showNumbersAppearOnce(input); } } } |