Array Practice Questions

The "distance of A" is defined as the minimum number of elements that must be replaced to make the array sorted in non-decreasing order. This is equivalent to finding the longest non-decreasing subsequence (LNDS) and subtracting its length from the total length of the array.
Given array: $A = [2, 5, 3, 1, 4, 2, 6]$.
Length of array $n = 7$.
We need to find the LNDS of $A$.
Possible non-decreasing subsequences:

• $[2, 3, 4, 6]$ (length 4)
• $[2, 3, 6]$ (length 3)
• $[2, 5, 6]$ (length 3)
• $[2, 4, 6]$ (length 3)
• $[1, 2, 6]$ (length 3)
• $[1, 4, 6]$ (length 3)

Using dynamic programming to find LNDS:
Let $dp[i]$ be the length of the longest non-decreasing subsequence ending at index $i$.
$A = [2, 5, 3, 1, 4, 2, 6]$
$dp[0]$ (for 2) = 1
$dp[1]$ (for 5) = 1 (since $5 \not< 2$) + 1 = 1 if no preceding element is smaller; or $dp[0]+1$ if $5 \ge 2$. In this case $dp[1]=2$ as $5 \ge 2$.
$dp[2]$ (for 3): $3 \ge 2 \implies dp[0]+1 = 2$. Max length ending at 3 is 2 ([2,3]$).$dp[3]$(for 1): Max length ending at 1 is 1 ([1]$).
$dp[4]$ (for 4): $4 \ge 2 \implies dp[0]+1 = 2$. $4 \ge 3 \implies dp[2]+1=3$. Max length ending at 4 is 3 ([2,3,4]$).$dp[5]$(for 2):$2 \ge 1 \implies dp[3]+1 = 2$. Max length ending at 2 is 2 ([1,2]$).
$dp[6]$ (for 6): $6 \ge 2 \implies dp[0]+1=2$. $6 \ge 5 \implies dp[1]+1=3$. $6 \ge 3 \implies dp[2]+1=3$. $6 \ge 1 \implies dp[3]+1=2$. $6 \ge 4 \implies dp[4]+1=4$. $6 \ge 2 \implies dp[5]+1=3$. Max length ending at 6 is 4 ([2,3,4,6]$).

The maximum value in $dp$ is 4. So, the length of the LNDS is 4.
The distance of A = Total length - Length of LNDS
Distance = $7 - 4 = 3$.
This means we need to replace at least 3 elements to make the array sorted. For example, to get $[2, 3, 4, 6]$, we need to replace $5, 1, 2$ with appropriate values.
For example, keeping $2, 3, 4, 6$ as the LIS, the original array is $[2, 5, 3, 1, 4, 2, 6]$. We can replace 5, 1, 2 with 2, 3, 4 respectively to get $[2, 2, 3, 3, 4, 4, 6]$ (non-decreasing). This involves 3 changes.
===END_Q35===

To find both the minimum and maximum elements in an array of $n$ integers, a straightforward approach requires $2n-2$ comparisons (finding min in $n-1$ and max in $n-1$).
A more efficient method involves comparing elements in pairs, then finding the minimum among the smaller elements and the maximum among the larger elements. This approach requires $3\lceil n/2\rceil - 2$ comparisons in the worst case.
Thus, the lowest upper bound $t$ satisfies $t \le 2n-2$ and $t \ge 3\lceil n/2\rceil - 2$.
The option $t \gt n$ is also true as $3\lceil n/2\rceil - 2$ is generally greater than $n$ for $n \ge 2$.

In a recursive binary search on a sorted array of size $n$, the worst-case number of arithmetic operations occurs when the element is not found or is at the very end of the search path. Each step of binary search divides the search space by half. This process continues until the search space is reduced to a single element or becomes empty. The number of comparisons (and thus arithmetic operations for calculating midpoints) is logarithmic with respect to $n$. Specifically, it is $\Theta(\log_2 n)$.

Assuming 1-based row numbers $r \in \{1, \dots, 10\}$ and column numbers $c \in \{1, \dots, 4\}$, the stored value $r \times c = 10$. The valid pairs $(r, c)$ within the array bounds are $(5, 2)$ and $(10, 1)$.

The memory address for an element $x[r][c]$ in row-major order with 0-based indexing (where $r' = r-1$ and $c' = c-1$) is given by:
$Address = Base + (r' \times \text{columns} + c') \times \text{size}$
Given $Base = 1000$, $\text{columns} = 4$, and $\text{size} = 1$:

1. For $(5, 2)$, $r'=4$ and $c'=1$:
   $Address = 1000 + (4 \times 4 + 1) = 1017$
2. For $(10, 1)$, $r'=9$ and $c'=0$:
   $Address = 1000 + (9 \times 4 + 0) = 1036$

Thus, the locations are $1017$ and $1036$.

Initial array: $A = [10, 4, 7, 23, 67, 12, 5]$.
Pass 1: The element $4$ is compared and inserted before $10$, resulting in $[4, 10, 7, 23, 67, 12, 5]$.
Pass 2: The element $7$ is compared and inserted between $4$ and $10$, resulting in $[4, 7, 10, 23, 67, 12, 5]$.
Pass 3: The element $23$ is compared with the sorted sub-array $[4, 7, 10]$. Since $23 > 10$, it remains in its current position, resulting in $[4, 7, 10, 23, 67, 12, 5]$.
The array after the third pass is $[4, 7, 10, 23, 67, 12, 5]$.

To shift an array $A$ of $n$ integers left by $k$ positions cyclically in linear time without extra space, we process the array in cycles.

1. Outer Loop Condition ($i < \text{min}$): The variable $\text{min}$ tracks the smallest index visited. Since $\text{min}$ is initialized to $n$, the outer loop ensures we begin processing each cycle until all elements are covered.
2. Inner Loop Condition ($j \neq (n + i - k) \pmod n$): This condition ensures the inner loop terminates just before the index $(i-k) \pmod n$ is reached, which is the exact location that needs to receive the value stored in $\text{temp}$.
3. Cyclic Assignment ($A[(j + k) \pmod n]$): This performs the left shift by bringing the element from position $(j + k) \pmod n$ to position $j$.
4. Closing the Cycle: After the inner loop, temp (the original value of $A[i]$) is placed into the empty position $(n + i - k) \pmod n$.
5. Iteration ($i + 1$): The index $i$ is incremented to prepare for the next potential starting point of a cycle.

This logic effectively moves all elements through their respective cycles in $O(n)$ time.

The array is sorted, containing a sequence of 0s followed by 1s. The goal is to find the index of the first '1'. The most efficient method for searching in a sorted array is binary search.

The worst-case number of probes (comparisons) for a binary search on an array of size N is given by $\lceil \log_2(N+1) \rceil$.
For this problem, N = 31.
The number of probes is $\lceil \log_2(31+1) \rceil = \lceil \log_2(32) \rceil = 5$.

• S1: In segment 1, Y[i] is assigned X[0][i]. Since X[i][j] = i+j, X[0][i] = 0+i = i. So, Y[i] becomes i. In segment 2, Y[i] is assigned X[i][0], which is i+0 = i. So, Y[i] also becomes i. The final contents of Y are identical in both cases. S1 is correct.
• S2: C stores 2D arrays in row-major order. Segment 1 accesses X[0][0], X[0][1], X[0][2], .... These are adjacent elements within the first row and are therefore contiguous in memory. S2 is correct.
• S3: Segment 2 accesses X[0][0], X[1][0], X[2][0], .... This is a column-wise access. In row-major layout, these elements are separated by the length of a full row in memory and are not contiguous. S3 is incorrect.

Thus, only statements S1 and S2 are correct.

To find the average number of searches in a binary search with $N=11$ items, we count the comparisons required for each item based on its level in the binary search tree.
Level 1 has $1$ item (requiring $1$ comparison), Level 2 has $2$ items (requiring $2$ comparisons), Level 3 has $4$ items (requiring $3$ comparisons), and the remaining $4$ items are at Level 4 (requiring $4$ comparisons).
The total number of comparisons is calculated as: $(1 \times 1) + (2 \times 2) + (4 \times 3) + (4 \times 4) = 1 + 4 + 12 + 16 = 33$.
The average number of searches is the total comparisons divided by the number of items: $\frac{33}{11} = 3.00$.

The monitor dimensions range from $0$ to $100$, which implies a width of $101$ pixels per row.
Pixel coordinates $(x, y)$ are given as $(6, 10)$, where $x=6$ is the column index and $y=10$ is the row index.
For a row-major order frame buffer, the memory address is calculated using the formula:
$\text{Address} = y \times \text{Width} + x$
Substituting the given values:
$\text{Address} = 10 \times 101 + 6 = 1010 + 6 = 1016$

An array is defined as $k$-ordered if $A[i] \leq A[i+k]$ for all valid indices $i$. A known property of $k$-ordered arrays is that any element at index $i$ must be within $k-1$ positions of its index in a fully sorted (1-ordered) array. Given that the array is 2-ordered ($k=2$), any element is at most $2-1=1$ position away from its sorted position. Although the array is also 3-ordered (making it fully 1-ordered, or sorted), the constraint derived from the 2-ordered property defines the maximum displacement for such an array structure. Thus, the maximum displacement is $1$.

To find the total number of elements in a multidimensional array, we calculate the number of elements in each dimension using the formula \text{size} = \text{upper_bound} - \text{lower_bound} + 1.
For the first dimension $A(1:8)$, the size is $8 - 1 + 1 = 8$.
For the second dimension $A(-5:5)$, the size is $5 - (-5) + 1 = 11$.
For the third dimension $A(-10:5)$, the size is $5 - (-10) + 1 = 16$.
The total number of elements is the product of these dimensions: $8 \times 11 \times 16 = 1408$.

The base address of the array $A$ is $1120$, the size of each element is $3$ words, and the starting index is $1$. For a one-dimensional array starting at index $1$, the address of element $A[i]$ is calculated as:
$Address(A[i]) = Base + (i - 1) \times \text{Size}$
Substituting the given values $Base = 1120$, $i = 49$, and $\text{Size} = 3$:
$Address(A[49]) = 1120 + (49 - 1) \times 3$
$Address(A[49]) = 1120 + 48 \times 3$
$Address(A[49]) = 1120 + 144 = 1264$

In a sorted array of $n$ elements, any integer appearing more than $n/2$ times must occupy the middle index $\lfloor n/2 \rfloor$. To determine if this candidate integer $x = A[\lfloor n/2 \rfloor]$ meets the threshold, we must calculate its total frequency. This is achieved by using binary search to find the index of the first occurrence and the index of the last occurrence of $x$ in the array. Each binary search requires $\Theta(\log n)$ comparisons. Therefore, the frequency can be calculated in $\Theta(\log n)$ time, making the overall complexity $\Theta(\log n)$.

To determine both the maximum and minimum of $n$ numbers efficiently, where $n$ is an even number, an optimized algorithm can be used.

1. Initialize: Compare the first two elements of the array. This takes 1 comparison. Assign the smaller to min_val and the larger to max_val.
2. Process Remaining Elements: The remaining $n-2$ elements are processed in pairs. Since $n$ is even, $n-2$ is also even, so there are $(n-2)/2$ pairs.
3. For each pair $(a, b)$:
   • Compare $a$ and $b$ to find the smaller and the larger of the two (1 comparison).
   • Compare the larger of $a, b$ with max_val (1 comparison). Update max_val if necessary.
   • Compare the smaller of $a, b$ with min_val (1 comparison). Update min_val if necessary.
   • This process takes 3 comparisons for every pair of elements.

Total comparisons needed:
$1 \text{ (for the initial pair)} + 3 \times \frac{n-2}{2} \text{ (for the remaining pairs)}$
$= 1 + \frac{3n - 6}{2}$
$= \frac{2 + 3n - 6}{2}$
$= \frac{3n - 4}{2}$
$= 1.5n - 2$
Since an algorithm exists that can find both the maximum and minimum using exactly $1.5n - 2$ comparisons (and this is known to be the optimal lower bound as well), it is true that "At most $1.5n - 2$ comparisons are needed."

To solve the problem, we transform the condition $\sum_{k=i}^j a_k = \sum_{k=i}^j b_k$ by defining $d_k = a_k - b_k$. The condition becomes $\sum_{k=i}^j d_k = 0$.
By defining prefix sums $S_m = \sum_{k=1}^m d_k$ with $S_0 = 0$, the condition simplifies to $S_j - S_{i-1} = 0$, or $S_j = S_{i-1}$ for indices $0 \le i-1 < j \le n$.
Finding the largest span length $j - i + 1$ is equivalent to maximizing $j - (i-1)$ such that $S_j = S_{i-1}$.
Since the values of $S_m$ range between $-n$ and $n$, we can store the first occurrence of each value in an array of size $2n+1$ during a single pass.
For each $S_j$, we check if it has been seen before; if so, we update the maximum span. This entire process takes $\Theta(n)$ time and $\Theta(n)$ space.

An element $X[i]$ is a leader if $X[i] > \max(X[i+1], X[i+2], \dots, X[n-1])$. By iterating from right to left, we maintain a variable $max\_so\_far$ initialized to $-\infty$. For each element $X[i]$, if $X[i] > max\_so\_far$, then $X[i]$ is a leader, and we update $max\_so\_far = X[i]$. This approach requires only a single scan through the array, resulting in a linear time complexity of $\Theta(n)$. Conversely, a left-to-right pass would require comparing each element with all subsequent elements, resulting in a suboptimal $\Theta(n^2)$ time complexity. Thus, the right-to-left pass is the optimal method.

To track the frequency of scores strictly above $50$, we are interested in the integer range $[51, 100]$. The number of distinct scores to be tracked is calculated as $100 - 51 + 1 = 50$. An array of size $50$ is the most space-efficient data structure, where an index $i$ (for $0 \le i < 50$) can store the frequency of the score $(i + 51)$. Consequently, options B, C, and D are either unnecessarily large or irrelevant for storing exactly 50 frequency counts.

The merged array $c$ contains $2n$ elements, where $c[2i]$ is the $(2i+1)$-th smallest element. Given $a[i] \geq b[i]$, we analyze the number of elements less than or equal to $b[i]$ and $a[i]$:

1. For $b[i]$: Since $a[i] \geq b[i]$, the number of elements in $a$ smaller than $b[i]$ is at most $i$. Since there are exactly $i$ elements in $b$ smaller than $b[i]$ (namely $b[0], \dots, b[i-1]$), the total number of elements strictly less than $b[i]$ is at most $i+i = 2i$. Thus, the $(2i+1)$-th element, $c[2i]$, must be $\geq b[i]$, making statement II true.
2. For $a[i]$: There are $i+1$ elements in $a$ less than or equal to $a[i]$ ($a[0], \dots, a[i]$). Since $b[i] \leq a[i]$, all $i+1$ elements $b[0], \dots, b[i]$ are also $\leq a[i]$. Thus, there are at least $(i+1) + (i+1) = 2i+2$ elements $\leq a[i]$. Therefore, the $(2i+1)$-th element, $c[2i]$, must be $\leq a[i]$, making statement III true.
3. Statements I and IV do not hold in all cases, as demonstrated by the counterexample $a=[10, 20]$ and $b=[5, 6]$ with $i=1$, where $c[2]=10$. Here, $10 \geq 20$ (I) and $10 \leq 6$ (IV) are both false.