CodingExcercises/DuplicateRowsInBinaryMatrix.cpp at master · madhu90/CodingExcercises · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <vector>
#include <unordered_map>

// QUESTION: https://www.techiedelight.com/find-duplicate-rows-binary-matrix/


class DuplicateRowFinder
{
public:
	void compute(const std::vector<std::vector<int>>& vec)
	{
		std::unordered_map<int, bool> map;

		for (int i = 0; i < vec.size(); ++i)
		{
			int num = 0;

			// Decimal representation of number
			for (int j = vec[i].size() - 1; j >= 0; --j)
			{
				int exp = std::pow(2, vec[i].size() - 1 - j);
				num += vec[i][j] * exp;
			}

			if (map.find(num) != map.end())
			{
				std::cout << "Duplicate row found at index " << i + 1 << std::endl;
			} else {
				map[num] = true;
			}
		}
	}
};

class BinaryTrie
{
private:
	BinaryTrie* character[2];
	bool isLeaf;

private:
	void deleteHelper(BinaryTrie*& curr)
	{
		if (curr)
		{
			deleteHelper(curr->character[0]);
			deleteHelper(curr->character[1]);
			delete curr;
			curr = nullptr;
		}
	}

	bool insert(const std::vector<int>& vec)
	{
		bool exists = true;
		BinaryTrie* curr = this;

		for (size_t i = 0; i < vec.size(); ++i)
		{
			if (curr->character[vec[i]] == nullptr)
			{
				exists = false;
				curr->character[vec[i]] = new BinaryTrie();
			}

			curr = curr->character[vec[i]];
		}

		return exists;
	}

public:
	BinaryTrie()
	{
		character[0] = nullptr;
		character[1] = nullptr;
		isLeaf = false;
	}

	~BinaryTrie()
	{
		if (character[0])
			deleteHelper(character[0]);

		if (character[1])
			deleteHelper(character[1]);
	}


	void isThereDuplicate(const std::vector<std::vector<int>>& mat)
	{
		for (size_t i = 0; i < mat.size(); ++i)
		{
			if (insert(mat[i]))
			{
				std::cout << "Duplicate row found at index " << i + 1 << std::endl;
			}
		}
	}
};

int main()
{
	std::vector<std::vector<int>> mat{
		{1, 0, 0, 1, 0},
		{0, 1, 1, 0, 0},
		{1, 0, 0, 1, 0},
		{0, 0, 1, 1, 0},
		{0, 1, 1, 0, 0}
	};

	BinaryTrie obj;
	obj.isThereDuplicate(mat);
	DuplicateRowFinder obj1;
	obj1.compute(mat);
	return 0;
}