This solution is sub-optimal in terms of space complexity because creating a set uses extra memory. While it should be possible to do better using bitwise operators, I can’t really wrap my head around the correct way to do so right now.
Assumes A is a non-empty integer list where
each item occurs thrice except for one.
return (3 * sum(set(A)) - sum(A)) // 2
You need some kind of state machine to represent all the possible states.
That is, if the problem stated that all elements appears exactly k (k > 1) times and only one element appears p (p > 1, p mod k != 0)times, then you need to have a state machine to represent all k states.
A state machine is like a counter increment each time there is a change of state. Suppose there are 0 to k - 1 states. When an element appear k times, then the state machine resets the state back to state 0. Therefore, you need a mask depending on the binary form of k = k_m, k_m-1, … , k_1. The mask is used to prevent from counting over k. Then you can retrieve the element that appears exactly p times from the state variable k_p. This is possible because all other elements appears exactly k times, when its k times, the variable state k_1.
Then you have to figure how to change the variables in each state when there’s a 1 or a 0 for each input.
I’d like to point something out. These types of coding problems are typical in technical interviews at big-name tech companies and also in competitive coding. The stated difficulty should be interpreted in this context.
For this particular set of problems, finding an optimal solution (one in the required time/space complexity) is not “easy”. It requires familiarity with bit manipulation, which is considered a pretty advanced and non-intuitive topic in Computer Science.
So if you look at this problem and go “There is no way I could solve this… and it’s supposed to be easy?!”, then this is what I would suggest:
Forget about optimal solutions and complexity all together. Just try to find a solution as opposed to the best solution. For most problems, it is entirely possible to find a solution that uses only basic programming concepts such as loops, lists, dicts, etc. And even if you ultimately fail, you will learn a lot just by trying.
Once you have a working solution, go ahead and Google the problem. Read through other peoples solutions and discussion of the problem. Try to understand what the code is doing and what the high-level concepts are. Just as an example, let’s say people are talking about Quicksort in their solutions. Never heard of it? Try searching on Youtube. There’s a whole bunch of excellent videos from top-tier schools out there.
Use your newfound knowledge to improve your own solution.
Okay, so maybe this sounds like a lot of work. And it is. But you can get a lot out it, in terms of both skills and confidence as a programmer. So… just do it! Or at least try.
Yes, having a naive non optimal solution is better than none. Trying to use basics structures is a good start.
Yes, be flexible and open to new ideas and suggestion. Sometimes, people give a well written comment in a form of a tutorial. Other resources also helps in learning.
There is always some point in time to you have to start to learn. Why not start now and start early! You can do it. Takes a lot of practice and study to build confidence. The confidence will come slowly but eventually.