Associate Software Engineer

There is a person named Bob who is the mayor of a state. He wants to find the maximise number of vehicles that can be registered in his state.

A vehicle normally has a registration number like ST 01 AB 1234. Each registration number has four parts, separated by spaces. The first part has two letters common for all cars in the state. The next two-digit number is the number of the district where the car is registered within the state. It is always two digits and may have a leading zero. After that, the next part consists of two letters (AB), with each letter selected from a range, denoting the series and the last part is a 4-digit number this will always be four digits, even if it has leading zeros).

The entire registration number is unique to each vehicle. You have been given the number of districts in the state, a range of letters to be used in the series and a set of digits that can be used for forming a vehicle registration number.

Your task is to find the maximum number of vehicles that can be registered in Bob’s state.

Note :

1. No two vehicles can have the same registration number. 
2. Two registration numbers are said to be different if they have at least a different character or a digit at the same location. For eg. DL 05 AC 1234 and DL 05 AC 1235 are different, DL 05 AC 1234 and DL 05 AB 1234 are different registration numbers. 
3. All the cars will have the same first two characters as they have to be registered in the same state.
4. The numbering of the districts in the state starts from ‘1’ (which will obviously be written as 01 in registration number).

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.

Note:

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

For Example:

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}