Repeating number in an array

Question

we are given a read only array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Return A and B. I know my solution is not space efficient but i am wondering why i am getting wrong output for cases like:

389, 299, 65, 518, 361, 103, 342, 406, 24, 79, 192, 181, 178, 205, 38, 298, 218, 143, 446, 324, 82, 41, 312, 166, 252, 59, 91, 6, 248, 395, 157, 332, 352, 57, 106, 246, 506, 261, 16, 470, 224, 228, 286, 121, 193, 241, 203, 36, 264, 234, 386, 471, 225, 466, 81, 58, 253, 468, 31, 197, 15, 282, 334, 171, 358, 209, 213, 158, 355, 243, 75, 411, 43, 485, 291, 270, 25, 100, 194, 476, 70, 402, 403, 109, 322, 421, 313, 239, 327, 238, 257, 433, 254, 328, 163, 436, 520, 437, 392, 199, 63, 482, 222, 500, 454, 84, 265, 508, 416, 141, 447, 258, 384, 138, 47, 156, 172, 319, 137, 62, 85, 154, 97, 18, 360, 244, 272, 93, 263, 262, 266, 290, 369, 357, 176, 317, 383, 333, 204, 56, 521, 502, 326, 353, 469, 455, 190, 393, 453, 314, 480, 189, 77, 129, 439, 139, 441, 443, 351, 528, 182, 101, 501, 425, 126, 231, 445, 155, 432, 418, 95, 375, 376, 60, 271, 74, 11, 419, 488, 486, 54, 460, 321, 341, 174, 408, 131, 115, 107, 134, 448, 532, 292, 289, 320, 14, 323, 61, 481, 371, 151, 385, 325, 472, 44, 335, 431, 187, 51, 88, 105, 145, 215, 122, 162, 458, 52, 496, 277, 362, 374, 26, 211, 452, 130, 346, 10, 315, 459, 92, 531, 467, 309, 34, 281, 478, 477, 136, 519, 196, 240, 12, 288, 302, 119, 356, 503, 527, 22, 27, 55, 343, 490, 127, 444, 308, 354, 278, 497, 191, 294, 117, 1, 396, 125, 148, 285, 509, 208, 382, 297, 405, 245, 5, 330, 311, 133, 274, 275, 118, 463, 504, 39, 99, 442, 337, 169, 140, 104, 373, 221, 499, 413, 124, 510, 159, 465, 80, 276, 83, 329, 524, 255, 387, 259, 397, 491, 517, 23, 4, 230, 48, 349, 412, 142, 114, 487, 381, 164, 35, 67, 498, 73, 440, 108, 226, 96, 132, 144, 207, 235, 33, 69, 128, 236, 364, 198, 475, 173, 493, 150, 90, 515, 111, 68, 232, 340, 112, 526, 492, 512, 495, 429, 146, 336, 17, 350, 251, 7, 184, 76, 380, 359, 293, 19, 49, 345, 227, 212, 430, 89, 474, 279, 201, 398, 347, 273, 37, 185, 177, 102, 304, 295, 422, 94, 426, 514, 116, 183, 180, 494, 42, 305, 152, 390, 30, 247, 451, 32, 388, 331, 78, 424, 368, 394, 188, 306, 449, 8, 214, 120, 179, 280, 511, 409, 338, 153, 507, 370, 461, 217, 161, 483, 147, 242, 86, 417, 268, 71, 462, 420, 167, 513, 379, 307, 522, 435, 113, 296, 457, 525, 45, 529, 423, 427, 2, 438, 64, 316, 46, 40, 13, 516, 367, 233, 110, 318, 250, 283, 216, 186, 310, 237, 377, 365, 175, 479, 378, 66, 414, 473, 165, 210, 50, 348, 372, 363, 339, 20, 168, 284, 415, 505, 206, 53, 223, 434, 202, 123, 399, 400, 135, 269, 428, 219, 456, 28, 464, 267, 489, 98, 391, 195, 366, 300, 484, 533, 229, 213, 149, 160, 256, 303, 530, 301, 29, 404, 344, 401, 220, 287, 9, 407, 170, 450, 523, 249, 72, 410, 3, 21, 200, 260

Expected Output:

213 87

Actual Output :

213 3

Java Code What I have Tried so far

public class Solution {
    // DO NOT MODIFY THE LIST
    public ArrayList<Integer> repeatedNumber(final List<Integer> a) {
        int n=a.size();
        int rep=0,b=0;
        int[] arr= new int[n+1];
        for(int i=0;i<n+1;i++) //value i is at index i
            arr[i]=i;
        arr[0]=-1;
        for(int val : a)
        {
            if(arr[val]!=-1)
                arr[val]=-1;
            else
            {
                rep=val;
                break;
            }
        }
        for(int i=0; i<n+1; i++)
        {
            if(arr[i]!=-1)
            {
                b=i;
                break;
            }
        }
        ArrayList<Integer> ans = new ArrayList<Integer>();
        ans.add(rep);
        ans.add(b);
        return ans;
    }
}

