New answers tagged arrays
1
Here is an algorithm using dynamic programming. Let us define the function $C:V\times \mathbb{N} \rightarrow \mathbb{N}$ as $C(i, s) = r$, if using only the first $i$ elements we can achieve a sum of at least $r$ in B, when having a sum at list $s$ in $A$. This means $C(i, s) = r$ if there is an index set $I \subseteq [i]$, such that $\sum_{j \in I} A[j] \...
4
I believe the goal of this question was to get you to say that the information about even or odd can't lead to any significant speedup in runtime.
Suppose you have an algorithm which works very fast in that case. Then, given any array of integers, you can split it up into an array of even integers and an other of odd integers in linear time. You can then ...
0
Use Radix sort. The time complexity is O(kn) and space complexity is O(k + n) . Here n is the number of elements and k is the number of bits required to represent largest element in the array.
3
Instead of a trie, here is an alternative approach that is compact and easy to implement:
Sort the list of strings. Store the sorted list. Use binary search for lookups.
To store the string, have two arrays: $A[1..n]$ is an array with $n$ entries, where $n$ is the number of strings; $B[1..M]$ is an array with $M$ characters, where $M$ is the sum of ...
0
This is an explanation of the correctness of Steven's answer. Of course I would be interested if anyone came up with something simpler but it is a great solution as it stands.
Define the effective key at a node to be the node's label + the offsets of all nodes on the (inclusive) path from itself to the root. Our inductive hypothesis is that after ...
0
It seems some kind of problem with mathematical solution (try to find the position with a closed math formula). However, here is an algorithmic approach that runs in $O(n \log^2 n)$.
Using segment tree / Fenwick tree, you can find the number of removed elements in a range (using prefix sums). Keep track of the offset (imagine having a pointer on the first ...
Top 50 recent answers are included
