# 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:

1. The first binary string "1100011000" has two arc intersections "00" and "11".
2. The second binary string "1010" has an arc intersection "11".
3. The third binary string "001111" has no arc intersections.
4. The fourth binary string "101101" has an arc intersection "11".
5. 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

1. Create a class called `Intersection`.
2. Define a function called `isIntersect` that takes a string `text` as a parameter and returns a boolean value.
3. Get the length `n` of the string `text`.
4. If `n` is 0, return false as an empty string cannot have any arc intersections.
5. Create an empty stack called `path`.
6. Iterate through the characters of the string from index 0 to n-1.
7. 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.
8. 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.
9. Define a function called `nonArcIntersection` that takes an array of strings `arr` and its size `n` as parameters and returns nothing.
10. Initialize a variable `count` to 0 to store the count of binary strings without arc intersections.
11. Iterate through the elements of the array from index 0 to n-1.
12. For each element, check if it does not contain any arc intersections by calling the `isIntersect` function.
13. If the element does not contain any arc intersections, increment the `count`.
14. 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())
{
path.push(text.charAt(i));
}
else
{
if(path.peek()==text.charAt(i))
{
// When consecutive elements are same
path.pop();
}
else
{
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)
{

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

*/

}
}``````

#### 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())
{
path.push(text[i]);
}
else
{
if (path.top() == text[i])
{
// When consecutive elements are same
path.pop();
}
else
{
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()
{
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

*/
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))
{
path.Push(text[i]);
}
else
{
if (path.Peek() == text[i])
{
// When consecutive elements are same
path.Pop();
}
else
{
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)
{
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

*/
}
}``````

#### 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 {
path = append(path, text[i])
} else {
if path[len(path) - 1] == text[i] {
// When consecutive elements are same
path = path[: len(path) - 1]
} else {
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))
{
array_push(\$path, \$text[\$i]);
}
else
{
if (end(\$path) == \$text[\$i])
{
// When consecutive elements are same
array_pop(\$path);
}
else
{
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()
{
\$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

*/
}
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))
{
path.push(text.charAt(i));
}
else
{
if (path[path.length - 1] == text.charAt(i))
{
// When consecutive elements are same
path.pop();
}
else
{
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 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

*/
}
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)) :
path.append(text[i])
else :
if (path[-1] == text[i]) :
#  When consecutive elements are same
path.pop()
else :
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() :
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

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))
path.push(text[i])
else

if (path.last == text[i])
#  When consecutive elements are same
path.pop()
else

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()
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
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)
{
path.push(text.charAt(i));
}
else
{
if (path.top == text.charAt(i).toInt)
{
// When consecutive elements are same
path.pop;
}
else
{
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

*/
}
}``````

#### 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())
{
path.push(text[i]);
}
else
{
if (path.peek() == text[i])
{
// When consecutive elements are same
path.pop();
}
else
{
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 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

*/
}
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())
{
path.push(text.get(i));
}
else
{
if (path.peek() == text.get(i))
{
// When consecutive elements are same
path.pop();
}
else
{
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 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

*/
}``````

#### 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).

## Comment

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.