DYZIO - Dyzio - SPOJ Solution C++

➤  Problem Link : DYZIO 

👉 Hint : Recursion

 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

int ans=-1;
unordered_map<int,int> mp;
void Recur(string s,int depth,int &cuts,int &i)
{

    if(i==s.length())
        return;
	if(mp.find(depth)==mp.end())
		mp[depth]=cuts;
	ans=max(ans,depth);
	if(s[i]=='1')
	{
		cuts++;
		i++;
		Recur(s,depth+1,cuts,i);
		Recur(s,depth+1,cuts,i);
	}
	else
	    i++;

}

int main()
{
	int n;
	string s;
	while(scanf("%d",&n)!=EOF)
	{
		mp.clear();
        int cuts=0,i=0;
        ans=-1;
		cin>>s;
		Recur(s,0,cuts,i);
		cout<<mp[ans]<<endl;
	}
}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.