Chef and Chain Codechef Solution

Chef and Chain Codechef Solution: Chef had a hard day and want to play little bit. The game is called “Chain”. Chef has the sequence of symbols. Each symbol is either ‘‘ or ‘+‘. The sequence is called Chain if each two neighboring symbols of sequence are either ‘-+‘ or ‘+-‘.

For example sequence ‘-+-+-+‘ is a Chain but sequence ‘-+-+–+‘ is not.

Help Chef to calculate the minimum number of symbols he need to replace (ex. ‘‘ to ‘+‘ or ‘+‘ to ‘‘) to receive a Chain sequence.

Input

  • First line contains single integer T denoting the number of test cases.
  • Line of each test case contains the string S consisting of symbols ‘‘ and ‘+‘.

Output

  • For each test case, in a single line print single interger – the minimal number of symbols Chef needs to replace to receive a Chain.

Constraints

  • 1 ≤ T ≤ 7
  • 1 ≤ |S| ≤ 10^5

Subtasks

  • Subtask 1 ≤ |S| ≤ 101 ≤ T ≤ 7 Points: 20
  • Subtask 1 ≤ |S| ≤ 10001 ≤ T ≤ 7 Points: 30
  • Subtask 1 ≤ |S| ≤ 10^51 ≤ T ≤ 7Points: 50

Example

Input:
2
---+-+-+++
-------
Output:
2
3

Explanation

Example case 1.

We can change symbol 2 from ‘‘ to ‘+‘ and symbol 9 from ‘+‘ to ‘‘ and receive ‘-+-+-+-+-+‘.

Example case 2.

We can change symbols 2, 4 and 6 from ‘‘ to ‘+‘ and receive ‘-+-+-+-‘.

Chef and Chain  – CodeChef Solution in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		try
		{
		    Scanner sc=new Scanner(System.in);
		    int t=sc.nextInt();
		    while(t-->0)
		    {
		        String A=sc.next();
		        int c1=0;
		        int c2=0;
		        int i=0;
		        int len=A.length();
		        int f1=0,f2=1;
		        for(i=0;i<len;i++)
		        {
		            if(f1==0 && A.charAt(i)=='+')
		              c1++;
		            else if(f1==1 && A.charAt(i)=='-')
		            c1++;
		            if(f2==0 && A.charAt(i)=='+')
		            c2++;
		            else if(f2==1 && A.charAt(i)=='-')
		            c2++;
		            f1=(f1+1)%2;
		            f2=(f2+1)%2;
		        }
		    if(c1<c2)
		    System.out.print(c1);
		    else
		    System.out.print(c2);
		    System.out.print("\n");
		    }
		}
		catch(Exception ee)
		{
		}
	}
}

Chef and Chain   – CodeChef Solution in CPP

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;
        string s1(s);
        int countA = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (i == 0 || i % 2 == 0)
            {
                if (s[i] != '+')
                {
                    s[i] = '+';
                    countA++;
                }
            }
            else
            {
                if (s[i] != '-')
                {
                    s[i] = '-';
                    countA++;
                }
            }
        }
        int countB = 0;
        for (int i = 0; i < s1.size(); i++)
        {
            if (i == 0 || i % 2 == 0)
            {
                if (s1[i] != '-')
                {
                    s1[i] = '-';
                    countB++;
                }
            }
            else
            {
                if (s1[i] != '+')
                {
                    s1[i] = '+';
                    countB++;
                }
            }
        }
              cout << min(countA, countB) << endl;
    }
}

Chef and Chain   -CodeChef Solution in Python

t=int(input())
for i in range(t):
    s=input()
    c=d=0
    if(s.count('+')==len(s) or s.count('-')==len(s)):
        print(len(s)//2)
    else:
        for j in range(len(s)):
            if j%2== 0:
                if s[j]== "-":
                    d+=1
                else:
                    c+=1
            else:
                if s[j] == "+":
                    d+=1
                else:
                    c+=1
        print(min(c,d))

Disclaimer: The above Problem(Chef and Chain  ) is generated by CodeChef but the solution is provided by  Chase2learn.This tutorial is only for Educational and Learning purpose.

Leave a Comment