Find a repeating element in an array in single for loop [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

Want to improve this question? Guide the asker to update the question so it focuses on a single, specific problem. Narrowing the question will help others answer the question concisely. You may edit the question if you feel you can improve it yourself. If edited, the question will be reviewed and might be reopened.

Closed 8 years ago.

Improve this 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
– chtz, Commented Jul 16, 2017 at 16:03
@KostasRim Sorting is at least as expensive as scanning an array, which makes your solution worse than 2 loops. — Scott Hunter
– Scott Hunter, Commented Jul 16, 2017 at 16:09
by the way this looks like a duplicate: stackoverflow.com/q/44637670/1632887 — seleciii44
– seleciii44, Commented Jul 16, 2017 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
– shourabh, Commented Jul 16, 2017 at 16:43

seleciii44 · Accepted Answer · 2017-07-17 18:22:31Z

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, 2017 at 18:22

answered Jul 16, 2017 at 16:23

seleciii44

1,5793 gold badges13 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

shourabh Over a year ago

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

seleciii44 Over a year ago

@shourabh you don't need to traverse twice. just check if a value exists in the set before you insert it.

shourabh Over a year ago

tell me how you check if value exists ? By traversing all possible set elements right?

seleciii44 Over a year ago

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

user4581301 Over a year ago

Probably what the interviewer is looking for, but depending on how the hash table is implemented there may be loops involved in handling collisions.

|

Collectives™ on Stack Overflow

Find a repeating element in an array in single for loop [closed]

1 Answer 1

8 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Linked

Related