This morning, I suddenly remembered this challenge. But I nearly forgot the answer. I’d better to record it here for latter review.
Question Name: Find the Abnormal Number
Question Description: in a given integer array, every number, except one, appears N times. The exceptional number appear M times, where M % N != 0. Find the abnormal number.
The solution uses a lot of bit operations.
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/28/2014 * Last updated: 08/28/2014 * * Filename: FindAbnormalNumber.java * Compilation: javac FindAbnormalNumber.java * Execution: java FindAbnormalNumber * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.util.Arrays; /** * In an array, every number, except one, appears M times. Find the one, * which did not appear M times. * I am using Java for demo, because int in Java is always 32bits. * @author Sheng Yu codesays.com */ public class FindAbnormalNumber { /** * In the given array input, every number, except one, appears M time. * But the abnormal one appears N times, where N != k * M (k is a * non-negative integer). Find the number, appears N times, and return * it. * @param input to given array to search. * @param N the normal numbers appear M times in the array. * @return the abnormal number, did not appear M times. */ public int findAbnormal(int[] input, int N) { // In the first stage, bits[i] is used to store the sum of i(th) bit // in all input numbers. Because the input size is less than maximum // integer, the sum at one bit position is less than Integer.MAX_VALUE. // So we do not need to consider the overflow issue. // http://stackoverflow.com/questions/3038392/do-java-arrays-have-a-maximum-size int[] bits = new int[32]; // The order of the two loops does not change the algorithm complexity. // But due to cache system, the input traversal be outside should have // a better performance. for (int item : input) { for (int i = 0; i < 32; ++i) { bits[i] += (item >> i) & 0b1; } } // Let the abnormal number be X. In the second stage, we compute the // value of each bit in X. // For all other normal numbers, appearing M times, it is either 0 or 1 // in i(th) bit. So sum of this bit is either 0 or M. In both cases, // sum % M = 0. // So if bits[i] % M == 0, the i(th) bit of X is 0; // Otherwise, the i(th) bit is 1. for (int i = 0; i < 32; ++i) { bits[i] %= N; bits[i] = bits[i] == 0 ? 0 : 1; } // bits[i] stores the value of each bit for the abnormal number. // Rebuild the number from the array. int result = 0; for (int i = 0; i < 32; ++i) { if (bits[i] == 1) result |= 1 << i; } return result; } /** * The helper function to test the findAbnormal function. * @param input to given array to search. * @param M the normal numbers appear M times in the array. * @param expected the right answer. */ public void testHelper(int[] input, int M, int expected) { StringBuilder sb = new StringBuilder(); sb.append("Test Case "); sb.append(Arrays.toString(input)); sb.append(" - M = "); sb.append(M); sb.append(this.findAbnormal(input, M) == expected ? ": PASS" : ": FAIL"); System.out.println(sb); return; } /** * Stub for test. * @param args the command line arguments. */ public static void main(String[] args) { FindAbnormalNumber finder = new FindAbnormalNumber(); finder.testHelper(new int[] {1, 3, 3, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 2}, 5, 3); finder.testHelper(new int[] {2, 1, 1, 1, 2}, 3, 2); finder.testHelper(new int[] {1, 0, 2, 2, 0}, 2, 1); finder.testHelper(new int[] {1, 0, 2, 2, 1}, 2, 0); finder.testHelper(new int[] {-2, -3, -2, -1, -2, -3, -1, -1}, 3, -3); finder.testHelper(new int[] {-2, -3, -2, -1, -2, -3, -1, -1}, 3, -3); finder.testHelper(new int[] {8, 23, 94, 8, 23, -9, -9, 94, -31}, 2, -31); finder.testHelper(new int[] {37, -95, -95, 37, -32, -32, 37, -32}, 3, -95); finder.testHelper(new int[] {37, -95, -95, 37, -32, -32, 37, -32, -95, 37}, 3, 37); } } |
Can you remember the time complexity requirement by any chance?
Should be O(N), where N is the length of input array, and considering the length of interger is constantly 32 or 64.