Find duplicate rows in a binary matrix
Here given code implementation process.
/*
C++ program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
#include<iostream>
#define R 8
#define C 7
using namespace std;
class Node
{
public:
//Indicates end of string
bool end;
Node **children;
Node()
{
this->end = false;
this->children = new Node*[2];
}
};
class TrieTree
{
public: Node *root;
TrieTree()
{
this->root = new Node();
}
bool insert(int row[], int cols)
{
//This variable are used to task find the index location of character
int index = 0;
//get the root node
Node *head = this->root;
bool status = true;
for (int level = 0; level < cols; level++)
{
//Get the index
index = row[level];
if (head->children[index] == NULL)
{
//When need to add new Node
head->children[index] = new Node();
//when modified trie tree
status = false;
}
head = head->children[index];
}
if (head != NULL)
{
//indicates end of string
head->end = true;
}
return status;
}
void display(int matrix[R][C], int rows, int cols)
{
for (int i = 0; i < rows; ++i)
{
cout << " Row [" << i << "] : ";
for (int j = 0; j < cols; ++j)
{
cout << " " << matrix[i][j];
}
cout << "\n";
}
cout << "\n";
}
};
int main()
{
//Make object
TrieTree obj = TrieTree();
int matrix[R][C] = {
{
1,
0,
1,
1,
0,
1,
1
},
{
0,
0,
0,
1,
0,
1,
1
},
{
1,
0,
1,
1,
0,
1,
1
},
{
0,
0,
0,
0,
0,
0,
0
},
{
1,
0,
1,
1,
0,
1,
1
},
{
0,
0,
0,
0,
0,
0,
0
},
{
1,
0,
0,
1,
0,
1,
1
},
{
0,
0,
0,
1,
0,
1,
1
},
};
bool status = false;
obj.display(matrix, R, C);
for (int i = 0; i < R; i++)
{
//pass row matrix[i]
status = obj.insert(matrix[i], C);
if (status == true)
{
cout << " Row "<<i<<" are Duplicate\n";
}
}
return 0;
}
Output
Row [0] : 1 0 1 1 0 1 1
Row [1] : 0 0 0 1 0 1 1
Row [2] : 1 0 1 1 0 1 1
Row [3] : 0 0 0 0 0 0 0
Row [4] : 1 0 1 1 0 1 1
Row [5] : 0 0 0 0 0 0 0
Row [6] : 1 0 0 1 0 1 1
Row [7] : 0 0 0 1 0 1 1
Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate
/*
C# program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
using System;
public class Node
{
//Indicates end of string
public Boolean end;
public Node[] children;
public
Node()
{
end = false;
children = new Node[2];
}
}
public class TrieTree
{
public Node root;
public TrieTree()
{
root = new Node();
}
public Boolean insert(int [,]matrix,int row, int cols)
{
//This variable are used to task find the index location of character
int index = 0;
//get the root node
Node head = root;
Boolean status = true;
for (int level = 0; level < cols; level++)
{
//Get the index
index = matrix[row,level];
if (head.children[index] == null)
{
//When need to add new Node
head.children[index] = new Node();
//when modified trie tree
status = false;
}
head = head.children[index];
}
if (head != null)
{
//indicates end of string
head.end = true;
}
return status;
}
public void display(int[,] matrix, int rows, int cols)
{
for (int i = 0; i < rows; i++)
{
Console.Write(" Row [" + i + "] : ");
for (int j = 0; j < cols; j++)
{
Console.Write(" " + matrix[i,j]);
}
Console.Write("\n");
}
Console.Write("\n");
}
public static void Main(String[] args)
{
//Make object
TrieTree obj = new TrieTree();
int [,] matrix = {
{1,0,1,1,0,1,1},
{0,0,0,1,0,1,1},
{1,0,1,1,0,1,1},
{0,0,0,0,0,0,0},
{1,0,1,1,0,1,1},
{0,0,0,0,0,0,0},
{1,0,0,1,0,1,1},
{0,0,0,1,0,1,1}
};
Boolean status = false;
//Get the size of matrix
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);
obj.display(matrix, rows, cols);
for (int i = 0; i < rows; i++)
{
//pass row matrix[i]
status = obj.insert(matrix,i, cols);
if (status == true)
{
Console.Write(" Row " + i + " are Duplicate\n");
}
}
}
}
Output
Row [0] : 1 0 1 1 0 1 1
Row [1] : 0 0 0 1 0 1 1
Row [2] : 1 0 1 1 0 1 1
Row [3] : 0 0 0 0 0 0 0
Row [4] : 1 0 1 1 0 1 1
Row [5] : 0 0 0 0 0 0 0
Row [6] : 1 0 0 1 0 1 1
Row [7] : 0 0 0 1 0 1 1
Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate
/*
Java program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
class Node
{
//Indicates end of string
public boolean end;
public Node[] children;
public Node()
{
end = false;
children = new Node[2];
}
}
public class TrieTree
{
public Node root;
public TrieTree()
{
root = new Node();
}
public boolean insert(int []row,int cols)
{
//This variable are used to task find the index location of character
int index = 0;
//get the root node
Node head = root;
boolean status = true;
for (int level = 0; level < cols; level++)
{
//Get the index
index = row[level];
if (head.children[index] == null)
{
//When need to add new Node
head.children[index] = new Node();
//when modified trie tree
status = false;
}
head = head.children[index];
}
if (head != null)
{
//indicates end of string
head.end = true;
}
return status;
}
public void display(int[][] matrix,int rows,int cols)
{
for (int i = 0; i < rows; ++i)
{
System.out.print(" Row [" + i + "] : ");
for (int j = 0; j < cols; ++j)
{
System.out.print(" " + matrix[i][j]);
}
System.out.print("\n");
}
System.out.print("\n");
}
public static void main(String[] args)
{
//Make object
TrieTree obj = new TrieTree();
int matrix[][] =
{
{1,0,1,1,0,1,1},
{0,0,0,1,0,1,1},
{1,0,1,1,0,1,1},
{0,0,0,0,0,0,0},
{1,0,1,1,0,1,1},
{0,0,0,0,0,0,0},
{1,0,0,1,0,1,1},
{0,0,0,1,0,1,1},
};
boolean status = false;
//Get the size of matrix
int rows = matrix.length;
int cols = matrix[0].length;
obj.display(matrix,rows,cols);
for (int i = 0; i < rows; i++)
{
//pass row matrix[i]
status = obj.insert(matrix[i],cols);
if (status == true)
{
System.out.print(" Row "+i+" are Duplicate\n");
}
}
}
}
Output
Row [0] : 1 0 1 1 0 1 1
Row [1] : 0 0 0 1 0 1 1
Row [2] : 1 0 1 1 0 1 1
Row [3] : 0 0 0 0 0 0 0
Row [4] : 1 0 1 1 0 1 1
Row [5] : 0 0 0 0 0 0 0
Row [6] : 1 0 0 1 0 1 1
Row [7] : 0 0 0 1 0 1 1
Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate
<?php
/*
Php program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
class Node
{
//Indicates end of string
public $end;
public $children;
function __construct()
{
$this->end = false;
$this->children = array_fill(0, 2, null);
}
}
class TrieTree
{
public $root;
function __construct()
{
$this->root = new Node();
}
public function insert( & $row, $cols)
{
//This variable are used to task find the index location of character
$index = 0;
//get the root node
$head = $this->root;
$status = true;
for ($level = 0; $level < $cols; $level++)
{
//Get the index
$index = $row[$level];
if ($head->children[$index] == null)
{
//When need to add new Node
$head->children[$index] = new Node();
//when modified trie tree
$status = false;
}
$head = $head->children[$index];
}
if ($head != null)
{
//indicates end of string
$head->end = true;
}
return $status;
}
public function display( & $matrix, $rows, $cols)
{
for ($i = 0; $i < $rows; ++$i)
{
echo(" Row [". $i ."] : ");
for ($j = 0; $j < $cols; ++$j)
{
echo(" ". $matrix[$i][$j]);
}
echo("\n");
}
echo("\n");
}
}
function main()
{
//Make object
$obj = new TrieTree();
$matrix = array(array(1, 0, 1, 1, 0, 1, 1),
array(0, 0, 0, 1, 0, 1, 1),
array(1, 0, 1, 1, 0, 1, 1),
array(0, 0, 0, 0, 0, 0, 0),
array(1, 0, 1, 1, 0, 1, 1),
array(0, 0, 0, 0, 0, 0, 0),
array(1, 0, 0, 1, 0, 1, 1),
array(0, 0, 0, 1, 0, 1, 1));
$status = false;
//Get the size of matrix
$rows = count($matrix);
$cols = count($matrix[0]);
$obj->display($matrix, $rows, $cols);
for ($i = 0; $i < $rows; $i++)
{
//pass row matrix[i]
$status = $obj->insert($matrix[$i], $cols);
if ($status == true)
{
echo(" Row ". $i ." are Duplicate\n");
}
}
}
main();
Output
Row [0] : 1 0 1 1 0 1 1
Row [1] : 0 0 0 1 0 1 1
Row [2] : 1 0 1 1 0 1 1
Row [3] : 0 0 0 0 0 0 0
Row [4] : 1 0 1 1 0 1 1
Row [5] : 0 0 0 0 0 0 0
Row [6] : 1 0 0 1 0 1 1
Row [7] : 0 0 0 1 0 1 1
Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate
/*
Node Js program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
class Node
{
//Indicates end of string
constructor()
{
this.end = false;
this.children = Array(2).fill(null);
}
}
class TrieTree
{
constructor()
{
this.root = new Node();
}
insert(row, cols)
{
//This variable are used to task find the index location of character
var index = 0;
//get the root node
var head = this.root;
var status = true;
for (var level = 0; level < cols; level++)
{
//Get the index
index = row[level];
if (head.children[index] == null)
{
//When need to add new Node
head.children[index] = new Node();
//when modified trie tree
status = false;
}
head = head.children[index];
}
if (head != null)
{
//indicates end of string
head.end = true;
}
return status;
}
display(matrix, rows, cols)
{
for (var i = 0; i < rows; ++i)
{
process.stdout.write(" Row [" + i + "] : ");
for (var j = 0; j < cols; ++j)
{
process.stdout.write(" " + matrix[i][j]);
}
process.stdout.write("\n");
}
process.stdout.write("\n");
}
}
function main(args)
{
//Make object
var obj = new TrieTree();
var matrix = [
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1]
];
var status = false;
//Get the size of matrix
var rows = matrix.length;
var cols = matrix[0].length;
obj.display(matrix, rows, cols);
for (var i = 0; i < rows; i++)
{
//pass row matrix[i]
status = obj.insert(matrix[i], cols);
if (status == true)
{
process.stdout.write(" Row " + i + " are Duplicate\n");
}
}
}
main();
Output
Row [0] : 1 0 1 1 0 1 1
Row [1] : 0 0 0 1 0 1 1
Row [2] : 1 0 1 1 0 1 1
Row [3] : 0 0 0 0 0 0 0
Row [4] : 1 0 1 1 0 1 1
Row [5] : 0 0 0 0 0 0 0
Row [6] : 1 0 0 1 0 1 1
Row [7] : 0 0 0 1 0 1 1
Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate
#
# Python 3 program
# Find duplicate rows in a binary matrix
# Using Trie Tree
class Node :
# Indicates end of string
def __init__(self) :
self.end = False
self.children = [None] * 2
class TrieTree :
def __init__(self) :
self.root = Node()
def insert(self, row, cols) :
# This variable are used to task find the index location of character
index = 0
# get the root node
head = self.root
status = True
level = 0
while (level < cols) :
# Get the index
index = row[level]
if (head.children[index] == None) :
# When need to add new Node
head.children[index] = Node()
# when modified trie tree
status = False
head = head.children[index]
level += 1
if (head != None) :
# indicates end of string
head.end = True
return status
def display(self, matrix, rows, cols) :
i = 0
while (i < rows) :
print(" Row [", i ,"] : ", end = "")
j = 0
while (j < cols) :
print(" ", matrix[i][j], end = "")
j += 1
print("\n", end = "")
i += 1
print("\n", end = "")
def main() :
# Make object
obj = TrieTree()
matrix = [
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1]
]
status = False
# Get the size of matrix
rows = len(matrix)
cols = len(matrix[0])
obj.display(matrix, rows, cols)
i = 0
while (i < rows) :
# pass row matrix[i]
status = obj.insert(matrix[i], cols)
if (status == True) :
print(" Row ", i ," are Duplicate\n", end = "")
i += 1
if __name__ == "__main__": main()
Output
Row [ 0 ] : 1 0 1 1 0 1 1
Row [ 1 ] : 0 0 0 1 0 1 1
Row [ 2 ] : 1 0 1 1 0 1 1
Row [ 3 ] : 0 0 0 0 0 0 0
Row [ 4 ] : 1 0 1 1 0 1 1
Row [ 5 ] : 0 0 0 0 0 0 0
Row [ 6 ] : 1 0 0 1 0 1 1
Row [ 7 ] : 0 0 0 1 0 1 1
Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate
# Ruby program
# Find duplicate rows in a binary matrix
# Using Trie Tree
class Node
# Define the accessor and reader of class Node
attr_reader :last, :children
attr_accessor :last, :children
# Indicates end of string
def initialize()
@last = false
@children = Array.new(2) {nil}
end
end
class TrieTree
# Define the accessor and reader of class TrieTree
attr_reader :root
attr_accessor :root
def initialize()
@root = Node.new()
end
def insert(row, cols)
# This variable are used to task find the index location of character
index = 0
# get the root node
head = @root
status = true
level = 0
while (level < cols)
# Get the index
index = row[level]
if (head.children[index] == nil)
# When need to add new Node
head.children[index] = Node.new()
# when modified trie tree
status = false
end
head = head.children[index]
level += 1
end
if (head != nil)
# indicates end of string
head.last = true
end
return status
end
def display(matrix, rows, cols)
i = 0
while (i < rows)
print(" Row [", i ,"] :")
j = 0
while (j < cols)
print(" ", matrix[i][j])
j += 1
end
print("\n")
i += 1
end
print("\n")
end
end
def main()
# Make object
obj = TrieTree.new()
matrix = [
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1]
]
status = false
# Get the size of matrix
rows = matrix.length
cols = matrix[0].length
obj.display(matrix, rows, cols)
i = 0
while (i < rows)
# pass row matrix[i]
status = obj.insert(matrix[i], cols)
if (status == true)
print(" Row ", i ," are Duplicate\n")
end
i += 1
end
end
main()
Output
Row [0] : 1 0 1 1 0 1 1
Row [1] : 0 0 0 1 0 1 1
Row [2] : 1 0 1 1 0 1 1
Row [3] : 0 0 0 0 0 0 0
Row [4] : 1 0 1 1 0 1 1
Row [5] : 0 0 0 0 0 0 0
Row [6] : 1 0 0 1 0 1 1
Row [7] : 0 0 0 1 0 1 1
Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate
/*
Scala program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
class Node(var last: Boolean,
var children: Array[Node])
{
//Indicates end of string
def this()
{
this(false,Array.fill[Node](2)(null));
}
}
class TrieTree(var root: Node)
{
def this()
{
this(new Node());
}
def insert(row: Array[Int], cols: Int): Boolean = {
//This variable are used to task find the index location of character
var index: Int = 0;
//get the root node
var head: Node = root;
var status: Boolean = true;
var level: Int = 0;
while (level < cols)
{
//Get the index
index = row(level);
if (head.children(index) == null)
{
//When need to add new Node
head.children(index) = new Node();
//when modified trie tree
status = false;
}
head = head.children(index);
level += 1;
}
if (head != null)
{
//indicates end of string
head.last = true;
}
return status;
}
def display(matrix: Array[Array[Int]], rows: Int, cols: Int): Unit = {
var i: Int = 0;
while (i < rows)
{
print(" Row [" + i + "] : ");
var j: Int = 0;
while (j < cols)
{
print(" " + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object
var obj: TrieTree = new TrieTree();
var matrix: Array[Array[Int]] = Array(
Array(1, 0, 1, 1, 0, 1, 1),
Array(0, 0, 0, 1, 0, 1, 1),
Array(1, 0, 1, 1, 0, 1, 1),
Array(0, 0, 0, 0, 0, 0, 0),
Array(1, 0, 1, 1, 0, 1, 1),
Array(0, 0, 0, 0, 0, 0, 0),
Array(1, 0, 0, 1, 0, 1, 1),
Array(0, 0, 0, 1, 0, 1, 1));
var status: Boolean = false;
//Get the size of matrix
var rows: Int = matrix.length;
var cols: Int = matrix(0).length;
obj.display(matrix, rows, cols);
var i: Int = 0;
while (i < rows)
{
//pass row matrix[i]
status = obj.insert(matrix(i), cols);
if (status == true)
{
print(" Row " + i + " are Duplicate\n");
}
i += 1;
}
}
}
Output
Row [0] : 1 0 1 1 0 1 1
Row [1] : 0 0 0 1 0 1 1
Row [2] : 1 0 1 1 0 1 1
Row [3] : 0 0 0 0 0 0 0
Row [4] : 1 0 1 1 0 1 1
Row [5] : 0 0 0 0 0 0 0
Row [6] : 1 0 0 1 0 1 1
Row [7] : 0 0 0 1 0 1 1
Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate
/*
Swift program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
class Node
{
//Indicates end of string
var last: Bool;
var children: [Node?]=[Node]();
init()
{
self.last = false;
var i = 0;
while (i<2) {
self.children.append(nil);
i+=1;
}
}
}
class TrieTree
{
var root: Node? ;
init()
{
self.root = Node();
}
func insert(_ row: [Int], _ cols: Int) -> Bool
{
//This variable are used to task find the index location of character
var index: Int = 0;
//get the root node
var head: Node? = self.root;
var status: Bool = true;
var level: Int = 0;
while (level < cols)
{
//Get the index
index = row[level];
if (head!.children[index] == nil)
{
//When need to add new Node
head!.children[index] = Node();
//when modified trie tree
status = false;
}
head = head!.children[index];
level += 1;
}
if (head != nil)
{
//indicates end of string
head!.last = true;
}
return status;
}
func display(_ matrix: [
[Int]
], _ rows: Int, _ cols: Int)
{
var i: Int = 0;
while (i < rows)
{
print(" Row [", i ,"] : ", terminator: "");
var j: Int = 0;
while (j < cols)
{
print(" ", matrix[i][j], terminator: "");
j += 1;
}
print("\n", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main()
{
//Make object
let obj: TrieTree = TrieTree();
var matrix : [[Int]] = [
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1]
];
var status: Bool = false;
//Get the size of matrix
let rows: Int = matrix.count;
let cols: Int = matrix[0].count;
obj.display(matrix, rows, cols);
var i: Int = 0;
while (i < rows)
{
//pass row matrix[i]
status = obj.insert(matrix[i], cols);
if (status == true)
{
print(" Row ", i ," are Duplicate\n", terminator: "");
}
i += 1;
}
}
main();
Output
Row [ 0 ] : 1 0 1 1 0 1 1
Row [ 1 ] : 0 0 0 1 0 1 1
Row [ 2 ] : 1 0 1 1 0 1 1
Row [ 3 ] : 0 0 0 0 0 0 0
Row [ 4 ] : 1 0 1 1 0 1 1
Row [ 5 ] : 0 0 0 0 0 0 0
Row [ 6 ] : 1 0 0 1 0 1 1
Row [ 7 ] : 0 0 0 1 0 1 1
Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment