Count of binary strings that does not contain Arc intersection
The problem is to count the number of binary strings in an array such that they do not contain any intersection in the form of arcs. An arc intersection occurs when there are consecutive identical elements in the binary string. For example, in the string "1100011000", there are three arc intersections: "00", "11", and "000". We need to count the binary strings that do not have any such arc intersections.
Problem Statement
Given an array of binary strings, count the number of binary strings that do not contain any arc intersection.
Example
Consider the following example:
Input:
arr = ["1100011000","1010", "001111","101101", "101"]
Output:
3
Explanation:
- The first binary string "1100011000" has two arc intersections "00" and "11".
- The second binary string "1010" has an arc intersection "11".
- The third binary string "001111" has no arc intersections.
- The fourth binary string "101101" has an arc intersection "11".
- The fifth binary string "101" has no arc intersections.
So, there are 3 binary strings that do not contain any arc intersections.
Idea to Solve the Problem
To solve the problem, we can use a stack to check for arc intersections in each binary string. We iterate through the binary string character by character, and for each character, we check if it is equal to the top element of the stack. If it is, it means there is an arc intersection, and we pop the top element from the stack. If it is not equal to the top element, we push it onto the stack. At the end, if the stack is empty, it means there are no arc intersections in the binary string.
Pseudocode
Function isIntersect(text):
n = length of text
If n is 0:
Return false
Create an empty stack called path
for i from 0 to n-1:
If path is empty:
Push text[i] onto path
Else:
If path.peek() is equal to text[i]:
Pop the top element from path
Else:
Push text[i] onto path
If path is empty:
Return false
Else:
Return true
Function nonArcIntersection(arr, n):
count = 0
For i from 0 to n-1:
If isIntersect(arr[i]) is false:
Increment count
Print count
Algorithm
- Create a class called
Intersection
. - Define a function called
isIntersect
that takes a stringtext
as a parameter and returns a boolean value. - Get the length
n
of the stringtext
. - If
n
is 0, return false as an empty string cannot have any arc intersections. - Create an empty stack called
path
. - Iterate through the characters of the string from index 0 to n-1.
- For each character, do the following:
a. If the stack
path
is empty, push the character onto the stack. b. If the stack is not empty, check if the character is equal to the top element of the stack. If it is, it means there is an arc intersection, so pop the top element from the stack. c. If the character is not equal to the top element of the stack, push the character onto the stack. - After iterating through all characters, check if the stack
path
is empty. If it is, return false as there are no arc intersections. Otherwise, return true. - Define a function called
nonArcIntersection
that takes an array of stringsarr
and its sizen
as parameters and returns nothing. - Initialize a variable
count
to 0 to store the count of binary strings without arc intersections. - Iterate through the elements of the array from index 0 to n-1.
- For each element, check if it does not contain any arc intersections by calling the
isIntersect
function. - If the element does not contain any arc intersections, increment the
count
. - After iterating through all elements, print the value of
count
.
Code Solution
import java.util.Stack;
/*
Java Program
Count of binary strings that does not contain Arc intersection
*/
public class Intersection
{
public boolean isIntersect (String text)
{
int n = text.length();
if(n == 0)
{
return false;
}
Stack<Character> path = new Stack<Character>();
for (int i = 0 ; i < n ; ++i )
{
if(path.isEmpty())
{
// Add new element
path.push(text.charAt(i));
}
else
{
if(path.peek()==text.charAt(i))
{
// When consecutive elements are same
path.pop();
}
else
{
// Add new element
path.push(text.charAt(i));
}
}
}
if(path.isEmpty())
{
return false;
}
else
{
// When intersection arc exist
return true;
}
}
public void nonArcintersection(String []arr, int n)
{
int count = 0;
// iterate array element
for (int i = 0; i < n ; ++i )
{
if(!isIntersect(arr[i]))
{
// Increase the counter
count++;
}
}
System.out.println(count);
}
public static void main(String[] args)
{
Intersection task = new Intersection();
String []arr = {
"1100011000","1010", "001111","101101", "101"};
int n = arr.length;
/*
arr = ["1100011000","1010",
"001111","101101",
"101"]
arr[0] = 1100011000
╔┄┄┄┄┄╗
╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ ➀ count
1 1 0 0 0 1 1 0 0 0
--------------------
arr[1] = 1010
Intersection exist
⤥
↘ ╔┄┄┄╗
╔┄│┄╗ │
│ │ │ │
│ │ │ │
1 0 1 0
--------------------
arr[2] = 001111
╔┄╗ ╔┄╗ ╔┄╗
│ │ │ │ │ │ No Intersection
│ │ │ │ │ │ ➁ count
0 0 1 1 1 1
--------------------
arr[3] = 101101
╔┄┄┄┄┄┄┄┄┄╗
│ ╔┄┄┄┄┄╗ │
│ │ ╔┄╗ │ │ No Intersection
│ │ │ │ │ │ ➂ count
│ │ │ │ │ │
1 0 1 1 0 1
--------------------
arr[4] = 101101
╔┄┄┄╗
│ │ No Intersection
│ │ but second
1 0 1 element pair missing.
So its not consider
-----------------------------
Result : 3
*/
task.nonArcintersection(arr,n);
}
}
Output
3
// Include header file
#include <iostream>
#include <stack>
#include <string>
using namespace std;
/*
C++ Program
Count of binary strings that does not contain Arc intersection
*/
class Intersection
{
public: bool isIntersect(string text)
{
int n = text.length();
if (n == 0)
{
return false;
}
stack < char > path;
for (int i = 0; i < n; ++i)
{
if (path.empty())
{
// Add new element
path.push(text[i]);
}
else
{
if (path.top() == text[i])
{
// When consecutive elements are same
path.pop();
}
else
{
// Add new element
path.push(text[i]);
}
}
}
if (path.empty())
{
return false;
}
else
{
// When intersection arc exist
return true;
}
}
void nonArcintersection(string arr[], int n)
{
int count = 0;
// iterate array element
for (int i = 0; i < n; ++i)
{
if (!this->isIntersect(arr[i]))
{
// Increase the counter
count++;
}
}
cout << count << endl;
}
};
int main()
{
Intersection *task = new Intersection();
string arr[] = {
"1100011000" , "1010" , "001111" , "101101" , "101"
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
arr = ["1100011000","1010",
"001111","101101",
"101"]
arr[0] = 1100011000
╔┄┄┄┄┄╗
╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ ➀ count
1 1 0 0 0 1 1 0 0 0
--------------------
arr[1] = 1010
Intersection exist
⤥
↘ ╔┄┄┄╗
╔┄│┄╗ │
│ │ │ │
│ │ │ │
1 0 1 0
--------------------
arr[2] = 001111
╔┄╗ ╔┄╗ ╔┄╗
│ │ │ │ │ │ No Intersection
│ │ │ │ │ │ ➁ count
0 0 1 1 1 1
--------------------
arr[3] = 101101
╔┄┄┄┄┄┄┄┄┄╗
│ ╔┄┄┄┄┄╗ │
│ │ ╔┄╗ │ │ No Intersection
│ │ │ │ │ │ ➂ count
│ │ │ │ │ │
1 0 1 1 0 1
--------------------
arr[4] = 101101
╔┄┄┄╗
│ │ No Intersection
│ │ but second
1 0 1 element pair missing.
So its not consider
-----------------------------
Result : 3
*/
task->nonArcintersection(arr, n);
return 0;
}
Output
3
// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program
Count of binary strings that does not contain Arc intersection
*/
public class Intersection
{
public Boolean isIntersect(String text)
{
int n = text.Length;
if (n == 0)
{
return false;
}
Stack < char > path = new Stack < char > ();
for (int i = 0; i < n; ++i)
{
if ((path.Count == 0))
{
// Add new element
path.Push(text[i]);
}
else
{
if (path.Peek() == text[i])
{
// When consecutive elements are same
path.Pop();
}
else
{
// Add new element
path.Push(text[i]);
}
}
}
if ((path.Count == 0))
{
return false;
}
else
{
// When intersection arc exist
return true;
}
}
public void nonArcintersection(String[] arr, int n)
{
int count = 0;
// iterate array element
for (int i = 0; i < n; ++i)
{
if (!this.isIntersect(arr[i]))
{
// Increase the counter
count++;
}
}
Console.WriteLine(count);
}
public static void Main(String[] args)
{
Intersection task = new Intersection();
String[] arr = {
"1100011000" , "1010" , "001111" , "101101" , "101"
};
int n = arr.Length;
/*
arr = ["1100011000","1010",
"001111","101101",
"101"]
arr[0] = 1100011000
╔┄┄┄┄┄╗
╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ ➀ count
1 1 0 0 0 1 1 0 0 0
--------------------
arr[1] = 1010
Intersection exist
⤥
↘ ╔┄┄┄╗
╔┄│┄╗ │
│ │ │ │
│ │ │ │
1 0 1 0
--------------------
arr[2] = 001111
╔┄╗ ╔┄╗ ╔┄╗
│ │ │ │ │ │ No Intersection
│ │ │ │ │ │ ➁ count
0 0 1 1 1 1
--------------------
arr[3] = 101101
╔┄┄┄┄┄┄┄┄┄╗
│ ╔┄┄┄┄┄╗ │
│ │ ╔┄╗ │ │ No Intersection
│ │ │ │ │ │ ➂ count
│ │ │ │ │ │
1 0 1 1 0 1
--------------------
arr[4] = 101101
╔┄┄┄╗
│ │ No Intersection
│ │ but second
1 0 1 element pair missing.
So its not consider
-----------------------------
Result : 3
*/
task.nonArcintersection(arr, n);
}
}
Output
3
package main
import "fmt"
/*
Go Program
Count of binary strings that does not contain Arc intersection
*/
func isIntersect(text string) bool {
var n int = len(text)
if n == 0 {
return false
}
var path = make([] byte, 0)
for i := 0 ; i < n ; i++ {
if len(path) == 0 {
// Add new element
path = append(path, text[i])
} else {
if path[len(path) - 1] == text[i] {
// When consecutive elements are same
path = path[: len(path) - 1]
} else {
// Add new element
path = append(path, text[i])
}
}
}
if len(path) == 0 {
return false
} else {
// When intersection arc exist
return true
}
}
func nonArcintersection(arr[] string, n int) {
var count int = 0
// iterate array element
for i := 0 ; i < n ; i++ {
if !isIntersect(arr[i]) {
// Increase the counter
count++
}
}
fmt.Println(count)
}
func main() {
var arr = [] string {"1100011000","1010","001111","101101","101"}
var n int = len(arr)
/*
arr = ["1100011000","1010",
"001111","101101",
"101"]
arr[0] = 1100011000
╔┄┄┄┄┄╗
╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ ➀ count
1 1 0 0 0 1 1 0 0 0
--------------------
arr[1] = 1010
Intersection exist
⤥
↘ ╔┄┄┄╗
╔┄│┄╗ │
│ │ │ │
│ │ │ │
1 0 1 0
--------------------
arr[2] = 001111
╔┄╗ ╔┄╗ ╔┄╗
│ │ │ │ │ │ No Intersection
│ │ │ │ │ │ ➁ count
0 0 1 1 1 1
--------------------
arr[3] = 101101
╔┄┄┄┄┄┄┄┄┄╗
│ ╔┄┄┄┄┄╗ │
│ │ ╔┄╗ │ │ No Intersection
│ │ │ │ │ │ ➂ count
│ │ │ │ │ │
1 0 1 1 0 1
--------------------
arr[4] = 101101
╔┄┄┄╗
│ │ No Intersection
│ │ but second
1 0 1 element pair missing.
So its not consider
-----------------------------
Result : 3
*/
nonArcintersection(arr, n)
}
Output
3
<?php
/*
Php Program
Count of binary strings that does not contain Arc intersection
*/
class Intersection
{
public function isIntersect($text)
{
$n = strlen($text);
if ($n == 0)
{
return false;
}
$path = array();
for ($i = 0; $i < $n; ++$i)
{
if (empty($path))
{
// Add new element
array_push($path, $text[$i]);
}
else
{
if (end($path) == $text[$i])
{
// When consecutive elements are same
array_pop($path);
}
else
{
// Add new element
array_push($path, $text[$i]);
}
}
}
if (empty($path))
{
return false;
}
else
{
// When intersection arc exist
return true;
}
}
public function nonArcintersection($arr, $n)
{
$count = 0;
// iterate array element
for ($i = 0; $i < $n; ++$i)
{
if (!$this->isIntersect($arr[$i]))
{
// Increase the counter
$count++;
}
}
echo($count."\n");
}
}
function main()
{
$task = new Intersection();
$arr = array("1100011000", "1010", "001111", "101101", "101");
$n = count($arr);
/*
arr = ["1100011000","1010",
"001111","101101",
"101"]
arr[0] = 1100011000
╔┄┄┄┄┄╗
╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ ➀ count
1 1 0 0 0 1 1 0 0 0
--------------------
arr[1] = 1010
Intersection exist
⤥
↘ ╔┄┄┄╗
╔┄│┄╗ │
│ │ │ │
│ │ │ │
1 0 1 0
--------------------
arr[2] = 001111
╔┄╗ ╔┄╗ ╔┄╗
│ │ │ │ │ │ No Intersection
│ │ │ │ │ │ ➁ count
0 0 1 1 1 1
--------------------
arr[3] = 101101
╔┄┄┄┄┄┄┄┄┄╗
│ ╔┄┄┄┄┄╗ │
│ │ ╔┄╗ │ │ No Intersection
│ │ │ │ │ │ ➂ count
│ │ │ │ │ │
1 0 1 1 0 1
--------------------
arr[4] = 101101
╔┄┄┄╗
│ │ No Intersection
│ │ but second
1 0 1 element pair missing.
So its not consider
-----------------------------
Result : 3
*/
$task->nonArcintersection($arr, $n);
}
main();
Output
3
/*
Node JS Program
Count of binary strings that does not contain Arc intersection
*/
class Intersection
{
isIntersect(text)
{
var n = text.length;
if (n == 0)
{
return false;
}
var path = [];
for (var i = 0; i < n; ++i)
{
if ((path.length == 0))
{
// Add new element
path.push(text.charAt(i));
}
else
{
if (path[path.length - 1] == text.charAt(i))
{
// When consecutive elements are same
path.pop();
}
else
{
// Add new element
path.push(text.charAt(i));
}
}
}
if ((path.length == 0))
{
return false;
}
else
{
// When intersection arc exist
return true;
}
}
nonArcintersection(arr, n)
{
var count = 0;
// iterate array element
for (var i = 0; i < n; ++i)
{
if (!this.isIntersect(arr[i]))
{
// Increase the counter
count++;
}
}
console.log(count);
}
}
function main()
{
var task = new Intersection();
var arr = ["1100011000", "1010", "001111", "101101", "101"];
var n = arr.length;
/*
arr = ["1100011000","1010",
"001111","101101",
"101"]
arr[0] = 1100011000
╔┄┄┄┄┄╗
╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ ➀ count
1 1 0 0 0 1 1 0 0 0
--------------------
arr[1] = 1010
Intersection exist
⤥
↘ ╔┄┄┄╗
╔┄│┄╗ │
│ │ │ │
│ │ │ │
1 0 1 0
--------------------
arr[2] = 001111
╔┄╗ ╔┄╗ ╔┄╗
│ │ │ │ │ │ No Intersection
│ │ │ │ │ │ ➁ count
0 0 1 1 1 1
--------------------
arr[3] = 101101
╔┄┄┄┄┄┄┄┄┄╗
│ ╔┄┄┄┄┄╗ │
│ │ ╔┄╗ │ │ No Intersection
│ │ │ │ │ │ ➂ count
│ │ │ │ │ │
1 0 1 1 0 1
--------------------
arr[4] = 101101
╔┄┄┄╗
│ │ No Intersection
│ │ but second
1 0 1 element pair missing.
So its not consider
-----------------------------
Result : 3
*/
task.nonArcintersection(arr, n);
}
main();
Output
3
# Python 3 Program
# Count of binary strings that does not contain Arc intersection
class Intersection :
def isIntersect(self, text) :
n = len(text)
if (n == 0) :
return False
path = []
i = 0
while (i < n) :
if ((len(path) == 0)) :
# Add new element
path.append(text[i])
else :
if (path[-1] == text[i]) :
# When consecutive elements are same
path.pop()
else :
# Add new element
path.append(text[i])
i += 1
if ((len(path) == 0)) :
return False
else :
# When intersection arc exist
return True
def nonArcintersection(self, arr, n) :
count = 0
i = 0
# iterate list element
while (i < n) :
if (not self.isIntersect(arr[i])) :
# Increase the counter
count += 1
i += 1
print(count)
def main() :
task = Intersection()
arr = ["1100011000", "1010", "001111", "101101", "101"]
n = len(arr)
# arr = ["1100011000","1010",
# "001111","101101",
# "101"]
# arr[0] = 1100011000
# ╔┄┄┄┄┄╗
# ╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
# │ │ │ │ │ │ │ │ │ │
# │ │ │ │ │ │ │ │ │ │ ➀ count
# 1 1 0 0 0 1 1 0 0 0
# --------------------
# arr[1] = 1010
# Intersection exist
# ⤥
# ↘ ╔┄┄┄╗
# ╔┄│┄╗ │
# │ │ │ │
# │ │ │ │
# 1 0 1 0
# --------------------
# arr[2] = 001111
# ╔┄╗ ╔┄╗ ╔┄╗
# │ │ │ │ │ │ No Intersection
# │ │ │ │ │ │ ➁ count
# 0 0 1 1 1 1
# --------------------
# arr[3] = 101101
# ╔┄┄┄┄┄┄┄┄┄╗
# │ ╔┄┄┄┄┄╗ │
# │ │ ╔┄╗ │ │ No Intersection
# │ │ │ │ │ │ ➂ count
# │ │ │ │ │ │
# 1 0 1 1 0 1
# --------------------
# arr[4] = 101101
# ╔┄┄┄╗
# │ │ No Intersection
# │ │ but second
# 1 0 1 element pair missing.
# So its not consider
# -----------------------------
# Result : 3
task.nonArcintersection(arr, n)
if __name__ == "__main__": main()
Output
3
# Ruby Program
# Count of binary strings that does not contain Arc intersection
class Intersection
def isIntersect(text)
n = text.length
if (n == 0)
return false
end
path = []
i = 0
while (i < n)
if ((path.length == 0))
# Add new element
path.push(text[i])
else
if (path.last == text[i])
# When consecutive elements are same
path.pop()
else
# Add new element
path.push(text[i])
end
end
i += 1
end
if ((path.length == 0))
return false
else
# When intersection arc exist
return true
end
end
def nonArcintersection(arr, n)
count = 0
i = 0
# iterate array element
while (i < n)
if (!self.isIntersect(arr[i]))
# Increase the counter
count += 1
end
i += 1
end
print(count, "\n")
end
end
def main()
task = Intersection.new()
arr = ["1100011000", "1010", "001111", "101101", "101"]
n = arr.length
# arr = ["1100011000","1010",
# "001111","101101",
# "101"]
# arr[0] = 1100011000
# ╔┄┄┄┄┄╗
# ╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
# │ │ │ │ │ │ │ │ │ │
# │ │ │ │ │ │ │ │ │ │ ➀ count
# 1 1 0 0 0 1 1 0 0 0
# --------------------
# arr[1] = 1010
# Intersection exist
# ⤥
# ↘ ╔┄┄┄╗
# ╔┄│┄╗ │
# │ │ │ │
# │ │ │ │
# 1 0 1 0
# --------------------
# arr[2] = 001111
# ╔┄╗ ╔┄╗ ╔┄╗
# │ │ │ │ │ │ No Intersection
# │ │ │ │ │ │ ➁ count
# 0 0 1 1 1 1
# --------------------
# arr[3] = 101101
# ╔┄┄┄┄┄┄┄┄┄╗
# │ ╔┄┄┄┄┄╗ │
# │ │ ╔┄╗ │ │ No Intersection
# │ │ │ │ │ │ ➂ count
# │ │ │ │ │ │
# 1 0 1 1 0 1
# --------------------
# arr[4] = 101101
# ╔┄┄┄╗
# │ │ No Intersection
# │ │ but second
# 1 0 1 element pair missing.
# So its not consider
# -----------------------------
# Result : 3
task.nonArcintersection(arr, n)
end
main()
Output
3
import scala.collection.mutable._;
/*
Scala Program
Count of binary strings that does not contain Arc intersection
*/
class Intersection()
{
def isIntersect(text: String): Boolean = {
var n: Int = text.length();
if (n == 0)
{
return false;
}
var path: Stack[Character] = new Stack[Character]();
var i: Int = 0;
while (i < n)
{
if (path.isEmpty)
{
// Add new element
path.push(text.charAt(i));
}
else
{
if (path.top == text.charAt(i).toInt)
{
// When consecutive elements are same
path.pop;
}
else
{
// Add new element
path.push(text.charAt(i));
}
}
i += 1;
}
if (path.isEmpty)
{
return false;
}
else
{
// When intersection arc exist
return true;
}
}
def nonArcintersection(arr: Array[String], n: Int): Unit = {
var count: Int = 0;
var i: Int = 0;
// iterate array element
while (i < n)
{
if (!isIntersect(arr(i)))
{
// Increase the counter
count += 1;
}
i += 1;
}
println(count);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Intersection = new Intersection();
var arr: Array[String] = Array(
"1100011000", "1010", "001111", "101101", "101");
var n: Int = arr.length;
/*
arr = ["1100011000","1010",
"001111","101101",
"101"]
arr[0] = 1100011000
╔┄┄┄┄┄╗
╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ ➀ count
1 1 0 0 0 1 1 0 0 0
--------------------
arr[1] = 1010
Intersection exist
⤥
↘ ╔┄┄┄╗
╔┄│┄╗ │
│ │ │ │
│ │ │ │
1 0 1 0
--------------------
arr[2] = 001111
╔┄╗ ╔┄╗ ╔┄╗
│ │ │ │ │ │ No Intersection
│ │ │ │ │ │ ➁ count
0 0 1 1 1 1
--------------------
arr[3] = 101101
╔┄┄┄┄┄┄┄┄┄╗
│ ╔┄┄┄┄┄╗ │
│ │ ╔┄╗ │ │ No Intersection
│ │ │ │ │ │ ➂ count
│ │ │ │ │ │
1 0 1 1 0 1
--------------------
arr[4] = 101101
╔┄┄┄╗
│ │ No Intersection
│ │ but second
1 0 1 element pair missing.
So its not consider
-----------------------------
Result : 3
*/
task.nonArcintersection(arr, n);
}
}
Output
3
import Foundation;
/*
Swift 4 Program
Count of binary strings that does not contain Arc intersection
*/
struct Stack
{
private
var items: [Character] = []
func peek()->Character
{
if (self.isEmpty()==false)
{
return items.first!
}
else
{
fatalError("This stack is empty.")
}
}
func isEmpty()->Bool
{
return items.count == 0
}
mutating func pop()
{
items.removeFirst()
}
mutating func push(_ data: Character)
{
items.insert(data, at: 0)
}
}
class Intersection
{
func isIntersect(_ data: String) -> Bool
{
let text = Array(data);
let n: Int = text.count;
if (n == 0)
{
return false;
}
var path = Stack();
var i: Int = 0;
while (i < n)
{
if (path.isEmpty())
{
// Add new element
path.push(text[i]);
}
else
{
if (path.peek() == text[i])
{
// When consecutive elements are same
path.pop();
}
else
{
// Add new element
path.push(text[i]);
}
}
i += 1;
}
if (path.isEmpty())
{
return false;
}
else
{
// When intersection arc exist
return true;
}
}
func nonArcintersection(_ arr: [String], _ n: Int)
{
var count: Int = 0;
var i: Int = 0;
// iterate array element
while (i < n)
{
if (!self.isIntersect(arr[i]))
{
// Increase the counter
count += 1;
}
i += 1;
}
print(count);
}
}
func main()
{
let task: Intersection = Intersection();
let arr: [String] = ["1100011000",
"1010",
"001111",
"101101",
"101"];
let n: Int = arr.count;
/*
arr = ["1100011000","1010",
"001111","101101",
"101"]
arr[0] = 1100011000
╔┄┄┄┄┄╗
╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ ➀ count
1 1 0 0 0 1 1 0 0 0
--------------------
arr[1] = 1010
Intersection exist
⤥
↘ ╔┄┄┄╗
╔┄│┄╗ │
│ │ │ │
│ │ │ │
1 0 1 0
--------------------
arr[2] = 001111
╔┄╗ ╔┄╗ ╔┄╗
│ │ │ │ │ │ No Intersection
│ │ │ │ │ │ ➁ count
0 0 1 1 1 1
--------------------
arr[3] = 101101
╔┄┄┄┄┄┄┄┄┄╗
│ ╔┄┄┄┄┄╗ │
│ │ ╔┄╗ │ │ No Intersection
│ │ │ │ │ │ ➂ count
│ │ │ │ │ │
1 0 1 1 0 1
--------------------
arr[4] = 101101
╔┄┄┄╗
│ │ No Intersection
│ │ but second
1 0 1 element pair missing.
So its not consider
-----------------------------
Result : 3
*/
task.nonArcintersection(arr, n);
}
main();
Output
3
import java.util.Stack;
/*
Kotlin Program
Count of binary strings that does not contain Arc intersection
*/
class Intersection
{
fun isIntersect(text: String): Boolean
{
val n: Int = text.length;
if (n == 0)
{
return false;
}
val path: Stack < Char > = Stack < Char > ();
var i: Int = 0;
while (i < n)
{
if (path.empty())
{
// Add new element
path.push(text.get(i));
}
else
{
if (path.peek() == text.get(i))
{
// When consecutive elements are same
path.pop();
}
else
{
// Add new element
path.push(text.get(i));
}
}
i += 1;
}
if (path.empty())
{
return false;
}
else
{
// When intersection arc exist
return true;
}
}
fun nonArcintersection(arr: Array < String > , n: Int): Unit
{
var count: Int = 0;
var i: Int = 0;
// iterate array element
while (i < n)
{
if (!this.isIntersect(arr[i]))
{
// Increase the counter
count += 1;
}
i += 1;
}
println(count);
}
}
fun main(args: Array < String > ): Unit
{
val task: Intersection = Intersection();
val arr: Array < String > = arrayOf(
"1100011000", "1010", "001111", "101101", "101");
val n: Int = arr.count();
/*
arr = ["1100011000","1010",
"001111","101101",
"101"]
arr[0] = 1100011000
╔┄┄┄┄┄╗
╔┄╗ ╔┄╗ │ ╔┄╗ │ ╔┄╗ No Intersection
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ ➀ count
1 1 0 0 0 1 1 0 0 0
--------------------
arr[1] = 1010
Intersection exist
⤥
↘ ╔┄┄┄╗
╔┄│┄╗ │
│ │ │ │
│ │ │ │
1 0 1 0
--------------------
arr[2] = 001111
╔┄╗ ╔┄╗ ╔┄╗
│ │ │ │ │ │ No Intersection
│ │ │ │ │ │ ➁ count
0 0 1 1 1 1
--------------------
arr[3] = 101101
╔┄┄┄┄┄┄┄┄┄╗
│ ╔┄┄┄┄┄╗ │
│ │ ╔┄╗ │ │ No Intersection
│ │ │ │ │ │ ➂ count
│ │ │ │ │ │
1 0 1 1 0 1
--------------------
arr[4] = 101101
╔┄┄┄╗
│ │ No Intersection
│ │ but second
1 0 1 element pair missing.
So its not consider
-----------------------------
Result : 3
*/
task.nonArcintersection(arr, n);
}
Output
3
Time Complexity
Let m be the maximum length of binary strings in the array, and n be the number of strings in the array. The time
complexity of the isIntersect
function is O(m) as it performs a single pass through the binary
string. The nonArcIntersection
function iterates through all elements of the array and calls the
isIntersect
function for each element, resulting in a time complexity of O(n * m). Overall, the
time complexity of the code is O(n * m).
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