[This](http://stackoverflow.com/questions/10764286/using-xor-operator-for-finding-duplicate-elements-in-a-array-fails-in-many-cases) might help — TheLostMind, Mar 18 '16 at 05:08
@laune - He could find duplicate number using XOR. Next, to find the missing number he could do `(n (n+1)) / 2` - sum of current array — TheLostMind, Mar 18 '16 at 05:17
@user6038386 Please look into my solution. Isn't this efficient ? — Vikrant Kashyap, Mar 18 '16 at 05:31
@TheLostMind I don't think you can do that if you have both flaws in the data at the same time. — laune, Mar 18 '16 at 05:44

laune · Accepted Answer · 2016-03-18T13:57:05.287

You find a mistake like this by reasoning that you need one complete pass over the array to detect a missing value. You may stop earlier for the duplicate.

for(int val : a){
    if(arr[val]!=-1){
        arr[val]=-1;
    } else {
        rep=val;
        ///////////////// Omit:      break;
    }
}

Later Basically the same idea but using a bit more of Java, making it shorter:

int dup = 0;
int abs = 0;
BitSet present = new BitSet( a.size() + 1 );
for( int x: a ){
    if( present.get( x ) ){
        dup = x;
    } else {
        present.set( x );
    }
}
abs = present.nextClearBit( 1 );

If you may modify the original array (or list), you can avoid using some extra storage:

int dup = 0;
int abs = 0;
for( int i = 0; i < a.length; ++i ){
    if( a[i] <= 0 ) continue;
    int val = a[i];
    a[i] = 0;
    while( true ){
        if( a[val-1] == -val ){
            dup = val;
            break;
        } else {
            int h = a[val-1];
            a[val-1] = -val;
            if( h == 0 ) break;
            val = h;
        }
    }
}
for( int i = 0; i < a.length; ++i ){
    if( a[i] >= 0 ){
         abs = i+1;
         break;
    }
}

But I am still wondering, why this is happening, can you plz elaborate more? for " you need one complete pass over the array to detect a missing value" -- > This loop is for finding duplicate not the missing number!! — Naveen Kumar, Mar 18 '16 at 06:49
But you mark the places where there *is* a number - so it's equivalent to finding the missing number, like a negative on a film :-) — laune, Mar 18 '16 at 07:54

score 0 · Answer 2 · answered Mar 18 '16 at 05:13

I would begin by using List.toArray(T[]) to get an array, sorting the array and then iterating the sorted array once. Something like,

public ArrayList<Integer> repeatedNumber(final List<Integer> a) {
    Integer[] arr = a.toArray(new Integer[0]);
    Arrays.sort(arr);
    Integer[] r = new Integer[2];
    for (int i = 1; i < arr.length; i++) {
        int prev = arr[i - 1];
        if (prev == arr[i]) {
            r[0] = prev;
        } else if (prev != arr[i] - 1) {
            r[1] = prev + 1;
        }
    }
    return new ArrayList<Integer>(Arrays.asList(r));
}

which I tested with your input and got (as requested)

[213, 87]

Why use an algorithm with a higher O()? – laune Mar 18 '16 at 05:20 — laune, Mar 18 '16 at 05:20
@laune Why (prematurely) optimize? – Elliott Frisch Mar 18 '16 at 05:32 — Elliott Frisch, Mar 18 '16 at 05:32

score 0 · Answer 3 · answered Mar 18 '16 at 05:30

Here is a solution that doesn't alter the original list and finds the missing one using only maths.

public static void main(String[] args) {
    find(new int[]{389, 299, 65, 518, 361, 103, 342, 406, 24, 79, 192, 181, 178, 205, 38, 298, 218, 143, 446, 324, 82, 41, 312, 166, 252, 59, 91, 6, 248, 395, 157, 332, 352, 57, 106, 246, 506, 261, 16, 470, 224, 228, 286, 121, 193, 241, 203, 36, 264, 234, 386, 471, 225, 466, 81, 58, 253, 468, 31, 197, 15, 282, 334, 171, 358, 209, 213, 158, 355, 243, 75, 411, 43, 485, 291, 270, 25, 100, 194, 476, 70, 402, 403, 109, 322, 421, 313, 239, 327, 238, 257, 433, 254, 328, 163, 436, 520, 437, 392, 199, 63, 482, 222, 500, 454, 84, 265, 508, 416, 141, 447, 258, 384, 138, 47, 156, 172, 319, 137, 62, 85, 154, 97, 18, 360, 244, 272, 93, 263, 262, 266, 290, 369, 357, 176, 317, 383, 333, 204, 56, 521, 502, 326, 353, 469, 455, 190, 393, 453, 314, 480, 189, 77, 129, 439, 139, 441, 443, 351, 528, 182, 101, 501, 425, 126, 231, 445, 155, 432, 418, 95, 375, 376, 60, 271, 74, 11, 419, 488, 486, 54, 460, 321, 341, 174, 408, 131, 115, 107, 134, 448, 532, 292, 289, 320, 14, 323, 61, 481, 371, 151, 385, 325, 472, 44, 335, 431, 187, 51, 88, 105, 145, 215, 122, 162, 458, 52, 496, 277, 362, 374, 26, 211, 452, 130, 346, 10, 315, 459, 92, 531, 467, 309, 34, 281, 478, 477, 136, 519, 196, 240, 12, 288, 302, 119, 356, 503, 527, 22, 27, 55, 343, 490, 127, 444, 308, 354, 278, 497, 191, 294, 117, 1, 396, 125, 148, 285, 509, 208, 382, 297, 405, 245, 5, 330, 311, 133, 274, 275, 118, 463, 504, 39, 99, 442, 337, 169, 140, 104, 373, 221, 499, 413, 124, 510, 159, 465, 80, 276, 83, 329, 524, 255, 387, 259, 397, 491, 517, 23, 4, 230, 48, 349, 412, 142, 114, 487, 381, 164, 35, 67, 498, 73, 440, 108, 226, 96, 132, 144, 207, 235, 33, 69, 128, 236, 364, 198, 475, 173, 493, 150, 90, 515, 111, 68, 232, 340, 112, 526, 492, 512, 495, 429, 146, 336, 17, 350, 251, 7, 184, 76, 380, 359, 293, 19, 49, 345, 227, 212, 430, 89, 474, 279, 201, 398, 347, 273, 37, 185, 177, 102, 304, 295, 422, 94, 426, 514, 116, 183, 180, 494, 42, 305, 152, 390, 30, 247, 451, 32, 388, 331, 78, 424, 368, 394, 188, 306, 449, 8, 214, 120, 179, 280, 511, 409, 338, 153, 507, 370, 461, 217, 161, 483, 147, 242, 86, 417, 268, 71, 462, 420, 167, 513, 379, 307, 522, 435, 113, 296, 457, 525, 45, 529, 423, 427, 2, 438, 64, 316, 46, 40, 13, 516, 367, 233, 110, 318, 250, 283, 216, 186, 310, 237, 377, 365, 175, 479, 378, 66, 414, 473, 165, 210, 50, 348, 372, 363, 339, 20, 168, 284, 415, 505, 206, 53, 223, 434, 202, 123, 399, 400, 135, 269, 428, 219, 456, 28, 464, 267, 489, 98, 391, 195, 366, 300, 484, 533, 229, 213, 149, 160, 256, 303, 530, 301, 29, 404, 344, 401, 220, 287, 9, 407, 170, 450, 523, 249, 72, 410, 3, 21, 200, 260});
}

public static void find(int[] numbers){
    int sum = 0;
    int duplicate = -1;

    for (int i = 0; i < numbers.length; i++) {
        sum += numbers[i];

        if(duplicate == -1) {
            for (int j = i + 1; j < numbers.length; j++) {
                if(numbers[i] == numbers[j]){
                    duplicate = numbers[i];
                }
            }
        }
    }

    int missing = triangle(numbers.length) - (sum - duplicate);

    System.out.println(duplicate + " " + missing);
}

public static int triangle(int amount) {
    return (int) ((Math.pow(amount, 2) + amount) / 2);
}

score -1 · Answer 4 · answered Mar 18 '16 at 05:29

I would suggest a better approach to do this. Here is logical steps that you need to follow.

I am explaining with an Example

ex:- incorrect Array => {20,30,40,40} and Correct Array => {20,30,40,60}

First Calculate Sum of correct Array and incorrect Array.

incorrect Array sum => 130 and Correct Array => 150.

Calculate the difference between the sum of these two Arrays.

Difference will be -20(Negative).

Then Find the Integer value which is Repeated.

Using loop Iteration find out the Number which is getting RepeatedFrom Incorrect Array. So Repeated Number will be 40.

Now Substract this Repeated Number with Difference You Found (Between the two Sum).

(-20)-(-40) = -60 You Got Your Missing Number .

Finally You will got your Missing Number in Negative. it is more efficient way to do this.

Note :- If you Iterate throughout one Incorrect array (n) in (n*n) in Nested Loops and again in Nested Loop Iterate throughout Correct array (n) in (n*n) So, Total will be (n*n*n*n). Its very hectic actually. In Solution which is given by me will max upto ((n*n)+n+n). So Definitely

Repeating number in an array

4 Answers4