# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

**Setter:** kulyash

**Tester:** Harris Leung

**Editorialist:** hrishik85

# DIFFICULTY:

1009

# PREREQUISITES:

None

# PROBLEM:

The problem requires us to construct a binary string of length N such that the count of ‘01’ subsequences is equal to the count of the ‘10’. The string should have at least 1 occurrence of ‘0’ and ‘1’.

# EXPLANATION:

A subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. Kindly note the important point here that ‘the order of remaining elements’ cannot be changed.

Multiple solutions are possible for this string construction problem. The constraint also states that N >= 3.

## Hint 1

Can we create a few strings of smaller length to identify a pattern or logic to solve this question?

## Hint 2

Lets see a few example binary strings. Let us try and identify if they meet the condition or not.

## Hint 2a

100 - This string has 2 occurrences of subsequence ‘10’ and 0 occurrences of subsequence ‘01’. This does not meet the condition.

## Hint 2b

001 - This string has 2 occurrences of subsequence ‘10’ and 0 occurrences of subsequence ‘01’. This does not meet the condition.

## Hint 2c

10101 - This string has 3 occurrences of subsequence ‘10’ which are - **10**101, **1**01**0**1 and 10**10**1

It also has 3 occurrence of subsequence ‘01’ as follows - 1**01**01, 1**0**10**1** and 101**01**

Since the count of ‘01’s match the count of ‘10’s - 10101 is a valid string

## Hint 2d

1010 - This string has 3 occurrences of ‘10’ and 1 occurrence of ‘01’. This is not a valid string

## Hint 2e

111000 - This string has 9 occurrences of ‘10’ and 0 occurrences of ‘01’. This is not a valid string

## Hint 2f

111001 - This string has 6 occurrences of ‘10’ and 2 occurrences of ‘10’. This is not a valid string

## Hint 2g

110011 - This string has 4 occurrences of ‘10’ and 4 occurrences of ‘01’. This is a valid string

## Hint 2h

101010 - This string has 6 occurrences of ‘10’ and 3 occurrences of ‘01’. This is not a valid string

## Hint 2i

11011 - This string has 2 occurrences of ‘10’ and 2 occurrences of ‘01’. This is a valid string

## Hint 2j

01010 - This string has 3 occurrences of ‘10’ and 3 occurrences of ‘01’. This is a valid string

What do we observe from the above examples that can help us solve this problem?

## Hint 3

Note that the number of ‘1’s and ‘0’s do not need to be equal to get a valid string

## Hint 4

A simple way to solve this problem is to construct a string such that it has ‘1’s at the extreme end of the string and ‘0’s in its body. For example ‘1001’, ‘10001’, 100001’, ‘1000000001’. Since N >= 3, we can use this to construct a string of any length N >= 3.

# TIME COMPLEXITY:

Time complexity is O(N).

# SOLUTION:

## Tester's Solution

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+5;
int n;
ll a[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--){
int n;cin >> n;
cout << '0';
for(int i=1; i<=n-2 ;i++) cout << '1';
cout << "0\n";
}
}
```

## Editorialist's Solution

```
t=int(input())
for _ in range(t):
n=int(input())
s=str()
i=0
while i<(n-2):
s=s+'0'
i=i+1
s='1'+s+'1'
print(s)
```