New answers tagged

3

The problem does not have any $O(n)$ time algorithm. Note that it is easy to check in linear time if all the elements in the array are the same or not. However, to check if all the elements are district, the problem is known as Element distinctness problem. And, this problem has an $\Omega(n \log n)$ lower bound complexity. More technically, your problem can ...


1

A binary heap with $n$ elements can be built in time $O(n)$. If there was a (comparison based) sorting algorithm capable $A$ of sorting the elements in a heap in time $o(n \log n)$ then you could obtain a (comparison-based) sorting algorithm $A'$ that works for arbitrary sequences $S$ of $n$ elements. Algorithm $A'$ is as follows: Construct a heap $H$ from $...


0

First, we can see the rotation problem (as described in the question) as equivalent to: interchange of two blocks of elements which are at index-ranges $[0, d-1]$ and $[d, n-1]$. Let's call these blocks, with elements exactly as the original array $A$, as $B_1$ and $B_2$. As result of this interchange, the order of these blocks in $A$ should change from $(...


1

C and C++ are low-level languages that give the programmer precise control over the memory layout. Each object takes a constant amount of memory which is fully determined (on a given implementation) by its type. The sizeof operator lets programs know this size. An object may contain pointers. The data that the pointers points to, if any, is not part of the ...


2

An important observation is that an un-sorted array $A$ must contain at least one index $i$, such that $A[i+1]<A[i]$ (assuming we are sorting in ascending order). In particular, if you assume that the first $k$ elements are ordered (but the array is not fully ordered), then in the last $n-k$ elements you will have such a behavior, and in particular there ...


5

Denote the array by $A_1,\ldots,A_n$. If $A_i > A_{i+1}$ then at least one of the two elements is out of place. We scan the array, and each time we find such a pair, we remove both elements. In $O(n)$ time, we obtain a sorted subarray $B$ together with $O(1)$ many unsorted elements, forming a set $C$. We sort $C$ in $O(1)$ and merge it with $B$ in $O(n)$.


0

This is likely going to be dependent on what technology and libraries you use to program the GPU (PyTorch? TensorFlow? CUDA? BLAS? something else?), and thus seems likely to be out of scope here. Typically the data must be transferred/copied onto the GPU anyway, so I'd expect the structure of it in RAM only affects the time to transfer to the GPU's memory, ...


0

Index of $A_{i,j}$ in $1$-$D$ will be $\frac{i(i-1)}{2} + j$ assuming $1$ based indexing.


0

$O(n)$, since you still will go through the entire array. And yes, this is a linear search since $O(n)$ is linear.


0

(expanding on my comment) Technically No You need to be very careful here, as there is a difference between algorithmic time complexity and runtime. In the case you have described, the runtime may be O(n) but the algorithm itself is O(n+m). This is because, without your external constraints, the algorithm's time complexity cannot be determined without ...


2

Count the number of times each of the 5 new element is moved in the array: The areay is of length $n$, and thus each of the 5 elements move at most $n$ times. The place of all other elements is correct, and thus there is at most $5n$ swaps required to "correct" the array, hence $O(n)$ swaps.


11

Yes, since $n + m \leq 2n$ the algorithm is $O(n)$. However, you may wish to write $O(m + n)$ because it clearly shows which variables the algorithm depends on, and what each variable does to the complexity.


36

Yes: $n+m \le n+n=2n$ which is $O(n)$, and thus $O(n+m)=O(n)$ For clarity, this is true only under the assumption that $m\le n$. Without this assumption, $O(n)$ and $O(n+m)$ are two different things - so it would be important to write $O(n+m)$ instead of $O(n)$.


1

Given a line $L = b$, the distance from any point $(x, y)$ to $L$ is $\left| y - b\right|$. The sum of a distances for a set of points $S = \{(x_1, y_1), \dots, (x_n, y_n)\}$ is then $$\left| y_1 - b \right| + \cdots + \left| y_n - b \right|$$ which is minimized for which $b$?


-3

#include <stdio.h> int main() { int n1,n2,n3,i,j,k,count=0; int a[n1],b[n2],c[n3]; n1=sizeof(a)/sizeof(a[0]); n2=sizeof(b)/sizeof(b[0]); n3=sizeof(c)/sizeof(c[0]); printf("Enter the size of each array\n"); scanf("%d %d %d",&n1,&n2,&n3); printf("enter %d elements:\n",n1); for(i = 0; i < n1; i++) { scanf(&...


0

Notice that you increment $p$, whilst also decrementing $n$. Since your condition in the while loop is that p < n, then the while loop will only work for half the elements. Also, note that you delete the last $n/2$ values, since you modify them without first reading them.


1

We need to first find the length of array in long time as it is not given. Start with length as 1 and increase it as multiple of 2. Check whether element at length-1 position is positive or not. If so repeat steps 1 and 2. If not return the index position it will be the maximum size of the array. As it is mentioned beyond the maximum position element value ...


1

You can answer the first question with binary search. Lets consider you're now discussing the interval $[l, r]$, and $m = \frac{(l + r)}{2}$. If $A[m] = m$, you have found an answer and you shall stop the search. If $A[m] < m$, then the answer must be in the interval $[m + 1, r]$, because if $i \le m$, then $A[i] \le A[m] - (m - i) < m - (m - i) = i$ (...


Top 50 recent answers are included