Chef and Chain Codechef Solution

April 14, 2023March 21, 2023 by admin

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.

Table of Contents

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| ≤ 10, 1 ≤ T ≤ 7 Points: 20

Subtask 1 ≤ |S| ≤ 1000, 1 ≤ T ≤ 7 Points: 30
Subtask 1 ≤ |S| ≤ 10^5, 1 ≤ 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.