Broken Telephone Codechef Solution

Hello Programmers In this post, you will know how to solve the Broken Telephone Codechef Solution.

Ezoicreport this adBroken Telephone Codechef Solution
Broken Telephone Codechef Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

Chef is judging a game called “Broken telephone”. There are total N players taking part in the game. They are all sitting in a line. In the start of the game, first player is given a secret message written on a sheet of paper. Then they keep sending the message by whispering it to the player sitting immediate right to one and so on until it reaches the last person.

Finally, the message received by the last player is compared with the message said by first player. If these messages aren’t equal, there is someone who has misheard the message or whispered it wrongly to the next player. If messages is equal, then the players win and receive a tasty chocolate.

Note that first player receives the message on a sheet of paper, thus he cannot mishear it.

As Chef wants to be sure that every player has fulfilled his/ her role in the game, so he asks everyone to state their received messages after the end of the game. You are given an array A of N integers denoting messages received by each person.

Please help Chef to find the number of players that could mishear the message or whisper it wrongly.

Input

  • The first line of the input contains an integer T denoting the number of test cases.
  • The first line of each test case contains a single integer N denoting the number of players
  • The second line contains N space-separated integers A1A2, …, AN denoting the messages of players.

Output

  • For each test case, output a single line containing an integer corresponding to the number of players that could mishear the message or whisper it wrongly.

Constraints and Subtasks

  • 1 ≤ T ≤ 5
  • 1 ≤ Ai ≤ 109

Subtask 1: 40 points

  • 2 ≤ N ≤ 103

Subtask 2: 60 points

  • 2 ≤ N ≤ 105

Sample Input 1 

3
7
1 1 1 3 3 3 2
5
1 3 1 1 1
4
5 5 5 5

Sample Output 1 

4
3

Explanation

  • Example 1: The 3-rd4-th6-th and 7-th player could mishear the message or whisper it wrongly.
  • Example 2: First 3 players could mishear the message or whisper it wrongly.

Ezoicreport this adBroken Telephone CodeChef Solution in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
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)
		    {
		        int n=sc.nextInt();
		        int ar[]=new int[n];
		        int a;
		        int i;
		        for(i=0;i<n;i++)
		        {
		            ar[i]=sc.nextInt();
		        }
		        a=0;
		        int p=-1;
		        i=1;
		        while(i<n)
		        {
		            if(ar[i]==ar[i-1])
		              {
		                  p=-1;
		                  i++;
		                  continue;
		              }
		              a+=1;
		              if(p==-1)
		              {
		                  a+=1;
		              }
		              p=1;
		              i++;
		        }
		        System.out.print(a);
		        System.out.print("\n");
		    }
		}
		catch(Exception ee)
		{
		}
	}
}
Ezoicreport this ad

Broken Telephone CodeChef Solution in CPP

#include <bits/stdc++.h>
#include<stack>
#include<array>
#include<vector>
#include<deque>
#include<algorithm>
#define ll long long int
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
int gcd(int a,int b)//b>=a
{
    if(a==0)
        return b;
    return gcd(b%a,a);
}
bool isprime(int x)
{
    if(x==2 || x==3)
        return true;
    else
    {
        for(int i=2;i<=sqrt(x);i++)
        {
            if(x%i==0)
                return true;
        }
        return false;
    }
}
ll numoffactors(ll x)//except 1 and itself considered
{
    ll i,c=0;
    for(i=2;i<=x/2;i++)
    {
        if(x%i==0)
            c++;
    }
    return c;
}
ll factorial(ll x)
{
    if(x==1)
        return 1;
    return x*factorial(x-1);
}
ll reversenumber(ll x)
{
    ll rem,rev=0;
    while(x!=0)
    {
        rem=x%10;
        rev=rev*10+rem;
        x/=10;
    }
    return rev;
}
ll combination(ll n,ll r)
{
    if(r==0)
        return 1;
    if(r==1)
        return n;
    if(r==2)
        return (n*(n-1)/2);
    ll x;
    x=factorial(n)/(factorial(r)*factorial(n-r));
    return x;
}
bool isarmstrong(ll x)
{
    ll temp=x,s=0;
    while(x!=0)
    {
        s+=pow((x%10),3);
        x/=10;
    }
    if(temp==s)
        return true;
    return false;
}
bool ispalindrome(string s)
{
    int i,l=s.length();
    for(i=0;i<l;i++)
    {
        if(s[i]!=s[l-i-1])
            return false;
    }
    return true;
}
void solve()
{
    ll n,i,c=0,flag;
    cin>>n;
    ll a[n];
    for(i=0;i<n;i++)
        cin>>a[i];
    if(n==2)
    {
        if(a[0]!=a[1])
        {
            cout<<2;
            return;
        }
        else
        {
            cout<<0;
            return;
        }
    }
    for(i=1;i<n;i++)
    {
        if(a[i]!=a[i-1])
        {
            if(flag==1)
                c++;
            else
            {
                c+=2;
                flag=1;
            }
        }
        else
            flag=0;
    }
    cout<<c;
}
int main() {
    ll t;
    cin>>t;
    while(t--)
    {
        solve();
        cout<<"\n";
    }
	return 0;
}

Broken Telephone CodeChef Solution in Python

t=int(input())
for p in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    lst=[]
    for i in range(1,n):
        if a[i]!=a[i-1]:
            lst.append(i)
            lst.append(i-1)
    d=set(lst)
    h=list(d)
    print(len(h))

Disclaimer: The above Problem (Broken Telephone) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Bear and Ladder Codechef Solution

Sharing Is Caring

Leave a Comment

Ezoicreport this ad