Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

Given an array arr of size N containing positive and negative integers. Arrange the array alternatively such that every non-negative integer is followed by a negative integer and vice-versa.

```
The number of positive integers and negative integers may not be equal. In such cases, add the extra integers at the end.
```

```
For array {4, -9, -2, 6, -8}, the output will be {-9, 4, -2, 6, -8}
For array {1, 2, 3, -5}, the output will be {-5, 1, 2, 3}
```

Detailed explanation

```
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first line of each test case or query contains an integer 'N' representing the size of the array (arr).
The second line contains 'N' single space-separated integers, representing the elements in the array.
```

```
For each test case, the output is “Valid” if the rearrangement is valid otherwise, “Invalid”, without quotes.
```

Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
For a single array, multiple solutions may be possible, just rearrange the array in any one possible way.
```

```
1 <= T <= 10
1 <= N <= 10^5
Sum of N over all test cases does not exceeds 10^5.
-(10^9) <= arr[i] <= (10^9)
Time limit: 1 second
```

```
1
4
-1 2 2 -5
```

```
-1 2 -5 2
```

```
2
5
-2 -3 -3 -6 -2
3
1 -1 -1
```

```
-2 -3 -3 -6 -2
-1 1 -1
```