Skip to main content

Count of binary strings that does not contain Arc intersection

Here given code implementation process.

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