83
You have at least two options, depending on what problem you want to solve.
If you want innocent readers of your code to not get the answers inadvertently, or you at least want to make it a bit difficult so that users are not tempted, you can encrypt the solutions and store the key as part of your code, perhaps a result of some computation (to make it even ...
45
Here is the answer which elaborates upon the algorithm from the paper linked by Joe: http://arxiv.org/abs/0805.1598
First let us consider a $\Theta(n \log n)$ algorithm which uses divide and conquer.
1) Divide and Conquer
We are given
$$a_1, a_2, \dots , b_1, b_2, \dots b_n$$
Now to use divide and conquer, for some $m = \Theta(n)$, we try to get the ...
44
Fixed-size queues are often implemented using what some people call circular buffers. If you remove the protection against it being full, you get the desired behaviour.
Of course, no actual pushing will happen in the array -- that would be too expensive -- but it will look like it from the outside.
31
No, it depends on your application. The measures of sortedness are often refered to as measures of disorder, which are functions from $N^{<N}$ to $\mathbb{R}$, where $N^{<N}$ is the collection of all finite sequences of distinct nonnegative integers. The survey by Estivill-Castro and Wood [1] lists and discusses 11 different measures of disorder in the ...
31
I see four main ways to solve this problem, with different running times:
$O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes linear time. You carry out $n$ deletions; therefore, this algorithm takes quadratic time.
$O(n \: log \: n)$ solution: sort the arrays beforehand; then, perform a ...
28
You have two three options:
Keep the answers separate from the rest of the source code
If you want your code to be open source, however don't want the answers to be open source, then you open source the code for the application without the questions & answers, with the questions & answers being a separate closed source "plugin" or data file. Your ...
27
The array indexing operation a[i] gains its meaning from the following features of C
The syntax a[i] is equivalent to *(a + i). Thus it is valid to say 5[a] to get at the 5th element of a.
Pointer-arithmetic says that given a pointer p and an integer i, p + i the pointer p advanced by i * sizeof(*p) bytes
The name of an array a very quickly devolves to a ...
26
The solution in fade2black's answer is the standard one, but it uses $O(n)$ space. You can improve this to $O(1)$ space as follows:
Let the array be $A[1],\ldots,A[n]$. For $d=1,\ldots,5$, compute $\sigma_d = \sum_{i=1}^n A[i]^d$.
Compute $\tau_d = \sigma_d - \sum_{i=1}^{n-5} i^d$ (you can use the well-known formulas to compute the latter sum in $O(1)$). ...
25
We count the number of array element reads and writes. To do bubble sort, you need $1 + 4n$ accesses (the initial write to the end, then, in the worst case, two reads and two writes to do $n$ swaps). To do the binary search, we need $2\log n + 2n + 1$ ($2\log n$ for binary search, then, in the worst case, $2n$ to shift the array elements to the right, then 1 ...
22
You could create an additional array $B$ of size $n$. Initially set all elements of the array to $0$. Then loop through the input array $A$ and increase $B[A[i]]$ by 1 for each $i$. After that you simply check the array $B$: loop over $A$ and if $B[A[i]] > 1$ then $A[i]$ is repeated. You solve it in $O(n)$ time at the cost of memory which is $O(n)$ and ...
18
I'm pretty sure I've found an algorithm that does not rely on number theory or cycle theory. Note that there are a few details to work out (possibly tomorrow), but I'm quite confident they will work out. I handwave as I'm supposed to be sleeping, not because I'm trying to hide problems :)
Let A be the first array, B the second, |A| = |B| = N and assume N=2^...
16
The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is:
total, such that for any values $a$ and $b$, $a \oplus b$ is defined and of the same type (or at least of some appropriate supertype of it, for which the ...
15
This is a very general trick, which can be used for other purposes than hashing. Below I give an implementation (in pseudo-code).
Let three uninitialized vectors $A$, $P$ and $V$ of size $n$ each. We will use these to do the operations requested by our data structure. We also maintain a variable $pos$. The operations are implemented as following:
init:
...
15
Arrays are simply laid out as contiguous chunks of memory. An array access such as a[i] is converted to an access to memory location addressOf(a)+i. This the code a[-1] is perfectly understandable, it simply refers to the address one before the start of the array.
This may seem crazy, but there are many reasons why this is allowed:
it is expensive to check ...
15
If you don't know anything about the contents of the matrix (such as some kind of monotonicity property), linear time is the best you can do for a one-off search with a deterministic algorithm by a simple adversary argument: if you don't look at everything, then you can't distinguish between the cases where the maximum component is/isn't one of the ones you ...
15
I'd post this as a comment on Tobi's answer, but I don't have the reputation yet.
As an alternative to calculating the sum of each list (especially if they are large lists or contain very large numbers that might overflow your data type when summed) you can use xor instead.
Just calculate the xor-sum (i.e. x[0]^x[1]^x[2]...x[n]) of each list and then xor ...
14
$\small \texttt{find-min}$ (resp. $\small \texttt{find-max}$), $\small \texttt{delete-min}$ (resp. $\small \texttt{delete-max}$) and $\small \texttt{insert}$ are the three most important operations of a min-heap (resp. max-heap), and they usually have complexity of $\small \mathcal{O}(1)$, $\small \mathcal{O}(\log n)$ and $\small \mathcal{O}(\log n)$ ...
14
Element = Sum(Array2) - Sum(Array1)
I sincerely doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps.
If the number of added elements is more than one, this won't work.
My answer has the same run time complexity for best, worst, and average case,
EDIT
After some thinking, ...
12
By a simple "adversary argument", you have to check each element (in some way): Suppose you have missed some element $x$ and get an answer "The sum is even": the adversary can modify $x$ (if it's odd, make it even; if it's even, make it odd), which will change the correct result but not your computation.
The adversary argument tells that in theory you have ...
11
A note on methodology
I thought a bit about this problem, and came to a solution. When I read Saeed Amiri's answer, I realized that what I came up with was a specialized version of the standard longest subsequence finding algorithm for a sequence of length 3. I'm posting the way I came up with the solution, because I think it is an interesting example of ...
answered Apr 7 '12 at 14:38
Gilles 'SO- stop being evil'
37.9k7 gold badges102 silver badges166 bronze badges
11
Some work has been done that matches your description. For instance:
Compiler-directed array interleaving for reducing energy in multi-bank memories. by Delaluz, V. Design Automation Conference, 2002. Proceedings of ASP-DAC 2002. 7th Asia and South Pacific and the 15th International Conference on VLSI Design. Proceedings.
describes a such an optimization.
11
An oracle is basically a magic black box that does something (e.g. query the entries of an array), usually in constant time. How the oracle does this is abstracted away from (and sometimes an oracle might even do something impossible like solve the halting problem). It's just a way of saying "presume we had these computational abilities, then ...".
11
Skiena didn't say "applicative order", just "applicative". This is sometimes used as meaning something like "purely functional", or a language that evaluates via the application of functions as opposed to the execution of state manipulating commands. Mathematica (at least nowadays) isn't purely functional, but it does seem that it strongly encourages a ...
11
Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:
Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)
Sort the $2N$ pairs by their first coordinate (in case of equality, put + before -). You can do this in time $O(N \log N)$ with any reasonable ...
11
What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound.
The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2*N* - 1 seems more like it would be the upper bound since there is ...
10
Strategy
The following linear-time algorithm adopts the strategy of hovering around $0$, by choosing either positive or negative numbers based on the sign of the partial sum. It preprocesses the list of numbers; it computes the permutation of the input on-the-fly, while performing the addition.
Algorithm
Partition $a_1, \ldots, a_n$ into a two lists, ...
10
This sounds more like the makings of a computational model rather than a programming language, as such, perhaps in the same way that the quantum computation can form the basis of a programming language such as the quantum lambda calculus.
Ask yourself:
What kinds of computation are you trying to perform?
How can these computations be composed?
How can the ...
10
If the elements need not be distinct, then you cannot have an $O(\log n)$ time algorithm.
Consider the sorted array $[0,0, \dots, 1]$ which has been cyclic shifted $k$ (unknown) times and you need to find where the $1$ appears. This needs $\Omega(n)$ time, as you need to examine at least $n-1$ elements.
However, if you assume the elements are distinct, ...
10
Mannila [1] axiomatizes presortedness (with a focus on comparison-based algorithms) as follows (paraphrasing).
Let $\Sigma$ a totally ordered set. Then a mapping $m$ from $\Sigma^{\star}$ (the sequences of distinct elements from $\Sigma$) to the naturals is a measure of presortedness if it satisfies below conditions.
If $X \in \Sigma^{\star}$ is ...
Only top voted, non community-wiki answers of a minimum length are eligible
