CODEWITHSUNDEEP
c++performancealgorithmdata-structures
Ali
Ali

Reputation: 5476

Finding one and N elements removed from an unsorted array

I'm trying to implement an efficient solution for the problem, "Assume that in an unsorted array ranging from 1 to n, how would find if a number is removed and what if n numbers removed?"

Let me remark that I have no trouble with coding and I'm just here if someone can contribute the basic idea I have. I thought, storing all the elements in a hash table with index being the number itself (i.e hash(1)=1) and later on from 1 to n check hash table if the value exists. This would take O(n) time. I propose this of course if more than one number is removed. For the single value I would calculate sum of nums from 1 to n and subtract the array's sum.

However for the n number removed is there anything I can add for efficiency. (If negative numbers involved though my solution is to store like (O(12)=12=-12), basic chaining but automatically increasing the time complexity to O(2n). This problem actually is the reason I'm asking the question, but still any idea for the only-positives could help as well.)

Upvotes: 1

Views: 1153

Answers (4)

jxh
jxh

Reputation: 70472

If you are allowed some amount of pre-processing before scanning the list, then you can have a pre-processed data structure that maintains a doubly linked list of the numbers you expect to have, and you remove elements from that linked list as you scan the sequence of numbers in the input. Whatever is left in the doubly linked list is what is missing from the input.

The access to members in the doubly linked list is O(1) because the nodes of the list were actually created from an array. The removal is O(1) from a doubly linked list. So the missing numbers are found in a single pass of the input. The complexity is O(i+m), with i the size of the input, and m is how many numbers are missing.

The code below creates the doubly linked list based on the starting value and ending value of the sequence from which the input will be compared against. Using it would be like:

Tracker t(0, 10);
int i;
while (std::cin >> i) t.remove(i);
t.report();

Enjoy!

struct Node {
    static int index;
    static int stop;
    int num;
    struct Node *next;
    struct Node *prev;
    Node () : num(index++), next(0), prev(0) {
        if (index <= stop) next = this + 1;
        if (index > 0) prev = this - 1;
    }
};

struct Tracker {
    int start;
    int finish;
    Node *nodes;
    Tracker (int s, int f) : start(s), finish(f) {
        if (finish < start) throw 0;
        Node::index = start;
        Node::stop = finish + 1;
        nodes = new Node[finish - start + 2];
        nodes[finish - start + 1].next = nodes;
        nodes[0].prev = &nodes[finish - start + 1];
    }
    ~Tracker () { delete[] nodes; }
    void remove (int i) {
        Node *n = &nodes[i - start];
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }
    void report () {
        Node *n = nodes[finish - start + 1].next;
        if (n->next == n) std::cout << "all there" << std::endl;
        else do {
            std::cout << "missing: " << n->num << std::endl;
            n = n->next;
        } while (n != &nodes[finish - start + 1]);
    }
};

Upvotes: 0

Mark
Mark

Reputation: 1100

Your solution is the best, you can't have a better complexity then O(N) ( O(2N) is actually O(N)) it does not matter if you have negative numbers if you have a good function to map your value. For numbers I would suggest a number that is lower than n and to be a prime number, let's call that number P. f(x) = x%P ( for value x the key would be x%P) for P = 9913 we should have: hash[10] = 10, 9923,-9903 and all the numbers that have (their value)%P equals with 10 from your array. You can use a linked list or a vector to get rid off the collision. for a number Y you should store Y at the index Y%P, and with one traversal for i in range(1..n) you should look in to the hash table at the pozition i%P for i( basically O(1) complexity for a query) and that's it. hope it helped. Sorry for my English :(

Upvotes: 2

JustinDanielson
JustinDanielson

Reputation: 3185

For your solution using hash tables, you don't need a hash table. If you know the values are from 1 to n, you can use an array of booleans of n size. Simply iterate through the array of values, use the value to index into the array of booleans and set the value at that location to True. Afterwards, iterate through the array of booleans and look for False values to see which have been removed. You could use less space, if you used an array of ints and set the True/False values at the bit locations. This is a counting sort

for i=0 to n:
    bools[values[i]] = True:
for i=0 to n:
    if(bools[i] == False):
        print("%d is missing".format(i))

If you are given negative values, first pass through the array and find the lowest value. If it's -10, add 10 to every value so -10 will go to location 0. Then use the above logic and when you find negative values, subtract 10.

"Assume that in an unsorted array ranging from 1 to n, how would find if a number is removed and what if n numbers removed?"

If n numbers were removed, the array would contain no values.

Upvotes: 0

Kerwong
Kerwong

Reputation: 428

I think we can define more than one data structures for this problem. For example, define INT del = 0; and define a del_list, the node of del_list can record the address and number; we have an unsorted array A, if we delete a number from this array A, add the deleted number into del_list and del++; so we can know how many numbers have been deleted, and which they are. Besides, I think there are more efficient way to solve this problem if we encode, but now I've no idea :P.. I hope this answer would help you.

Upvotes: 0

Related Questions