Geek asks and answers

Find pairs that sum with X in an array of integers of size N that has an element in the range from 0 to N-1

This is an interview question. We have an array of integers of size N containing an element from 0 to N-1. It is possible that the number may occur more than two times. The goal is to find pairs that add up to a given number X.

I did this using an auxiliary array having a counter of the elements of the primary array, and then rearranging the primary auxiliary array so that the primary order is sorted and then looks for pairs.

But the interviewer needed constant spatial complexity, so I told him to sort the array, but this solution is nlogn time complex. He needs a solution O (n).

Is there any method for this in O (n) without extra space?

+5
source share
3 answers

No, I do not believe. You need extra space to be able to "sort" the data in O (n) by assigning to buckets, or you need to sort a place that will not be O (n).

Of course, there are always tricks if you can make certain assumptions. For example, if N < 64Kyour integers are 32 bits wide, you can multiplex the space needed for the count array on top of the current array.

In other words, use the lower 16 bits to store the values ​​in the array, and then use the upper 16 bits for your array, where you simply store the counter of the values ​​corresponding to the index.

, N == 8. , 8 , 8, . (), .

  0    1    2    3    4    5    6    7    <- index
(0)7 (0)6 (0)2 (0)5 (0)3 (0)3 (0)7 (0)7

O (n), :

for idx = 0 to N:
    array[array[idx] % 16] += 16 // add 1 to top four bits

, 7. , 16 7, . modulo , , , .

, :

  0    1    2    3    4    5    6    7    <- index
(0)7 (0)6 (1)2 (2)5 (0)3 (1)3 (1)7 (3)7

, int (array[X] / 16), X.

, . , , , , : -)

, , X, O (N). . , , N 8, , 8. ( , :

 0   1   2   3   4   5   6   7    <- index
(0) (0) (1) (2) (0) (1) (1) (3)

, , - , , 8.

  • 0 8 ( ).
  • 1 7. 0 x 3, .
  • 2 6. 1 x 1, (2,6).
  • 3 5. 2 x 1, (3,5).
  • 4, , . , 4s, , . , , , ( , m) 1 + 2 + 3 + ... + m-1. , m(m-1)/2.

, , , .

,

a b c d e f g h <- identifiers
7 6 2 5 3 3 7 7

:

(2,6) (3,5) (3,5)
(c,b) (e,d) (f,d) <- identifiers

8.

:

#include <stdio.h>

int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 4, 4, 4, 4};
#define SZ (sizeof(arr) / sizeof(*arr))

static void dumpArr (char *desc) {
    int i;
    printf ("%s:\n   Indexes:", desc);
    for (i = 0; i < SZ; i++) printf (" %2d", i);

    printf ("\n   Counts :");
    for (i = 0; i < SZ; i++) printf (" %2d", arr[i] / 100);

    printf ("\n   Values :");
    for (i = 0; i < SZ; i++) printf (" %2d", arr[i] % 100);

    puts ("\n=====\n");
}

. :

int main (void) {
    int i, j, find, prod;

    dumpArr ("Initial");

    // Sort array in O(1) - bucket sort.

    for (i = 0; i < SZ; i++) {
        arr[arr[i] % 100] += 100;
    }

, :

    dumpArr ("After bucket sort");

    // Now do pairings.

    find = 8;
    for (i = 0, j = find - i; i <= j; i++, j--) {
        if (i == j) {
            prod = (arr[i]/100) * (arr[i]/100-1) / 2;
            if (prod > 0) {
                printf ("(%d,%d) %d time(s)\n", i, j, prod);
            }
        } else {
            if ((j >= 0) && (j < SZ)) {
                prod = (arr[i]/100) * (arr[j]/100);
                if (prod > 0) {
                    printf ("(%d,%d) %d time(s)\n", i, j, prod);
                }
            }
        }
    }

    return 0;
}

:

Initial:
   Indexes:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
   Counts :  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   Values :  3  1  4  1  5  9  2  6  5  3  5  8  9  4  4  4  4
=====

After bucket sort:
   Indexes:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
   Counts :  0  2  1  2  5  3  1  0  1  2  0  0  0  0  0  0  0
   Values :  3  1  4  1  5  9  2  6  5  3  5  8  9  4  4  4  4
=====

(2,6) 1 time(s)
(3,5) 6 time(s)
(4,4) 10 time(s)

, , , .

+6

" " O (N) . , , . - .

: , ; , ; , :

  • , ,
  • , , ( , ).

"" , "" "" . , , , "1" "pointing" . . - , .

, 0 1. , reset 0 / 1. k=2 ( , k, ). k = 2, 4, 8,...

  • k .. 2k-1, "" , , - "1".
  • k .. 2k-1 2 .. k-1 2 .. k-1 reset .
  • 0 .. 2k-1 k .. 2k-1 k .. 2k-1 reset .

O (N) . . , 0 .. 2k-1 , k-1. , .

( X), .

+1

Sorting strings is n log n, but if you can assume that numbers are limited (and you can, because you are only interested in numbers that sum up to a specific value), you can use Radix sorting. Radix sorting takes O (kN) time, where "k" is the key length. This is constant in your case, so I think it's fair to say O (N).

As a rule, I would solve this using a hash, for example

http://41j.com/blog/2012/04/find-items-in-an-array-that-sum-to-15/

Although this, of course, is not a linear temporary solution.

0
source

More articles:


All Articles