CV - EDITORIAL

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Vivek Chauhan

Tester: Michael Nematollahi

Editorialist: Taranpreet Singh

DIFFICULTY:

Cakewalk.

PREREQUISITES:

None. Trying the problem would be enough.

PROBLEM:

Given a string S of length N, print the number of positions i such that i-th character is a consonant while i+1-th character is a vowel. The characters ‘a’, ‘e’, ‘i’, ‘o’, ‘u’.

EXPLANATION

The solution is to just check all positions i whether position i is a valid position or not. To check whether position i is valid, we need S[i] being a consonant and S[i+1] being a vowel. We can also see being a consonant as not being a vowel since each character can either be a vowel or a consonant.

This condition can be written as

 if !isVowel( S[i] ) and isVowel( S[i+1] ) ans++

Now, isVowel is a function which returns true when the character passed is a vowel. It can be checked using if-else condition or adding all vowels to set and checking if a character is present in a set of vowels.

Bonus Problem
Given a string S of length N, find the number of pairs of positions (a, b), a \leq b such that S[a] is consonant and S[b] is a vowel. N can be up to 10^5.

TIME COMPLEXITY

Time Complexity is O(N) per test case.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const int N = 105;
ll inf = 1e16;
ll mod = 1e9 + 7;

char en = '\n';
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
	if (n & 1)
	  res = (res * x) % mod;
	x = (x * x) % mod;
	n >>= 1;
  }
  return res;
}
bool isVowel(char c)
{
  return c=='a' or c=='e' or c=='i' or c=='o' or c=='u';
}

int32_t main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll t;
  cin>>t;

  while(t--)
  {
	ll n;
	cin>>n;
	string s;
	cin>>s;
	s='a'+s;
	ll res=0;
	for(ll i=1;i<s.length();i++)
	{
	  if(!isVowel(s[i-1]) && isVowel(s[i]))
	    res++;
	}
	cout<<res<<en;
  }
}
Tester's Solution 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define F first
#define S second

bool mark[200];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	mark['a'] = mark['e'] = mark['o'] = mark['i'] = mark['u'] = true;
	int te;	cin >> te;
	while (te--){
		int n, ans = 0; 
		string s; 
		cin >> n >> s;
		for (int i = 1; i < n; i++)
			if (mark[s[i]] && !mark[s[i-1]])
				ans++;
		cout << ans << "\n";
	}
	return 0;
}
Editorialist's Solution 
import java.util.*;
import java.io.*;
class CV{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), cnt = 0;
	    String s = n();
	    for(int i = 1; i< n; i++)
	        if(!isVowel(s.charAt(i-1)) && isVowel(s.charAt(i)))
	            cnt++;
	    pn(cnt);
	}
	boolean isVowel(char c){
	    switch(c){
	        case 'a':
	        case 'e':
	        case 'i':
	        case 'o':
	        case 'u':
	            return true;
	        default:return false;
	    }
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new CV().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to Share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

2 Likes