Find a repeating element in an array in single for loop

Question

Well hello there suppose you are given an array [1,5,3,6,7,3,67,54] in which every element comes only once except one element which is 3 in this case. The task at hand is to find this element and you are allowed to only use one for loop which is equal to the size of the array.

PS: you might suggest to use hash map but in that case after the traversal of array is over you would need to traverse the hash map to find which key has the value 2 which makes it 2 for loops and is not allowed.

How would you do it ?

Show us what you tried so far! Why would you need to iterate through the hash-map? — chtz, Jul 16 '17 at 16:03
@KostasRim Sorting is at least as expensive as scanning an array, which makes your solution worse than 2 loops. — Scott Hunter, Jul 16 '17 at 16:09
by the way this looks like a duplicate: https://stackoverflow.com/q/44637670/1632887 — seleciii44, Jul 16 '17 at 16:28
@chtz hello sir i was asked this in an interview and i used map from cpp to store the count of the numbers but interviewer said that would make it 2 loops ...same goes for using sets — shourabh, Jul 16 '17 at 16:43

seleciii44 · Answer 1 · 2017-07-17T18:22:31.580

4

Hash map can solve your problem. Actually, it has more than you need. Use an unordered_set. Traverse the array, if a value does not exist in the set insert it; otherwise you have found your duplicate value.

--EDIT--

Ok, one of us does not understand the other, that's for sure. Depending on what i understand from your question, below is a sample solution using a set. If you think i still misunderstand, then please give more details about your problem.

#include<vector>
#include<iostream>
#include<unordered_set>

bool repeating(const std::vector<int> &vec, int &repeatingValue)
{
    std::unordered_set<int> set;
    for(auto x: vec)
    {
        if(set.count(x))
        {
            repeatingValue = x;
            return true;
        }
        set.insert(x);
    }
    return false;
}

int main()
{
    std::vector<int> v{1,5,3,6,7,3,67,54};

    int repeatingValue;
    if(repeating(v, repeatingValue))
        std::cout<<repeatingValue<<std::endl;
    else
        std::cout<<"No repeating value detected!" << std::endl;

    return 0;
}

edited Jul 17 '17 at 18:22

answered Jul 16 '17 at 16:23

seleciii44

1,529
3
13
26

please read the side note it says only use one for loop if you check every time if the value is present in the set you are using another for loop to traverse the set – shourabh Jul 16 '17 at 16:39
@shourabh you don't need to traverse twice. just check if a value exists in the set before you insert it. – seleciii44 Jul 16 '17 at 16:44
tell me how you check if value exists ? By traversing all possible set elements right? – shourabh Jul 16 '17 at 16:46
1

of course not! hash relates a key to an index. so checking means you just go to the index and look if the value is there – seleciii44 Jul 16 '17 at 16:51
Probably what the interviewer is looking for, but depending on how the hash table is implemented there may be loops involved in handling collisions. – user4581301 Jul 16 '17 at 17:10
@user4581301 that's right. I did not claim that. I was just trying to fix a misunderstanding. – seleciii44 Jul 16 '17 at 17:20
One other alternative, since there don't seem to be any other limitations in the question, you could skip the hash and make an infinitely large boolean array. – user4581301 Jul 16 '17 at 20:55
@seleciii44 i dont think you understand the problem i am presenting.. even if you manage to put map[3] = 2 in the hashmap , there will be other keys having values 1 like map[1] = 1 , map[5] = 1, map[6] = 1 etc, now to know which key has the value 2 you need to scan all the key value pairs this will account for another loop thats what i am trying to say – shourabh Jul 17 '17 at 16:32

Find a repeating element in an array in single for loop

1 Answers1