Ninja and Binary String Problem Statement

Ninja has a binary string S of size N given by his friend. The task is to determine if it's possible to sort the binary string S in decreasing order by removing any number of non-adjacent characters. Your help is needed to solve this challenge.

Input:

int T // number of test cases int N // size of the binary string for each test case string S // the binary string

Output:

Print "true" for each test case if the string can be sorted in decreasing order, otherwise "false".

Example:

Input:

2
5
10101
3
110

Output:

true
true

Constraints:

1

Question

Ninja and Binary String Problem Statement

Ninja has a binary string S of size N given by his friend. The task is to determine if it's possible to sort the binary string S in decreasing order by removing any number of non-adjacent characters. Your help is needed to solve this challenge.

Input:

int T  // number of test cases
int N  // size of the binary string for each test case
string S  // the binary string

Output:

Print "true" for each test case if the string can be sorted in decreasing order, otherwise "false".

Example:

Input:

Output:

true
true

Constraints:

1 <= T <= 5
1 <= N <= 10^4
Where T is the total number of test cases and N is the size of the given string.
Time limit: 1 sec

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
A binary string is a string which contains only '1' or '0' characters.
The order is not strictly decreasing.

Accepted Answer

Determine if a binary string can be sorted in decreasing order by removing non-adjacent characters.

Check if the count of '1's in the string is equal to the length of the string, in which case it can be sorted in decreasing order.
If there are multiple '0's between two '1's, they can be removed to sort the string in decreasing order.
If there are more '0's than '1's, it is not possible to sort the string in decreasing order.

Ninja and Binary String Problem Statement

Input:

Output:

Example:

Input:

Output:

Constraints:

Note:

Arcesium Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern