Find if an array of strings can be chained to form a circle | Set 1

Last Updated : 15 Feb, 2023

Given an array of strings, find if the given strings can be chained to form a circle. A string X can be put before another string Y in circle if the last character of X is same as first character of Y.
Examples:

Input: arr[] = {"geek", "king"}
Output: Yes, the given strings can be chained.
Note that the last character of first string is same
as first character of second string and vice versa is
also true.

Input: arr[] = {"for", "geek", "rig", "kaf"}
Output: Yes, the given strings can be chained.
The strings can be chained as "for", "rig", "geek" 
and "kaf"

Input: arr[] = {"aab", "bac", "aaa", "cda"}
Output: Yes, the given strings can be chained.
The strings can be chained as "aaa", "aab", "bac" 
and "cda"

Input: arr[] = {"aaa", "bbb", "baa", "aab"};
Output: Yes, the given strings can be chained.
The strings can be chained as "aaa", "aab", "bbb" 
and "baa"

Input: arr[] = {"aaa"};
Output: Yes

Input: arr[] = {"aaa", "bbb"};
Output: No

Input  : arr[] = ["abc", "efg", "cde", "ghi", "ija"]
Output : Yes
These strings can be reordered as, “abc”, “cde”, “efg”,
“ghi”, “ija”

Input : arr[] = [“ijk”, “kji”, “abc”, “cba”]
Output : No

The idea is to create a directed graph of all characters and then find if there is an eulerian circuit in the graph or not.
Graph representation of some string arrays are given in below diagram,

If there is an eulerian circuit, then chain can be formed, otherwise not.

Note that a directed graph has eulerian circuit only if in degree and out degree of every vertex is same, and all non-zero degree vertices form a single strongly connected component.

Following are detailed steps of the algorithm.

Create a directed graph g with number of vertices equal to the size of alphabet. We have created a graph with 26 vertices in the below program.

Do following for every string in the given array of strings.

…..a) Add an edge from first character to last character of the given graph.

If the created graph has eulerian circuit, then return true, else return false.

Following are C++ and Python implementations of the above algorithm.

C++

// A C++ program to check if a given 
// directed graph is Eulerian or not
#include<iostream>
#include <list>
#define CHARS 26
using namespace std;
 
// A class that represents an undirected graph
class Graph
{
    int V;    // No. of vertices
    list<int> *adj; // A dynamic array of adjacency lists
    int *in;
public:
    // Constructor and destructor
    Graph(int V);
    ~Graph()   { delete [] adj; delete [] in; }
 
    // function to add an edge to graph
    void addEdge(int v, int w) { adj[v].push_back(w);  (in[w])++; }
 
    // Method to check if this graph is Eulerian or not
    bool isEulerianCycle();
 
    // Method to check if all non-zero degree 
    // vertices are connected
    bool isSC();
 
    // Function to do DFS starting from v. Used in isConnected();
    void DFSUtil(int v, bool visited[]);
 
    Graph getTranspose();
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
    in = new int[V];
    for (int i = 0; i < V; i++)
       in[i] = 0;
}
 
/* This function returns true if the directed 
   graph has an eulerian cycle, otherwise returns
   false  */
bool Graph::isEulerianCycle()
{
    // Check if all non-zero degree vertices are connected
    if (isSC() == false)
        return false;
 
    // Check if in degree and out degree 
    // of every vertex is same
    for (int i = 0; i < V; i++)
        if (adj[i].size() != in[i])
            return false;
 
    return true;
}
 
// A recursive function to do DFS starting from v
void Graph::DFSUtil(int v, bool visited[])
{
    // Mark the current node as visited and print it
    visited[v] = true;
 
    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}
 
// Function that returns reverse (or transpose) of this graph
// This function is needed in isSC()
Graph Graph::getTranspose()
{
    Graph g(V);
    for (int v = 0; v < V; v++)
    {
        // Recur for all the vertices adjacent to this vertex
        list<int>::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
        {
            g.adj[*i].push_back(v);
            (g.in[v])++;
        }
    }
    return g;
}
 
