# GROUPS - Editorial

Setter:
Tester: Felipe Mota
Editorialist: Taranpreet Singh

Simple

None

# PROBLEM

There are N seats in a row, each may either be empty, denoted by ‘0’, or occupied, denoted by ‘1’. People seated on consecutive seats become friends. Find the number of groups of friends.

# QUICK EXPLANATION

• The number of groups of friends is the number of blocks consisting of consecutive '1’s. So we need to count the number of segments consisting entirely of ones which cannot be extended.
• The number of segments can be found by splitting given string at each occurrence of ‘0’ and counting the number of non-empty splits.

# EXPLANATION

Interpreting story, we have a binary string of N characters and we need to find the number of segments of 1s in string.

One naive way would be to split the string at every occurrence of 0, and then count the number of non-empty strings. We can see that everytime we get a non-empty split, it must consist of 1s only, which represent one group of friends.

For example: S = `00101100111` leads to splits `"", "1", "11", "", "111"`. Among these, only three are non-empty, hence there are only three groups of friends.

This can be implemented to execute in O(|S|) and sufficient to get AC, but can we simplify implementation more? The answer is YES.

### Optional Observation

What we can notice is that every group ends either leads to substring `10` to appear in string, or `1` at the end of string. This happens because either a group is occupying all seats till end of the row, or there’s atleast one empty seat just after the group.

If we add another empty seat at end of the row, it wouldn’t affect the answer.

Hence, after adding an empty seat (or a ‘0’) at end of row (string), the number of group of friends is exactly the number of occurrences of `10` in resulting string.

No need of splitting strings anymore.

# TIME COMPLEXITY

The time complexity is O(|S|) per test case.
The memory complexity is O(|S|) per test case.

# SOLUTIONS

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007

int main(){
FIO;
int t,n,k,i,j;
string s;
cin >> t;
while(t--){
cin >> s;
s=s;
j=0;
char prv='0';
for(char c:s){
if(prv=='0' && c=='1')
j++;
prv=c;
}
cout << j << "\n";
}
return 0;
}
``````
Tester's Solution
``````#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
while(t--){
for(auto c : s)
assert(c == '0' || c == '1');
int ans = 0, n = s.size();
for(int i = 0, j = 0; i < n; i = j){
while(j < n && s[i] == s[j]) j++;
if(s[i] == '1') ans += 1;
}
cout << ans << '\n';
}
return 0;
}
``````
Editorialist's Solution
``````import java.util.*;
import java.io.*;
class GROUPS{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
String S = n();
S += "0";
int groupCount = 0;
for(int i = 0; i+1< S.length(); i++)
if(S.charAt(i) == '1' && S.charAt(i+1) == '0')
groupCount++;
pn(groupCount);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
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 GROUPS().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());}

StringTokenizer st;
}

}

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

String nextLine() throws Exception{
String str = "";
try{