## Wave sort

Question 43. Re-arrange the elements in an array like a wave so that the values of the array alternately increase and decrease. The elements in the array are unique. For instance, if A = {50, 10, 20, 30, 40}, after re-arranging A can be {10, 30, 20, 50, 40} where in the value of consecutive elements alternately increases and decreases

This problem can be solved in O(nlogn) without additional memory as follows:

1. First sort the entire array in ascending order. So {50, 10, 20, 30, 40} becomes {10, 20, 30, 40, 50}

2. Then starting from index 1 in the array, swap the neighboring elements. So {10, 20, 30, 40, 50} becomes {10, 30, 20, 50, 40}

## C/C++

```
/*
a: array that has to be sorted so that the values in it alternatively increase
and decrease. The elements should be unique
length: number of elements in the array. should be >= 1
*/
void wave_sort(int a[], int length)
{
int i, temp;

/*Sort the elements in ascending order*/
qsort(a, length, sizeof(int), cmp_function);

/*Swap the alternate elements*/
for (i = 1; i < length - 1; i += 2) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}

```

## Java

```
/*
a: non-empty array that has to be sorted so that the values in it
alternatively increase and decrease. The elements should be unique
*/
public static void waveSort(int[] a) {
/*Sort the elements in ascending order*/
Arrays.sort(a);

/*Swap the alternate elements*/
for (int i = 1; i < a.length - 1; i += 2) {
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}

```

## Python

```
#a: non-empty list that has to be sorted so that the values in it
#	alternatively increase and decrease. The elements should be unique
def wave_sort(a) :
#Sort the elements in ascending order
a.sort()

#Swap the neighboring elements
for  i in range(1, len(a) - 1, 2):
a[i], a[i+1] = a[i+1], a[i]

```

## Search a sorted list with interspersed empty slots

Question 42. Consider the sorted array of strings A= {“”, “apple”, “”, “”, “ball”, “cat”, “”, “dog”, “”, “”, “”, “egg”, “”}. The array has empty strings interspersed in it. How will you efficiently search for strings in such an array?

We can use binary search to search the array of sorted strings. However since the array has empty strings in it, suppose we hit an empty string during binary search, we won’t know how to continue the search. To solve this problem we slightly modify the binary search and use the following strategy:

1. Binary search will occur between indexes low and high. If A[high] is an empty string, then we go on decrementing high till A[high] is a non-empty string. (Suppose we don’t find a non-empty string and we reach A[low], then all elements between low and high are empty strings. So we simply return indicating the search string was not found.)

2. We then find the mid element between low and high. If A[mid] is a non-empty string, then we proceed with the usual binary search. If A[mid] however is an empty string, then we go on incrementing mid till A[mid] is a non-empty string. Since A[high] already has a non-empty string, we will surely find a non-empty string when we keep incrementing mid.

## C/C++

```
/*
strings: sorted array of strings in which some of the strings can be empty ("")
num_strings: number of strings present (including empty strings)
x: string to be searched
Returns: index of x in the array strings if found, -1 otherwise
*/
int search(char *strings[], int num_strings, char *x)
{
int mid, result;
int low = 0;
int high = num_strings - 1;

while (low <= high) {
/*If we hit an empty string at position high, then keep decreasing
high till we get a non-empty string*/
while (low <= high && strcmp(strings[high], "") == 0) {
--high;
}

/*If we have only empty strings between low and high, then return
if (low > high)
return -1;
mid = (low + high) / 2;

/*If we get an empty element at mid, then keep incrementing mid.
We are guaranteed to find a non-empty string since strings[high]
is non-empty*/
while (strcmp(strings[mid], "") == 0)
mid = mid + 1;

/*Compare the mid element with the element being searched*/
result = strcmp(strings[mid], x);

if (result == 0) {
return mid;
} else if (result < 0) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}

```

## Java

