Skip to main content

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())
            {
                // 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).

Last updated on by Kalkicode




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.

New Comment