CareerCup

Clarify.
I just have to pair socks of same color right ?
Problem can be reduced to sorting of array containing 0 and 1.

Then do another parse through the sorted array. With start index and end index. Start pairing start and end. Stop when pairing is not possible.

We may need to keep another array with the indexes of the socks

Clarify the question, please.
Because, if the question is: is it possible to pair them (Put all the white sockets in the bucket#1 and all the black sockets in the bucket#2)? Then:
- if the number of socks is not paired {number} % 2 != 0 - then the answer is immediately False.
- if the number is paired - we need to go through the list of the socks (could be both directional iteration) and put the socks on 2 different buckets. Once the number of socks (black or white) becomes bigger than half of all the socks - the answer is False.
- if the balancing of both lists works - then we will end the iteration with the balanced number of socks in both buckets.

If we need to differentiate by "left" and "right" for each color - then the flow is different.

Like other comments, please clarify the problem and provide additional details. Thank you.

Works for any number of sock colors. O(N) time, O(K) space, where K is number of colors:

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

using namespace std;

enum Sock {
	black = 0,
	white = 1
};

vector<pair<Sock, Sock>> Pair(vector<Sock> const &a)
{
	vector<pair<Sock, Sock>> out;
	unordered_set<Sock, hash<int>> part1;
	for (auto &s : a) {
		if (part1.find(s) != part1.end()) {
			out.push_back(pair<Sock, Sock>(s, s));
			part1.erase(s);
		} else {
			part1.insert(s);
		}
	}
	cout << (part1.empty() ? "all paired\n" : "not all paired\n");
	return out;
}

int main()
{
	vector<pair<Sock, Sock>> pairs = Pair({black, white, white, black, white, black, white, black});
	for (auto &p : pairs) {
		cout << p.first << ", " << p.second << "\n";
	}
}