```
/*
strings: sorted array of strings in which some of the strings can be empty ("")
x: string to be searched
Returns: index of x in the array strings if found, -1 otherwise
*/
public static int search(String[] strings, String x) {
int low = 0;
int high = strings.length - 1;

while (low <= high) {
/*If we hit an empty string at position high, then keep
decreasing high till we get a non-empty string*/
while (low <= high && strings[high] == "")
--high;

/*If we have only empty strings between low and high, then return
if (low > high)
return -1;

int mid = (low + high) / 2;

/*If we get an empty element at mid, then keep incrementing mid.
We are guaranteed to find a non-empty string since strings[high]
is non-empty*/
while (strings[mid] == "")
mid = mid + 1;

/*Compare the mid element with the element being searched*/
int result = strings[mid].compareTo(x);

if (result == 0) {
return mid;
} else if (result < 0) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}

```

## Python

```
#strings: sorted list of strings in which some of the strings can be empty ('')
#x: string to be searched
#Returns: index of x in the strings list if found, -1 otherwise
def search(strings, x) :
low = 0
high = len(strings) - 1

while (low <= high) :
#If we hit an empty string at position high, then keep decreasing
#high until we get a non-empty string
while (low <= high and strings[high] == '') :
high = high - 1

#If we have only empty strings between low and high, then return
if (low > high):
return -1

mid = (low + high) // 2

#If we get an empty element at mid, then keep incrementing mid.
#We are guaranteed to find a non-empty string since strings[high]
#is non-empty
while (strings[mid] == ''):
mid += 1

#Compare the mid element with the element being searched
if (strings[mid] == x) :
return mid
elif (strings[mid] < x) :
low = mid + 1
else :
high = mid - 1

return -1

```

## Find the first element larger than k in a sorted array

Question 41. Find the first element larger than k in a sorted array

Consider the sorted array A = {10, 20, 20, 30, 40, 50}. The first element larger than 25 is 30. In normal binary search, we search for a particular element and stop when we find the element. When we are trying to find the first element larger than k, k may not even exist in the array. So we instead use a modified form of binary search where we keep track of the first element larger than k as we search the array. The time complexity is O(logn). The code is given below

## C/C++

```
/*
a: sorted array containing elements in non-decreasing order
length: number of elements in the array
k: we are searching for the number immediately above k
Returns: the number immediately greater than k in the array if it exists,
MAX_INT otherwise
*/
int find_next_higher(int a[], int length, int k)
{
int low, high, mid, result;

low = 0;
high = length - 1;

result = MAX_INT;
while (low <= high) {
mid = (low + high) / 2;

if (a[mid] > k) {
result = a[mid]; /*update the result and continue*/
high = mid - 1;
} else {
low = mid + 1;
}
}

return result;
}

```

## Java

```
/*
a: sorted array containing elements in non-decreasing order
k: we are searching for the number immediately above k
Returns: the number immediately greater than k in the array if it exists,
MAX_INT otherwise
*/
public static int findNextHigher(int[] a, int k) {
int low = 0;
int high = a.length - 1;

int result = MAX_INT;
while (low <= high) {
int mid = (low + high) / 2;

if (a[mid] > k) {
result = a[mid]; /*update the result and continue*/
high = mid - 1;
} else {
low = mid + 1;
}
}

return result;
}

```

## Python

```
#a: sorted list containing elements in non-decreasing order
#k: we are searching for the number immediately above k
#Returns: the number immediately greater than k in the list if it exists,
#		MAX_INT otherwise
def find_next_higher(a, k) :
low = 0
high = len(a) - 1

result = MAX_INT
while (low <= high) :
mid = (low + high) // 2

if (a[mid] > k) :
result = a[mid] #update the result and continue
high = mid - 1
else :
low = mid + 1

return result

```

## Find the first occurrence of an element in a sorted array

Question 40. Find the first occurrence of a number in a sorted array

Consider the sorted array A = {10, 10, 20, 20, 30, 30, 30}. If we are asked to return the first occurrence of 30, then we return the index 4. If we are asked to return the first occurrence of a number not present in the array such as 15, then we return -1.

We can do this using modified binary search in O(logn). In normal binary search, we stop as soon as we find the element being searched. In the modified binary search, we continue the binary search if the found element is not the first occurrence of the element in the array. The code is given below

## C/C++

```
/*
a: array being searched
n: number of elements in array
x: element being searched
Return value: first position of x in a, if x is absent -1 is returned
*/
int find_first(int a[], int n, int x)
{
int start, end, mid;

start = 0;
end = n - 1;

while (start <= end) {
mid = (start + end) / 2;

if (a[mid] == x) {
if (mid == 0 || a[mid - 1] != x)
return mid;
else
end = mid - 1;

} else if (a[mid] > x) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}

```

## Java

```
/*
a: array being searched
x: element being searched
Return value: first position of x in a, if x is absent -1 is returned
*/
public static int findFirst(int[] a, int x) {
int n = a.length;
int start = 0;
int end = n - 1;

while (start <= end) {
int mid = (start + end) / 2;

if (a[mid] == x) {
if (mid == 0 || a[mid - 1] != x)
return mid;
else
end = mid - 1;

} else if (a[mid] > x) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}

```

## Python

```
#a: list being searched
#x: element being searched
#Return value: first position of x in a, if x is absent -1 is returned
def find_first(a, x) :
n = len(a)
start = 0
end = n - 1

while (start <= end) :
mid = (start + end) // 2

if (a[mid] == x) :
if (mid == 0 or a[mid - 1] != x):
return mid
else:
end = mid - 1

elif (a[mid] > x) :
end = mid - 1
else :
start = mid + 1

return -1

```

## Find max and min using least operations

Question 39. Find the maximum and minimum elements in an array using the least number of comparisons

In the simple approach, we will compare each element of the array with the maximum value and minimum value obtained so far. So for every element, we need 2 comparisons.

In the efficient approach, we pick all pairs of consecutive numbers in the array and first compare the numbers within each pair. Then we compare the highest in the pair with the maximum value and the lowest in the pair with the minimum value. So we need 3 comparisons for 2 elements instead of 4 comparisons needed by the simple approach.

Since we will be picking pairs of consecutive numbers, if we have odd number of elements in the array, the last element will be left unpaired. To avoid this problem, if we have odd elements, we will initialize the max value and the min value to the first element in the array and then go on picking pairs of numbers from the second element onwards.

## C/C++

```
/*a:input array
length: number of elements in array a
min_value: the minimum value is returned here
max_value: the maximum value is returned here*/
void find_min_max(int a[], int length, int *min_value, int *max_value) {
int i = 0;
*max_value = MIN_INT;
*min_value = MAX_INT;
if (length % 2 == 1) {
/*If there are odd number of elements, then initialize
max_value and min_value with a[0]*/
*max_value = *min_value = a[0];
i = 1;
}

for (; i < length; i += 2) {
if (a[i] > a[i+1]) {
if (a[i] > *max_value)
*max_value = a[i];
if (a[i+1] < *min_value)
*min_value = a[i+1];
} else {
if (a[i] < *min_value)
*min_value = a[i];
if (a[i+1] > *max_value)
*max_value = a[i+1];
}
}
}

```

## Java

```
/*a:input array
result: the minimum value is returned in result[0] and
the maximum value is returned in result[1]*/
public static void findMinMax(int[] a, int[] result) {
int length = a.length;
int maxValue = MIN_INT;
int minValue = MAX_INT;
int i = 0;
if (length % 2 == 1) {
/*If there are odd number of elements, then initialize
maxValue and minValue with a[0]*/
maxValue = minValue = a[0];
i = 1;
}

for (; i < length; i += 2) {
if (a[i] > a[i+1]) {
if (a[i] > maxValue)
maxValue = a[i];
if (a[i+1] < minValue)
minValue = a[i+1];
} else {
if (a[i] < minValue)
minValue = a[i];
if (a[i+1] > maxValue)
maxValue = a[i+1];
}
}
result[0] = minValue;
result[1] = maxValue;
}

```

## Python

```
#a: input list
#Returns: the minimum value and maximum value in list are returned
def find_min_max(a) :
length = len(a)
max_value = MIN_INT
min_value = MAX_INT

i = 0
if (length % 2 == 1) :
#If there are odd number of elements, then initialize
#max_value and min_value with a[0]
max_value = min_value = a[0]
i = 1

while ( i < length ) :
if (a[i] > a[i+1]) :
if (a[i] > max_value) :
max_value = a[i]
if (a[i+1] < min_value):
min_value = a[i+1]
else :
if (a[i] < min_value):
min_value = a[i]
if (a[i+1] > max_value):
max_value = a[i+1]

i += 2

return min_value, max_value

```

## Find the smallest and second smallest

Question 38. Find the smallest and second smallest numbers in an array

We can find the smallest and second smallest numbers in a single scan of the array. We will maintain another array called min_values for storing the 2 smallest numbers. min_values[0] will store the smallest value and min_values[1] will store the second smallest value. min_values[0] and min_values[1] are initialized to MAX_INT. As we traverse the main array, we do the following

– If the current element is smaller than min_values[0], then we move min_values[0] to min_values[1] and store the current element in min_values[0]

– If the current element is larger than min_values[0] but smaller than min_values[1], then we store the current element in min_values[1]

The code is given below:

## C/C++

```
/*
a:input array
length: number of elements in array a
min_value: the two smallest values will be returned here
*/
void find_two_smallest(int a[], int length, int min_value[])
{
int i;

min_value[0] = min_value[1] = MAX_INT;

for (i = 0; i < length; ++i) {
if (a[i] < min_value[0]) {
min_value[1] = min_value[0];
min_value[0] = a[i];
} else if (a[i] < min_value[1]) {
min_value[1] = a[i];
}
}
}

```

## Java

```
/*
a:input array
minValue: the two smallest values will be returned here
*/
public static void findTwoSmallest(int[] a, int[] minValue) {
minValue[0] = minValue[1] = MAX_INT;

for (int curVal : a) {
if (curVal < minValue[0]) {
minValue[1] = minValue[0];
minValue[0] = curVal;
} else if (curVal < minValue[1]) {
minValue[1] = curVal;
}
}
}

```

## Python

```
#a:input list
#Return value: the two smallest values will be returned
def find_two_smallest(a) :
length = len(a)

min_value = [MAX_INT, MAX_INT]

for  cur_val in a:
if (cur_val < min_value[0]) :
min_value[1] = min_value[0]
min_value[0] = cur_val
elif (cur_val  < min_value[1]) :
min_value[1] = cur_val

return min_value[0], min_value[1]

```

## Find maximum of two integers without if-else and comparison

Question 37. Find the maximum of 2 integers without using if-else or any other comparison operator

We can find the maximum of 2 integers without making use of if else or any comparison operator using the function below

## C/C++

```
/*Returns the maximum of x and y without using if-else and comparison*/
int find_max(int x, int y) {
int difference = x - y;
int sign_bit = 	(difference >> 31) & 0x1;
/*
Sign bit can be 0 or 1
If sign bit is 0, max = x - (0 * difference) = x
If sign bit is 1, max = x - (1 * (x-y)) = x - x + y = y
*/
int max = x  - (sign_bit * difference);
return max;
}

```

## Java

```
/*Returns the maximum of x and y without using if-else and comparison*/
public static int findMax(int x, int y) {
int difference = x - y;
int signBit = 	(difference >> 31) & 0x1;
/*
Sign bit can be 0 or 1
If sign bit is 0, max = x - (0 * difference) = x
If sign bit is 1, max = x - (1 * (x-y)) = x - x + y = y
*/
int max = x  - (signBit * difference);
return max;
}

```

## Python

```
#Returns the maximum of x and y without using if-else and comparison
# Maximum value of x and y should not exceed 31 bits
def find_max(x, y) :
difference = x - y
sign_bit = (difference >> 31) & 0x1

#Sign bit can be 0 or 1
#If sign bit is 0, max = x - (0 * difference) = x
#If sign bit is 1, max = x - (1 * (x-y)) = x - x + y = y
max_value = x  - (sign_bit * difference)
return max_value

```

First we compute the difference between x and y. Next we find the sign bit of the difference. In the 2’s complement notation, the most significant bit indicates the sign of the number. If the sign bit is 0, then the number is positive and if the bit is 1, then the number is negative.

If x >= y, then the difference x – y is positive and so the sign bit of the difference is 0.

If x < y, then the difference x – y is negative and sign bit of the difference is 1.

Then we compute max = x – (sign_bit * difference).

If x >= y, then sign_bit = 0 and max = x – (0 * difference) = x. So we return x as the maximum value

If x < y, then sign_bit = 1 and max = x - (1 * difference) = x - difference = x - (x - y) = y. So we return y as the maximum value

## Circular left shift and circular right shift on integer

Question 36. Implement circular shift left and circular shift right on an unsigned integer

Let n be the number of bits to shift. Let m be the total number of bits present in the integer. If we circular shift an integer m times then we get back the original integer. So the actual number of shifts we need to perform is n % m.

The functions for circular shift left (also called left shift rotate) and circular shift right (right shift rotate) are given below

## C/C++

```
/*
input: input value which has to be circularly shifted left
n: number of positions to shift
Return value: result after circularly left shifting input
*/
unsigned int circular_left_shift(unsigned int input, int n)
{
unsigned int size = sizeof(unsigned int) * 8;
unsigned int result;

n = n % size;
result = input << n | input >> (size - n);
return result;
}

/*
input: input value which has to be circularly shifted right
n: number of positions to shift
Return value: result after circularly right shifting input
*/
unsigned int circular_right_shift(unsigned int input, int n)
{
unsigned int size = sizeof(int) * 8;
unsigned int result;

n = n % size;
result = input >> n | input << (size - n);
return result;
}

```

## Java

```
/*
input: input value which has to be circularly shifted left
n: number of positions to shift
Return value: result after circularly left shifting input
*/
public static int circularLeftShift(int input, int n) {
int numBitsInInt = 32;
n = n % numBitsInInt;
int result = input << n | input >>> (numBitsInInt - n);
return result;
}

/*
input: input value which has to be circularly shifted right
n: number of positions to shift
Return value: result after circularly right shifting input
*/
public static int circularRightShift(int input, int n) {
int numBitsInInt = 32;
n = n % numBitsInInt;
int result = input >>> n | input << (numBitsInInt - n);
return result;
}

```

## Python

```
#value: input value which has to be circularly shifted left
#n: number of positions to shift
#Return value: result after circularly left shifting input value
def circular_left_shift(value, n) :
num_bits_in_int = 32
n = n % num_bits_in_int
mask = (1 << num_bits_in_int) - 1
result = (value << n) | (value >> (num_bits_in_int - n))
return result

#value: input value which has to be circularly shifted right
#n: number of positions to shift
#Return value: result after circularly right shifting input
def circular_right_shift(value, n) :
num_bits_in_int = 32
n = n % num_bits_in_int
mask = (1 << num_bits_in_int) - 1
result = (value >> n) | (value << (num_bits_in_int - n))
return result

```

## Copy bits from one integer to another

Question 35. Copy the bits between the specified start bit and end bit positions of one integer into another integer. For instance if source integer is 0xBBB and destination integer is 0xAEC and we copy the bits from 4 to 7 from source to destination, the result is 0xABC

Let the source integer be 0xBBB, destination integer be 0xAEC and we have to copy bits from position 4 to 7. The strategy we use is as follows:

1. Construct a mask (let’s call it ones mask) in which all the bits are initially set to 1. If we need to copy n bits and the total number of bits in the integer is m, then right shift the ones mask by (m-n). So if we need to copy 4 bits between bit 4 and bit 7, and total number of bits in integer is 32, we perform ones_mask >> (32 – 4). So ones_mask will have a value 0xF.

2. Left shift the ones mask to the starting position from where we have to copy the bits. The ones mask will now have 1’s from the start bit position to the end bit position. In this example, starting bit position is 4, so we perform (ones_mask << 4) = (0xF << 4) = 0xF0.

3. Construct a zeroes mask which is the complement of the ones mask. The zeroes mask will have 0’s from the start bit to the end bit. So if ones mask is 0xF0, then zeroes mask will be 0xFFFFFF0F.

4. AND the destination integer with the zeroes mask to clear out the bits in the destination from start bit to end bit. So if destination is 0xAEC, then 0xAEC & 0xFFFFFF0F will give 0xA0C

5. AND the source integer with the ones mask so that only the bits from start and end bit positions remain and the rest of the bits are cleared. If the source integer is 0xBBB, then 0xBBB & 0xF0 will give 0xB0

6. OR the source and destination. So 0xA0C | 0xB0 will give 0xABC

## C/C++

```
/*
dest: destination integer into which the bits have to be copied
src: source integer from which the bits have to be copied
end_pos: Most Significant bit position upto where the bits should be copied
start_pos: Least Significant bit position from where the bits should be copied
end_pos should be >= start_pos
Return value: result integer after copying bits from source to destination
*/
unsigned int copy_bits(unsigned int dest, unsigned int src,
unsigned int end_pos, unsigned int start_pos)
{
unsigned int num_bits_to_copy = end_pos - start_pos + 1;
unsigned int num_bits_in_int = sizeof(unsigned int) * 8;
unsigned int ones_mask = ~((unsigned int) 0); /*all ones*/

/*Use the bit-wise right shift operator to remove the excess 1's

/*Left shift the 1's to the starting position. ones_mask will contain 1's
from start_pos to end_pos*/

/*zeroes_mask will contain 0's from start_pos to end_pos*/

/*clear the bits in destination from start_pos to end_pos*/

/*retain the bits in source from start_pos to end_pos and clear the
remaining bits*/

/*copy the source bits into the destination*/
dest = dest | src;

return dest;
}

```

## Java

```
/*
dest: destination integer into which the bits have to be copied
src: source integer from which the bits have to be copied
endPos: Most Significant bit position upto where the bits should be copied
startPos: Least Significant bit position from where the bits should be copied
endPos should be >= startPos
Return value: result integer after copying bits from source to destination
*/
public static int copyBits(int dest, int src,  int endPos,  int startPos) {
int numBitsToCopy = endPos - startPos + 1;
int numBitsInInt = 32;

/*Use the bit-wise right shift operator to remove the excess 1's

/*Left shift the 1's to the starting position. onesMask will contain
1's from startPos to endPos*/

/*zeroesMask will contain 0's from startPos to endPos*/

/*clear the bits in destination from startPos to endPos*/

/*retain the bits in source from startPos to endPos and clear
the remaining bits*/

/*copy the source bits into the destination*/
dest = dest | src;

return dest;
}

```

## Python

```
#dest: destination integer into which the bits have to be copied
#src: source integer from which the bits have to be copied
#end_pos: Most Significant bit position upto where the bits should be copied
#start_pos: Least Significant bit position from where the bits should be copied
#	end_pos should be >= start_pos
#Return value: result integer after copying bits from source to destination
def copy_bits(dest,  src,  end_pos,  start_pos) :
num_bits_to_copy = end_pos - start_pos + 1
num_bits_in_int = 32
ones_mask = (1 << 32) - 1

#Use the bit-wise right shift operator to remove the excess 1's

#Left shift the 1's to the starting position. ones_mask will contain 1's
#from start_pos to end_pos

#zeroes_mask will contain 0's from start_pos to end_pos

#clear the bits in destination from start_pos to end_pos

#retain the bits in source from start_pos to end_pos and
#clear the remaining bits

#copy the source bits into the destination
dest = dest | src

return dest

```

## Compute parity bit

Question 34. Given an integer, compute the parity bit for the integer

There are two types of parity bit schemes

1. Even parity: if the total number of 1’s is odd, then the parity bit will be 1 to make the total number of 1’s (including the parity bit) even

2. Odd parity: if the total number of 1’s is even, then the parity bit will be 1 to make the total number of 1’s (including the parity bit) odd.

We will implement an even parity scheme here. We count the number of 1’s in the integer using the scheme described in problem 29

## C/C++

```
/*
x: input integer
Return value: parity bit, 1 if there are odd number of 1's, 0 otherwise
*/
unsigned int compute_parity(unsigned int x)
{
/*for each bit set to 1 in x, toggle the parity bit*/
unsigned int parity = 0;
while (x != 0) {
parity = parity ^ 1;
x = x & (x - 1);
}

return parity;
}

```

## Java

```
/*
x: input integer
Return value: parity bit, 1 if there are odd number of 1's, 0 otherwise
*/
public static int computeParity( int x) {
/*for each bit set to 1 in x, toggle the parity bit*/
int parity = 0;
while (x != 0) {
parity = parity ^ 1;
x = x & (x - 1);
}

return parity;
}

```

## Python

```
#x: input integer
#Return value: parity bit, 1 if there are odd number of 1's, 0 otherwise
def compute_parity(x):
#for each bit set to 1 in x, toggle the parity bit
parity = 0
while (x):
parity = parity ^ 1
x = x & (x - 1)

return parity

```