// This function returns true if all non-zero
// degree vertices of graph are strongly connected.
// Please refer
// https://www.geeksforgeeks.org/connectivity-in-a-directed-graph/
bool Graph::isSC()
{
    // Mark all the vertices as not visited (For first DFS)
    bool visited[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
 
    // Find the first vertex with non-zero degree
    int n;
    for (n = 0; n < V; n++)
        if (adj[n].size() > 0)
          break;
 
    // Do DFS traversal starting from first non zero degree vertex.
    DFSUtil(n, visited);
 
     // If DFS traversal doesn’t visit all vertices, then return false.
    for (int i = 0; i < V; i++)
        if (adj[i].size() > 0 && visited[i] == false)
              return false;
 
    // Create a reversed graph
    Graph gr = getTranspose();
 
    // Mark all the vertices as not visited (For second DFS)
    for (int i = 0; i < V; i++)
        visited[i] = false;
 
    // Do DFS for reversed graph starting from first vertex.
    // Starting Vertex must be same starting point of first DFS
    gr.DFSUtil(n, visited);
 
    // If all vertices are not visited in second DFS, then
    // return false
    for (int i = 0; i < V; i++)
        if (adj[i].size() > 0 && visited[i] == false)
             return false;
 
    return true;
}
 
// This function takes an of strings and returns true
// if the given array of strings can be chained to
// form cycle
bool canBeChained(string arr[], int n)
{
    // Create a graph with 'alpha' edges
    Graph g(CHARS);
 
    // Create an edge from first character to last character
    // of every string
    for (int i = 0; i < n; i++)
    {
        string s = arr[i];
        g.addEdge(s[0]-'a', s[s.length()-1]-'a');
    }
 
    // The given array of strings can be chained if there
    // is an eulerian cycle in the created graph
    return g.isEulerianCycle();
}
 
// Driver program to test above functions
int main()
{
    string arr1[] =  {"for", "geek", "rig", "kaf"};
    int n1 = sizeof(arr1)/sizeof(arr1[0]);
    canBeChained(arr1, n1)?  cout << "Can be chained \n" :
                           cout << "Can't be chained \n";
 
    string arr2[] =  {"aab", "abb"};
    int n2 = sizeof(arr2)/sizeof(arr2[0]);
    canBeChained(arr2, n2)?  cout << "Can be chained \n" :
                           cout << "Can't be chained \n";
 
    return 0;
}

Java

// Java program to check if a given 
// directed graph is Eulerian or not 
import java.util.ArrayList;
import java.util.List;
 
// A class that represents an 
// undirected graph
class GFG{
     
static final int CHARS = 26;
 
// No. of vertices
int V; 
 
// A dynamic array of adjacency lists
List<List<Integer>> adj; 
int[] in;
 
// Constructor
GFG(int V)
{
    this.V = V;
    in = new int[V];
    adj = new ArrayList<>(CHARS);
     
    for(int i = 0; i < CHARS; i++)
    {
       adj.add(i, new ArrayList<>());
    }
}
 
// Function to add an edge to graph
void addEdge(int v, int w)
{
    adj.get(v).add(w);
    in[w]++;
}
 
// Method to check if this graph 
// is Eulerian or not
boolean isEulerianCycle() 
{
     
    // Check if all non-zero degree 
    // vertices are connected
    if (!isSC())
        return false;
 
    // Check if in degree and out 
    // degree of every vertex is same
    for(int i = 0; i < V; i++)
       if (adj.get(i).size() != in[i])
           return false;
 
    return true;
}
 
// This function returns true if all 
// non-zero degree vertices of graph
// are strongly connected. Please refer
boolean isSC() 
{
     
    // Mark all the vertices as not 
    // visited (For first DFS)
    boolean[] visited = new boolean[V];
    for(int i = 0; i < V; i++)
       visited[i] = false;
 
    // Find the first vertex with 
    // non-zero degree
    int n;
    for(n = 0; n < V; n++)
       if (adj.get(n).size() > 0)
           break;
 
    // Do DFS traversal starting from 
    // first non zero degree vertex.
    DFSUtil(n, visited);
 
    // If DFS traversal doesn't visit all 
    // vertices, then return false.
    for(int i = 0; i < V; i++)
       if (adj.get(i).size() > 0 && !visited[i])
           return false;
 
    // Create a reversed graph
    GFG gr = getTranspose();
 
    // Mark all the vertices as not 
    // visited (For second DFS)
    for(int i = 0; i < V; i++)
       visited[i] = false;
 
    // Do DFS for reversed graph starting
    // from first vertex. Starting Vertex 
    // must be same starting point of first DFS
    gr.DFSUtil(n, visited);
 
    // If all vertices are not visited in 
    // second DFS, then return false
    for(int i = 0; i < V; i++)
       if (adj.get(i).size() > 0 && !visited[i])
           return false;
 
    return true;
}
 
// Function to do DFS starting from v.
// Used in isConnected();
// A recursive function to do DFS 
// starting from v
void DFSUtil(int v, boolean[] visited)
{
     
    // Mark the current node as 
    // visited and print it
    visited[v] = true;
 
    // Recur for all the vertices 
    // adjacent to this vertex
    for(Integer i : adj.get(v))
       if (!visited[i])
       {
           DFSUtil(i, visited);
       }
}
 
// Function that returns reverse 
// (or transpose) of this graph
// This function is needed in isSC()
GFG getTranspose()
{
    GFG g = new GFG(V);
    for(int v = 0; v < V; v++)
    {
        
       // Recur for all the vertices 
       // adjacent to this vertex
       for(Integer i : adj.get(v))
       {
          g.adj.get(i).add(v);
          g.in[v]++;
       }
    }
    return g;
}
 
// This function takes an of strings
// and returns true if the given array
// of strings can be chained to form cycle
static boolean canBeChained(String[] arr, int n)
{
     
    // Create a graph with 'alpha' edges
    GFG g = new GFG(CHARS);
 
    // Create an edge from first character
    // to last character of every string
    for(int i = 0; i < n; i++)
    {
       String s = arr[i];
       g.addEdge(s.charAt(0) - 'a', 
                 s.charAt(s.length() - 1) - 'a');
    }
     
    // The given array of strings can be 
    // chained if there is an eulerian 
    // cycle in the created graph
    return g.isEulerianCycle();
}
 
// Driver code
public static void main(String[] args) throws Exception
{
    String[] arr1 = { "for", "geek", 
                      "rig", "kaf" };
    int n1 = arr1.length;
     
    System.out.println((canBeChained(arr1, n1) ?
                       "Can be chained " : 
                       "Can't be chained "));
 
    String[] arr2 = { "aab", "abb" };
    int n2 = arr2.length;
     
    System.out.println((canBeChained(arr2, n2) ?
                       "Can be chained " : 
                       "Can't be chained "));
}
}
 
// This code is contributed by abhay379201

Python3

# Python program to check if a given directed graph is Eulerian or not
CHARS = 26
 
# A class that represents an undirected graph
class Graph(object):
    def __init__(self, V):
        self.V = V      # No. of vertices
        self.adj = [[] for x in range(V)]  # a dynamic array
        self.inp = [0] * V
 
    # function to add an edge to graph
    def addEdge(self, v, w):
        self.adj[v].append(w)
        self.inp[w]+=1
 
    # Method to check if this graph is Eulerian or not
    def isSC(self):
        # Mark all the vertices as not visited (For first DFS)
        visited = [False] * self.V
 
        # Find the first vertex with non-zero degree
        n = 0
        for n in range(self.V):
            if len(self.adj[n]) > 0:
                break
 
        # Do DFS traversal starting from first non zero degree vertex.
        self.DFSUtil(n, visited)
 
        # If DFS traversal doesn't visit all vertices, then return false.
        for i in range(self.V):
            if len(self.adj[i]) > 0 and visited[i] == False:
                return False
 
        # Create a reversed graph
        gr = self.getTranspose()
 
        # Mark all the vertices as not visited (For second DFS)
        for i in range(self.V):
            visited[i] = False
 
        # Do DFS for reversed graph starting from first vertex.
        # Starting Vertex must be same starting point of first DFS
        gr.DFSUtil(n, visited)
 
        # If all vertices are not visited in second DFS, then
        # return false
        for i in range(self.V):
            if len(self.adj[i]) > 0 and visited[i] == False:
                return False
 
        return True
 
    # This function returns true if the directed graph has an eulerian
    # cycle, otherwise returns false
    def isEulerianCycle(self):
 
        # Check if all non-zero degree vertices are connected
        if self.isSC() == False:
            return False
 
        # Check if in degree and out degree of every vertex is same
        for i in range(self.V):
            if len(self.adj[i]) != self.inp[i]:
                return False
 
        return True
 
    # A recursive function to do DFS starting from v
    def DFSUtil(self, v, visited):
 
        # Mark the current node as visited and print it
        visited[v] = True
 
        # Recur for all the vertices adjacent to this vertex
        for i in range(len(self.adj[v])):
            if not visited[self.adj[v][i]]:
                self.DFSUtil(self.adj[v][i], visited)
 
    # Function that returns reverse (or transpose) of this graph
    # This function is needed in isSC()
    def getTranspose(self):
        g = Graph(self.V)
        for v in range(self.V):
            # Recur for all the vertices adjacent to this vertex
            for i in range(len(self.adj[v])):
                g.adj[self.adj[v][i]].append(v)
                g.inp[v]+=1
        return g
 
# This function takes an of strings and returns true
# if the given array of strings can be chained to
# form cycle
def canBeChained(arr, n):
 
    # Create a graph with 'alpha' edges
    g = Graph(CHARS)
 
    # Create an edge from first character to last character
    # of every string
    for i in range(n):
        s = arr[i]
        g.addEdge(ord(s[0])-ord('a'), ord(s[len(s)-1])-ord('a'))
 
    # The given array of strings can be chained if there
    # is an eulerian cycle in the created graph
    return g.isEulerianCycle()
 
# Driver program
arr1 = ["for", "geek", "rig", "kaf"]
n1 = len(arr1)
if canBeChained(arr1, n1):
    print ("Can be chained")
else:
    print ("Cant be chained")
 
arr2 = ["aab", "abb"]
n2 = len(arr2)
if canBeChained(arr2, n2):
    print ("Can be chained")
else:
    print ("Can't be chained")
 
# This code is contributed by BHAVYA JAIN

C#

// C# program to check if a given
// directed graph is Eulerian or not
using System;
using System.Collections.Generic;
 
// A class that represents an
// undirected graph
public class GFG {
 
    static readonly int CHARS = 26;
 
    // No. of vertices
    int V;
 
    // A dynamic array of adjacency lists
    List<List<int> > adj;
    int[] ind;
 
    // Constructor
    GFG(int V)
    {
        this.V = V;
        ind = new int[V];
        adj = new List<List<int> >(CHARS);
 
        for (int i = 0; i < CHARS; i++) {
            adj.Add(new List<int>());
        }
    }
 
    // Function to add an edge to graph
    void addEdge(int v, int w)
    {
        adj[v].Add(w);
        ind[w]++;
    }
 
    // Method to check if this graph
    // is Eulerian or not
    bool isEulerianCycle()
    {
 
        // Check if all non-zero degree
        // vertices are connected
        if (!isSC())
            return false;
 
        // Check if in degree and out
        // degree of every vertex is same
        for (int i = 0; i < V; i++)
            if (adj[i].Count != ind[i])
                return false;
 
        return true;
    }
 
    // This function returns true if all
    // non-zero degree vertices of graph
    // are strongly connected. Please refer
    bool isSC()
    {
 
        // Mark all the vertices as not
        // visited (For first DFS)
        bool[] visited = new bool[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;
 
        // Find the first vertex with
        // non-zero degree
        int n;
        for (n = 0; n < V; n++)
            if (adj[n].Count > 0)
                break;
 
        // Do DFS traversal starting from
        // first non zero degree vertex.
        DFSUtil(n, visited);
 
        // If DFS traversal doesn't visit all
        // vertices, then return false.
        for (int i = 0; i < V; i++)
            if (adj[i].Count > 0 && !visited[i])
                return false;
 
        // Create a reversed graph
        GFG gr = getTranspose();
 
        // Mark all the vertices as not
        // visited (For second DFS)
        for (int i = 0; i < V; i++)
            visited[i] = false;
 
        // Do DFS for reversed graph starting
        // from first vertex. Starting Vertex
        // must be same starting point of first DFS
        gr.DFSUtil(n, visited);
 
        // If all vertices are not visited in
        // second DFS, then return false
        for (int i = 0; i < V; i++)
            if (adj[i].Count > 0 && !visited[i])
                return false;
 
        return true;
    }
 
    // Function to do DFS starting from v.
    // Used in isConnected();
    // A recursive function to do DFS
    // starting from v
    void DFSUtil(int v, bool[] visited)
    {
 
        // Mark the current node as
        // visited and print it
        visited[v] = true;
 
        // Recur for all the vertices
        // adjacent to this vertex
        foreach(int i in adj[v]) if (!visited[i])
        {
            DFSUtil(i, visited);
        }
    }
 
    // Function that returns reverse
    // (or transpose) of this graph
    // This function is needed in isSC()
    GFG getTranspose()
    {
        GFG g = new GFG(V);
        for (int v = 0; v < V; v++) {
 
            // Recur for all the vertices
            // adjacent to this vertex
            foreach(int i in adj[v])
            {
                g.adj[i].Add(v);
                g.ind[v]++;
            }
        }
        return g;
    }
 
    // This function takes an of strings
    // and returns true if the given array
    // of strings can be chained to form cycle
    static bool canBeChained(String[] arr, int n)
    {
 
        // Create a graph with 'alpha' edges
        GFG g = new GFG(CHARS);
 
        // Create an edge from first character
        // to last character of every string
        for (int i = 0; i < n; i++) {
            String s = arr[i];
            g.addEdge(s[0] - 'a', s[s.Length - 1] - 'a');
        }
 
        // The given array of strings can be
        // chained if there is an eulerian
        // cycle in the created graph
        return g.isEulerianCycle();
    }
 
    // Driver code
    static public void Main()
    {
        String[] arr1 = { "for", "geek", "rig", "kaf" };
        int n1 = arr1.Length;
 
        Console.WriteLine((canBeChained(arr1, n1)
                               ? "Can be chained "
                               : "Can't be chained "));
 
        String[] arr2 = { "aab", "abb" };
        int n2 = arr2.Length;
 
        Console.WriteLine((canBeChained(arr2, n2)
                               ? "Can be chained "
                               : "Can't be chained "));
    }
}
 
// This code is contributed by akashish__

Javascript

// A Javascript program to check if 
// a given directed graph is Eulerian or not
      let CHARS = 26;
 
      // A class that represents an undirected graph
      class Graph {
        constructor(V) {
          this.V = V; // No. of vertices
          this.adj = Array.from(Array(V), () => new Array()); // A dynamic array of adjacency lists
          this.in = new Array(V);
          for (let i = 0; i < V; i++) {
            this.in[i] = 0;
          }
        }
 
        // function to add an edge to graph
        addEdge(v, w) {
          this.adj[v].push(w);
          this.in[w]++;
        }
 
        // Method to check if this graph is Eulerian or not
        /* This function returns true if the directed
           graph has an eulerian cycle, otherwise returns
           false  */
 
        isEulerianCycle() {
          // Check if all non-zero degree vertices are connected
          if (this.isSC() == false) return false;
 
          // Check if in degree and out degree
          // of every vertex is same
          for (let i = 0; i < this.V; i++)
            if (this.adj[i].length != this.in[i]) return false;
 
          return true;
        }
 
        // Method/Function to check if all non-zero degree
        // vertices are connected
 
        // This function returns true if all non-zero
        // degree vertices of graph are strongly connected.
        // Please refer
        // https://www.geeksforgeeks.org/connectivity-in-a-directed-graph/
        isSC() {
          // Mark all the vertices as not visited (For first DFS)
          let visited = new Array(this.V);
          for (let i = 0; i < this.V; i++) visited[i] = false;
 
          // Find the first vertex with non-zero degree
          let n;
          for (n = 0; n < this.V; n++) if (this.adj[n].length > 0) break;
 
          // Do DFS traversal starting from first non zero degree vertex.
          this.DFSUtil(n, visited);
 
          // If DFS traversal doesn’t visit all vertices, then return false.
          for (let i = 0; i < this.V; i++)
            if (this.adj[i].length > 0 && visited[i] == false) return false;
 
          // Create a reversed graph
          let gr = this.getTranspose();
 
          // Mark all the vertices as not visited (For second DFS)
          for (let i = 0; i < this.V; i++) visited[i] = false;
 
          // Do DFS for reversed graph starting from first vertex.
          // Starting Vertex must be same starting point of first DFS
          gr.DFSUtil(n, visited);
 
          // If all vertices are not visited in second DFS, then
          // return false
          for (let i = 0; i < this.V; i++)
            if (this.adj[i].length > 0 && visited[i] == false) return false;
 
          return true;
        }
 
        // A recursive function to do DFS starting from v. Used in isConnected();
        DFSUtil(v, visited) {
          // Mark the current node as visited and print it
          visited[v] = true;
 
          // Recur for all the vertices adjacent to this vertex
          for (let j in this.adj[v]) {
            let i = this.adj[v][j];
            if (!visited[i]) {
              this.DFSUtil(i, visited);
            }
          }
        }
 
        // Function that returns reverse (or transpose) of this graph
        // This function is needed in isSC()
        getTranspose() {
          let g = new Graph(this.V);
          for (let v = 0; v < this.V; v++) {
            // Recur for all the vertices adjacent to this vertex
            for (let j in this.adj[v]) {
              let i = this.adj[v][j];
              g.adj[i].push(v);
              g.in[v]++;
            }
          }
          return g;
        }
      }
      // This function takes an of strings and returns true
      // if the given array of strings can be chained to
      // form cycle
      function canBeChained(arr, n) {
        // Create a graph with 'alpha' edges
        let g = new Graph(CHARS);
 
        // Create an edge from first character to last character
        // of every string
        for (let i = 0; i < n; i++) {
          let s = arr[i];
          g.addEdge(
            s[0].charCodeAt() - "a".charCodeAt(),
            s[s.length - 1].charCodeAt() - "a".charCodeAt()
          );
        }
 
        // The given array of strings can be chained if there
        // is an eulerian cycle in the created graph
        return g.isEulerianCycle();
      }
 
      // Driver program to test above functions
 
      let arr1 = ["for", "geek", "rig", "kaf"];
      let n1 = arr1.length;
      canBeChained(arr1, n1)
        ? console.log("Can be chained")
        : console.log("Can't be chained");
 
      let arr2 = ["aab", "abb"];
      let n2 = arr2.length;
      canBeChained(arr2, n2)
        ? console.log("Can be chained")
        : console.log("Can't be chained");
         
        // This code is contributed by satwiksuman.

Output

Can be chained 
Can't be chained

Time Complexity: O(n*m) where n is max of sizes of arr1 and arr2 and m is maximum size word in arr1 or arr2.
Auxiliary space: O(max(n,m))

Find if an array of strings can be chained to form a circle | Set 2

GeeksforGeeks

Improve

Previous Article

Word Ladder (Length of shortest chain to reach a target word)

Tarjan's Algorithm to find Strongly Connected Components

Similar Reads

Find if an array of strings can be chained to form a circle | Set 2

Given an array of strings, find if the given strings can be chained to form a circle. A string X can be put before another string Y in a circle if the last character of X is the same as the first character of Y. Examples: Input: arr[] = {"geek", "king"} Output: Yes, the given strings can be chained. Note that the last character of first string is s

Find area of the larger circle when radius of the smaller circle and difference in the area is given

Given two integers r and d where r is the radius of the smaller circle and d is the difference of the area of this circle with some larger radius circle. The task is to find the area of the larger circle.Examples: Input: r = 4, d = 5 Output: 55.24 Area of the smaller circle = 3.14 * 4 * 4 = 50.24 55.24 - 50.24 = 5Input: r = 12, d = 3 Output: 455.16

Count of strings in Array A that can be made equal to strings in Array B by appending characters

Given two arrays of strings SearchWord[] and FindWord[]. The task is to check how many strings in FindWord[] can be formed after the following operations on as many strings as possible: Pick a string from SearchWord[].Add one English alphabet (that is not present in that string).Rearrange the string as you like.Note: Every alphabet in the SearchWor

Angle subtended by the chord to center of the circle when the angle subtended by the another equal chord of a congruent circle is given

Given are two congruent circles with two equal chords. The angle subtended to the center from the chord of one of the circles is given. The task is to find the angle subtended by the chord to the center of another circle.Examples: Input: z = 48 Output: 48 degrees Input: z = 93 Output: 93 degrees Approach: In triangle AOB and PXQ AO = PX(radii of co

Area of the circle that has a square and a circle inscribed in it

Given the side of a square that is kept inside a circle. It keeps expanding until all four of its vertices touch the circumference of the circle. Another smaller circle is kept inside the square now and it keeps expanding until its circumference touches all four sides of the square. The outer and the inner circle form a ring. Find the area of this

Program to calculate area of inner circle which passes through center of outer circle and touches its circumference

Given a circle C1 and it's a radius r1. And one another circle C2 whose passes through center of circle C1 and touch the circumference of circle C1. The task is to find out the area of circle C2. Examples: Input: r1 = 4Output:Area of circle c2 = 12.56Input: r1 = 7Output:Area of circle c2 = 38.465 Approach: Radius r2 of circle C2 is [Tex]\ r2 = r1/2

Equation of circle when three points on the circle are given

Given three coordinates that lie on a circle, (x1, y1), (x2, y2), and (x3, y3). The task is to find the equation of the circle and then print the centre and the radius of the circle. The equation of circle in general form is x² + y² + 2gx + 2fy + c = 0 and in radius form is (x - h)² + (y -k)² = r², where (h, k) is the centre of the circle and r is

Check if a circle lies inside another circle or not

Given two circles with radii and centres given. The task is to check whether the smaller circle lies inside the bigger circle or not. Examples: Input: x1 = 10, y1 = 8, x2 = 1, y2 = 2, r1 = 30, r2 = 10 Output: The smaller circle lies completely inside the bigger circle without touching each other at a point of circumference. Input :x1 = 7, y1 = 8

Find the count of sub-strings whose characters can be rearranged to form the given word

Given a string str, the task is to find the count of all the sub-strings of length four whose characters can be rearranged to form the word "clap".Examples: Input: str = "clapc" Output: 2 "clap" and "lapc" are the required sub-strings Input: str = "abcd" Output: 0 Approach: For every sub-string of length four, count the occurrences of the character

Count new pairs of strings that can be obtained by swapping first characters of pairs of strings from given array

Given an array arr[] consisting of N strings, the task is to find the pair of strings that is not present in the array formed by any pairs (arr[i], arr[j]) by swapping the first characters of the strings arr[i] and arr[j]. Examples: Input: arr[] = {"good", "bad", "food"}Output: 2Explanation:The possible pairs that can be formed by swapping the firs

Article Tags :

Practice Tags :