0

I am trying to implement this problem in C++ using unordered map:

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

My solution:

class Solution {
 public:
  int singleNumber(vector<int>& nums) {
    std::unordered_map<int, int> umap;

    for (auto i = nums.begin(); i != nums.end(); i++) {
      umap[*i] = umap[*i] + 1;
    }

    for (auto i = umap.begin(); i != umap.end(); i++) {
      if (umap[*i] == 1) {
        return *i;
      }
    } 
  }
};

But unfortunately, it does not work. I get this error while compiling

Line 16: Char 17: fatal error: no viable overloaded operator[] for type 'std::unordered_map'
        if (umap[*i] == 1) {
            ~~~~^~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/unordered_map.h:973:7: note: candidate function not viable: no known conversion from 'std::pair' to 'const std::unordered_map, std::equal_to, std::allocator > >::key_type' (aka 'const int') for 1st argument
      operator[](const key_type& __k)
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/unordered_map.h:977:7: note: candidate function not viable: no known conversion from 'std::pair' to 'std::unordered_map, std::equal_to, std::allocator > >::key_type' (aka 'int') for 1st argument
      operator[](key_type&& __k)
      ^
1 error generated.

I cannot understand the error. Can anyone explain to me?

Improve this question
4
  • 1
    The unordered map would take up extra memory, though. So even if you get this to work, it wont satisfy the task given. Commented Apr 10, 2020 at 5:01
  • Could you implement it without using extra memory? -- You didn't follow the instructions when you used unordered_map. This is a question where if you don't know the trick, you may never solve it. Commented Apr 10, 2020 at 5:01
  • 1
    (umap[*i] == 1) is problamatic, you cannot compare it that way. use (i->first == 1) Commented Apr 10, 2020 at 5:03
  • 1
    Yes, as @PaulMcKenzie, the solution is actually very easy to implement once you think of the trick. Think of the mathematical properties of your input array. You have to read each value exactly once. Commented Apr 10, 2020 at 5:03

2 Answers 2

Reset to default
2

The relevant bit of the error is:

candidate function not viable: no known conversion from
   'std::pair' to
   'const std::unordered_map, std::equal_to, std::allocator > >::key_type'
       (aka 'const int')
for 1st argument operator[](const key_type& __k)

So what this means is then when using the subscript operator in umap[*i] == 1 the type of *i is some std::pair and the type that the operator expects is const int (look at the "aka").

That's because map iterators return an std::pair containing a reference to the key data and to the value data. You can get the value data easily just from the iterator without invoking the subscript operator:

if (i->second == 1)
  return i->first;

However, as stated in the comments you don't need any additional container to solve this puzzle. The constraint "Could you implement it without using extra memory?" is actually a hint to the solution. There is a mathematical property in a non-empty array of integers, where every element appears twice (!) except for one.

Also, I'd recommend using the variable name i for indexes and calling iterators it, but that's just personal preference.

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

1 Comment

The return statement also needs a change - it should be return i->first.
-2

You do not need std::unordered_map as std::unordered_set would be sufficient in this case:

std::unordered_set<int> set;
for( auto i : nums ) {
   auto p = set.insert( i );
   if( !p.second ) set.erase( p.first );
}

So logic is you try to insert a number, but if it was already there you remove it. Another benefit of this approach beside smaller memory footprint is that after loop you will have only one element in the set - one you need. So you do not need to iterate and search.

But proper solution is a trick that you should be aware about. It based of the properties of xor operation:

A xor A == 0 for any A
A xor 0 == A for any A

and because xor operation has commutative property as well:

A xor B xor A == A xor A xor B == 0 xor B == B

I think you now can get the idea of implementation without additional memory.

Improve this answer

5 Comments

@bitmask Spoiling? This is one of the useless puzzle sometimes asked in interview. You either know this trick or you do not, There is no value of guessing it like other programming puzzles often asked in the interview process. Duh. Like "how to find if single linked list has loops?" What the point of solving these puzzles?
@bitmask on top of that it is quite easy to find this answer by google geeksforgeeks.org/… so I gave OP the idea, not code.
@Slava Your link is really helpful as well as your answer.
Well, the question wasn't "how do I solve this puzzle?". It was "what is wrong with my unordered_map access?". I agree that this is a useless task in an interview. But it can be figured out in a homework setting where you have time to think about the problem. However, my complaint appears academic since OP seems to have accepted this non-answer.
@bitmask non-answer? You already provided what is wrong with OP code, I added to that providing one more efficient solution and gave a clue how to solve it properly - note I did not provide the code, only the way. I do not see benefit on solving "aha this the trick" problems on programming site. "Oh we are so clever we know how XOR works, we also know how to exchange 2 variable using it, do not give him clue" people

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.