Design a DFA that accepts a string containing 3 aβs and 3 bβs
Problem Statement: Design a Definite Finite Automata for accepting the permutation of Three aβs and Three bβs over the input {a, b}
Input: S = βaaabbbβ
Output: Accepted
Explanation:
The input has three a and three b.Input: S = βabababaβ
Output: Accepted
Explanation:
The input has three a and three b.
To design a DFA we need to check the input character by character. These are a few steps that should be kept in mind while designing a DFA.
- Think of all most of the possible input that can be accepted (like, in this example, aaabbb, bbbaaa, ababab, abaabbβ¦etc).
- Create an initial transition state.
- Do transition on each input alphabet to other transition states.
- Reach a final state such that in each step the language used was accept(like, in this example, an equal number of a and b).
Designing steps:
Step 1: Create an initial state βAβ which is indicated by β>.
Step 2: Think of the possible string that can be aaabbb or bbbaaa which can occur by transition like,
- The transition of input βaβ from state βAβ to state βBβ
- The transition of input βaβ from state βBβ to state βCβ
- The transition of input βaβ from state βCβ to state βDβ
- The transition of input βaβ from state βDβ to dead state βQ2β
- The transition of input βbβ from state βDβ to state βEβ
- The transition of input βbβ from state βEβ to state βFβ
- The transition of input βbβ from state βFβ to state βGβ
- The transition of input βbβ from state βGβ to dead state βQ2β
Step 3: Now work on a possibility like bβs comes after two aβs for example aababb, aabbab.
- The transition of βbβ from state βCβ to state βJβ
- The transition of βaβ from state βJβ to state βEβ
- The transition of βbβ from state βJβ to state βMβ
- The transition of βaβ from state βMβ to state βFβ
- The transition of βbβ from state βMβ to state βPβ
The transition is shown in the diagram.
Step-4: Now thinking of the possibility that starts with βabaβ and then fulfills the condition of the given language. For this following transitions to be done:
- The transition of βbβ from state βBβ to state βIβ
- The transition of βaβ from state βIβ to state βJβ
Step-5: Now thinking of the possibility that starts with βabbβ and then fulfills the condition of the given language. For this following transitions to be done:
- The transition of βbβ from state βIβ to state βLβ
- The transition of βaβ from state βLβ to state βMβ
Step-6: Now there is a possibility that after reading one βaβ it reads all 3 bβs and then end execution by reading the remaining 2 aβs. For the transition of βbβ from state βLβ to βOβ.
Step-7: there is a possibility that it reads βaβ after reading one βbβ and then it reads any combination of βaβ and βbβ so that string contains 3 aβs and 3 bβs.For this transition of βaβ is done from stateβHβ to state βIβ.
Step-8: Now, think about the strings starts with two bβs and the go for any combination of string to get the desired result for this we do a transition of βaβ from stare βKβ to state βLβ.
Step-9: Now input alphabet βaβ of states D, E, F, G, and βbβ of states G, N, O, P are left for transitions.AS we have done all possibilities of the above language so the remaining transition will go to dead states βQ1β³ and Q2β.
- The transition of input βaβ from state βDβ to dead state βQ1β
- The transition of input βaβ from state βEβ to dead state βQ1β
- The transition of input βaβ from state βFβ to dead state βQ1β
- The transition of input βaβ from state βGβ to dead state βQ1β
- The transition of input βbβ from state βGβ to dead state βQ2β
- The transition of input βbβ from state βNβ to dead state βQ2β
- The transition of input βbβ from state βOβ to dead state βQ2β
- The transition of input βbβ from state βPβ to dead state βQ2β
Transition table of above DFA
STATES | INPUT (a) | INPUT (b) |
---|---|---|
β> A (initial state) | B | H |
B | C | I |
C | D | J |
D | Q2 (dead state) | E |
E | Q2 (dead state) | F |
F | Q2 (dead state) | G*(final state) |
G* (final state) | Q2 (dead state) | Q1 (dead state) |
H | I | K |
I | J | L |
J | E | M |
K | L | N |
L | M | O |
M | F | P |
N | O | Q1 (dead state) |
O | P | Q1 (dead state) |
P | G* (final state) | Q1 (dead state) |
Below is the implementation of the DFA:
C++
// C++ implementation of the // DFA of permutation of three // a's and three b's #include<bits/stdc++.h> using namespace std; // declaration of state functions void stateA(string),stateB(string),stateC(string),stateD(string); void stateE(string),stateF(string),stateG(string),stateH(string); void stateI(string),stateJ(string),stateK(string),stateL(string); void stateM(string),stateN(string),stateO(string),stateP(string); void stateQ1(string),stateQ2(string); // State A void stateA(string n) { if (n[0] == 'a' ) stateB(n.substr(1)); else if (n[0] == 'b' ) { stateH(n.substr(1)); } } // State B void stateB(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateC(n.substr(1)); else if (n[0] == 'b' ) stateI(n.substr(1)); } } // State C void stateC(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateD(n.substr(1)); else if (n[0] == 'b' ) stateJ(n.substr(1)); } } // State D void stateD(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateQ2(n); else if (n[0] == 'b' ) stateE(n.substr(1)); } } // State E void stateE(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateQ2(n); else if (n[0] == 'b' ) stateF(n.substr(1)); } } // State F void stateF(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateQ2(n.substr(1)); else if (n[0] == 'b' ) stateG(n.substr(1)); } } // State G void stateG(string n) { if (n.length() == 0) cout << "string Accepted" ; else { if (n[0] == 'a' ) stateQ2(n); else if (n[0] == 'b' ) stateQ2(n); } } // State H void stateH(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateI(n.substr(1)); else if (n[0] == 'b' ) stateK(n.substr(1)); } } // State I void stateI(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateJ(n.substr(1)); else if (n[0] == 'b' ) stateL(n.substr(1)); } } // State J void stateJ(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateE(n.substr(1)); else if (n[0] == 'b' ) stateM(n.substr(1)); } } // State K void stateK(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateL(n.substr(1)); else if (n[0] == 'b' ) stateN(n.substr(1)); } } // State L void stateL(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateM(n.substr(1)); else if (n[0] == 'b' ) stateO(n.substr(1)); } } // State M void stateM(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateF(n.substr(1)); else if (n[0] == 'b' ) stateP(n.substr(1)); } } // State N void stateN(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else if (n[0] == 'a' ) stateO(n.substr(1)); else if (n[0] == 'b' ) stateQ1(n); } // State Q void stateO(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateP(n.substr(1)); else if (n[0] == 'b' ) stateQ1(n); } } // State P void stateP(string n) { if (n.length() == 0) cout << "string Not Accepted" ; else { if (n[0] == 'a' ) stateG(n.substr(1)); else if (n[0] == 'b' ) stateQ1(n.substr(1)); } } // State Q1 void stateQ1(string n) { cout << "string Not Accepted" ; } // State Q2 void stateQ2(string n) { cout << "string Not Accepted" ; } int main() { string n = "abaabb" ; // call stateA // to check the input stateA(n); } |
Java
// Java implementation of the // DFA of permutation of three // a's and three b's import java.util.*; class GFG{ // State A static void stateA(String n) { if (n.charAt( 0 ) == 'a' ) stateB(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) { stateH(n.substring( 1 )); } } // State B static void stateB(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateC(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateI(n.substring( 1 )); } } // State C static void stateC(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateD(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateJ(n.substring( 1 )); } } // State D static void stateD(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateQ2(n); else if (n.charAt( 0 ) == 'b' ) stateE(n.substring( 1 )); } } // State E static void stateE(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateQ2(n); else if (n.charAt( 0 ) == 'b' ) stateF(n.substring( 1 )); } } // State F static void stateF(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateQ2(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateG(n.substring( 1 )); } } // State G static void stateG(String n) { if (n.length() == 0 ) System.out.print( "String Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateQ2(n); else if (n.charAt( 0 ) == 'b' ) stateQ2(n); } } // State H static void stateH(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateI(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateK(n.substring( 1 )); } } // State I static void stateI(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateJ(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateL(n.substring( 1 )); } } // State J static void stateJ(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateE(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateM(n.substring( 1 )); } } // State K static void stateK(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateL(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateN(n.substring( 1 )); } } // State L static void stateL(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateM(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateO(n.substring( 1 )); } } // State M static void stateM(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateF(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateP(n.substring( 1 )); } } // State N static void stateN(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else if (n.charAt( 0 ) == 'a' ) stateO(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateQ1(n); } // State Q static void stateO(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateP(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateQ1(n); } } // State P static void stateP(String n) { if (n.length() == 0 ) System.out.print( "String Not Accepted" ); else { if (n.charAt( 0 ) == 'a' ) stateG(n.substring( 1 )); else if (n.charAt( 0 ) == 'b' ) stateQ1(n.substring( 1 )); } } // State Q1 static void stateQ1(String n) { System.out.print( "String Not Accepted" ); } // State Q2 static void stateQ2(String n) { System.out.print( "String Not Accepted" ); } // Driver code public static void main(String[] args) { // Take String input String n = "abaabb" ; // Call stateA // to check the input stateA(n); } } // This code is contributed by pratham76 |
Python3
# Python3 implementation of the # DFA of permutation of three # a's and three b's # State A def stateA(n): if (n[ 0 ] = = 'a' ): stateB(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateH(n[ 1 :]) # State B def stateB(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateC(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateI(n[ 1 :]) # State C def stateC(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateD(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateJ(n[ 1 :]) # State D def stateD(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateQ2(n) elif (n[ 0 ] = = 'b' ): stateE(n[ 1 :]) # State E def stateE(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateQ2(n) elif (n[ 0 ] = = 'b' ): stateF(n[ 1 :]) # State F def stateF(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateQ2(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateG(n[ 1 :]) # State G def stateG(n): if ( len (n) = = 0 ): print ( "String Accepted" ) else : if (n[ 0 ] = = 'a' ): stateQ2(n) elif (n[ 0 ] = = 'b' ): stateQ2(n) # State H def stateH(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateI(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateK(n[ 1 :]) # State I def stateI(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateJ(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateL(n[ 1 :]) # State J def stateJ(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateE(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateM(n[ 1 :]) # State K def stateK(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateL(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateN(n[ 1 :]) # State L def stateL(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateM(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateO(n[ 1 :]) # State M def stateM(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateF(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateP(n[ 1 :]) # State N def stateN(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateO(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateQ1(n) # State Q def stateO(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateP(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateQ1(n) # State P def stateP(n): if ( len (n) = = 0 ): print ( "String Not Accepted" ) else : if (n[ 0 ] = = 'a' ): stateG(n[ 1 :]) elif (n[ 0 ] = = 'b' ): stateQ1(n[ 1 :]) # State Q1 def stateQ1(n): print ( "String Not Accepted" ) # State Q2 def stateQ2(n): print ( "String Not Accepted" ) # take string input n = "abaabb" # call stateA # to check the input stateA(n) |
C#
// C# implementation of the // DFA of permutation of three // a's and three b's using System; using System.Collections; class GFG{ // State A static void stateA( string n) { if (n[0] == 'a' ) stateB(n.Substring(1)); else if (n[0] == 'b' ) { stateH(n.Substring(1)); } } // State B static void stateB( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateC(n.Substring(1)); else if (n[0] == 'b' ) stateI(n.Substring(1)); } } // State C static void stateC( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateD(n.Substring(1)); else if (n[0] == 'b' ) stateJ(n.Substring(1)); } } // State D static void stateD( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateQ2(n); else if (n[0] == 'b' ) stateE(n.Substring(1)); } } // State E static void stateE( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateQ2(n); else if (n[0] == 'b' ) stateF(n.Substring(1)); } } // State F static void stateF( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateQ2(n.Substring(1)); else if (n[0] == 'b' ) stateG(n.Substring(1)); } } // State G static void stateG( string n) { if (n.Length == 0) Console.Write( "String Accepted" ); else { if (n[0] == 'a' ) stateQ2(n); else if (n[0] == 'b' ) stateQ2(n); } } // State H static void stateH( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateI(n.Substring(1)); else if (n[0] == 'b' ) stateK(n.Substring(1)); } } // State I static void stateI( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateJ(n.Substring(1)); else if (n[0] == 'b' ) stateL(n.Substring(1)); } } // State J static void stateJ( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateE(n.Substring(1)); else if (n[0] == 'b' ) stateM(n.Substring(1)); } } // State K static void stateK( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateL(n.Substring(1)); else if (n[0] == 'b' ) stateN(n.Substring(1)); } } // State L static void stateL( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateM(n.Substring(1)); else if (n[0] == 'b' ) stateO(n.Substring(1)); } } // State M static void stateM( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateF(n.Substring(1)); else if (n[0] == 'b' ) stateP(n.Substring(1)); } } // State N static void stateN( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else if (n[0] == 'a' ) stateO(n.Substring(1)); else if (n[0] == 'b' ) stateQ1(n); } // State Q static void stateO( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateP(n.Substring(1)); else if (n[0] == 'b' ) stateQ1(n); } } // State P static void stateP( string n) { if (n.Length == 0) Console.Write( "String Not Accepted" ); else { if (n[0] == 'a' ) stateG(n.Substring(1)); else if (n[0] == 'b' ) stateQ1(n.Substring(1)); } } // State Q1 static void stateQ1( string n) { Console.Write( "String Not Accepted" ); } // State Q2 static void stateQ2( string n) { Console.Write( "String Not Accepted" ); } // Driver code public static void Main ( string [] args) { // Take string input string n = "abaabb" ; // Call stateA // to check the input stateA(n); } } // This code is contributed by rutvik_56 |
Javascript
<script> // JavaScript implementation of the // DFA of permutation of three // a's and three b's // State A function stateA(n) { if (n[0] === "a" ) stateB(n.substring(1)); else if (n[0] === "b" ) { stateH(n.substring(1)); } } // State B function stateB(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateC(n.substring(1)); else if (n[0] === "b" ) stateI(n.substring(1)); } } // State C function stateC(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateD(n.substring(1)); else if (n[0] === "b" ) stateJ(n.substring(1)); } } // State D function stateD(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateQ2(n); else if (n[0] === "b" ) stateE(n.substring(1)); } } // State E function stateE(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateQ2(n); else if (n[0] === "b" ) stateF(n.substring(1)); } } // State F function stateF(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateQ2(nsubstring(1)); else if (n[0] === "b" ) stateG(n.substring(1)); } } // State G function stateG(n) { if (n.length === 0) document.write( "String Accepted" ); else { if (n[0] === "a" ) stateQ2(n); else if (n[0] === "b" ) staseQ2(n); } } // State H function stateH(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateI(n.substring(1)); else if (n[0] === "b" ) stateK(n.substring(1)); } } // State I function stateI(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateJ(n.substring(1)); else if (n[0] === "b" ) stateL(n.substring(1)); } } // State J function stateJ(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateE(n.substring(1)); else if (n[0] === "b" ) stateM(n.substring(1)); } } // State K function stateK(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateL(n.substring(1)); else if (n[0] === "b" ) stateN(n.substring(1)); } } // State L function stateL(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateM(n.substring(1)); else if (n[0] === "b" ) stateO(n.substring(1)); } } // State M function stateM(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateF(n.substring(1)); else if (s[0] === "b" ) stateP((n.Substr = ing(s))); } } // State N function stateN(n) { if (n.length === 0) document.write( "String Not Accepted" ); else if (n[0] === "a" ) stateO(n.substring(1)); else if (n[s] === "b" ) stateQ1(n); } // Stste Q function stateO(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateP(n.substring(1)); else if (n[0] === "b" ) staseQ1(n); } } // State P function stateP(n) { if (n.length === 0) document.write( "String Not Accepted" ); else { if (n[0] === "a" ) stateG(n.substring(1)); else if (n[0] === "b" ) stateQ1(nsSubstring(1)); } } // State Q1 function stateQ1(n) { document.write( "String Not Accepted" ); } // State Q2 function stateQ2(n) { document.write( "String Not Accepted" ); } // Driver code // Take string input var n = "abaabb" ; // Call stateA // to check the input stateA(n); </script> |
String Accepted
Time Complexity: O(N)
Auxiliary Space: O(N)