New answers tagged data-structures
-1
Without using stack and recursion.
2
Yuval describes the general approach.
Let the binary representation of the two numbers be $n_1,\dots,n_k$ and $m_1,\dots,m_k$, where $n_1$ is the most significant bit. Introduce fresh new boolean variables $t_1,\dots,t_k$. The intention is that these will indicate the common prefix of $n,m$.
In particular, add the following clauses:
$t_{i+1} \implies ...
0
I want to check whether a arbitrary binary number is less or equal to another binary number in a cnf-formula.
This exercise is very interesting to become familiar with Boolean formulas in CNF.
In the question you did not specify whether the two numbers must have the same length or different lengths but for simplicity we will focus on the case $|n|=|m|$.
...
0
Let the string be $S_1,\ldots,S_n$. For every $m$, find the minimum number of words that $S_1,\ldots,S_m$ can be split into. I'll let you work out the remaining details.
0
Sometimes, depending on the sources,direct access and random access are used to express the same memory access mode and therefore do not present any substantial difference in the speed of data access.
More in detail, the differences between the two modes can be sought in their implementation:
Random Access can be realized directly via RAM memory wiring, ...
0
I can see several problems with your solution.
First of all, I don't think you are updating the balls after every second, as I would expect there to be a loop from $1$ to $t_i$. I think you are adding $t_1$ seconds, then adding $t_2$ seconds etc.
Which brings up the second problem. I think you are treating the intervals $t_i$ as incremental, whereas in the ...
0
One solution that comes to mind is to first build a directed graph where every vertex represents a vertex. An edge goes from Box A to Box B if B fits into A. One can easily verify that this graph contains no cycles. A maximum sequence of nested boxes is equivalent to the longest path in this directed acyclic graph. A longest path in a DAG can be found by ...
1
I think of divisibility mostly in terms of decomposition into prime factors: to be divisible by a query integer $q$, an integer $a_i$ has to be divisible by at least the same power of each prime in $q$s decomposition.
Divisibility by different primes is independent: I think of this (divisibility of integers from a set that can be preprocessed) as a ...
0
If the only condition is that $a_i >= 3a_{i-1}$ for even i then this should be quite trivial? What subset sums can you achieve by just picking the last two array elements?
1
What you ask is impossible, assuming you don't really mean sets (as sets are orderless), but ordered tuples. Consider $j=2$, then you effectively have $k$-length binary strings. And those require $\Omega(k)$ storage.
0
Given a set of keys, a “perfect” hash function is one that gives a different hash for each key. As soon as you try to apply it to a key outside that set, it is quite likely not “perfect” anymore.
Let’s say you are writing a compiler, and you found a”perfect” hash function that maps each reserved identifier of your programming language to a different hash ...
1
Your attempt runs into a huge problem with the input [1, 2, $2^{63}$].
Either your numbers are so small that it doesn’t matter. Otherwise, you start with a solution, find its speed and why it is slow, and then iteratively improve it. That’s usually a much better method than hoping that someone does the work for you.
For this specific problem, I think ...
2
For this problem I recommend to solve first for trees with simpler structures that can be generalized afterwards with data structures that run on top of trees (there are plenty of them).
Let's build an idea of what are the dynamics of the problem before jumping to the answer. We have the array A = [N0, N1, N2, N3]. An let's say after each second numbers at ...
1
Since there are no updates there is a rather simple solution. Store a map of key -> array of pairs, such that for every element in your original vector (value, key) at position pos, you store in the vector associated with given key in the map the pair (position, value). Keep every vector sorted by position.
For example in the input array: $$[(3, 1), (2, 3), ...
0
Since you have specified that the array is unsorted, i am afraid you cant do a query in $O(logN)$, assuming we are talking about time complexity and not space complexity (but i think this is the case since you have expressed the desire to make the query efficient because there can be more than one).
Keep in mind that (apart from a few exceptions which ...
-4
Here is working code. Don't forget to input your percentage in fractional form (e.g. $0.02$ for $2\%$).
#include <stdio.h>
#define MONTHS_IN_YEAR 12
float monthlyRepaymentAmount(float principalAmount, float interestRate, int numberOfYears);
int main(void) {
//Problem statement variables
float principalAmount; // use int if principal can ...
4
This is only a sketch of solution (there might be some off-by-ones)
Looking at a permutation of $\{1\ldots,n\}$ is equivalent at looking its inversion table $(a_1, \ldots, a_n)$ where $a_i$ is the number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S_n$ and $\prod_{1\le i\le n} \{0,\ldots,i-1\}$ and ...
1
You could look at the answers to this question on SO: https://stackoverflow.com/questions/19372991/number-of-n-element-permutations-with-exactly-k-inversions
(in particular the part about Mahonian numbers)
Additionally, it seems that dynamic programming with memoisation runs in $\mathcal{O}(N\cdot k)$ [NB: I didn't actually check this, it's in one of the ...
2
For every $i \in \{0,\ldots,n\}$ (where $n$ is the length of the array) and for every $a,b,c \in \{0,\ldots,15\}$, we determine whether it is possible to partition the first $i$ elements of the array into four subsets, the first three of which XOR to $a,b,c$, respectively. We also compute the XOR of the entire array. Using the information for $i = n$, we can ...
-2
Usually an array is considered as uniformly distributed when the difference between the elements are equal or almost same.
Example 1: 1,2,3,4,5,6 (Difference is 1)
Example 2: 10,20,31,40,55,60,73,80(Here the difference between the two adjacent elements are almost close to 10).
Interpolation search is to be used when the given array is both sorted and ...
2
Note that $\lceil \log(2^n) \rceil = n$.
An algorithm that uses $n$ bits to represent the set would be fine (it would count as a succinct data structure). An algorithm that uses $n + 2 \sqrt{n}$ bits would also be fine.
An algorithm that uses $2n$ bits to represent the set would not be fine (it would not count as a succinct data structure). Similarly, an ...
0
Adding to the answer by HEKTO above, to calculate the rank in a BST with unique elements,
the rank of a left child = rank of the parent - 1 - number of elements in its right subtree
and,
the rank for a left child = rank of the parent + 1 + number of elements in its left subtree.
It can be used to find any general $i^{th}$ order statistic in the BST in O(...
0
The key observation is the fact that only a single value will be changed in every operation.
For each element maintain an array of the form [(snap_id, value)].
Every time you need to snapshot the array, find out which elements have changed since their last snap_shot and update only those elements.
If you are asked to retrieve the value of any element at ...
0
Using arrays instead of classes and objects would make it easier for you to implement the disjoint set union concept.
Here's a resource to start off with:- Disjoint Set Union
for edge in edges:
if find_set(edge[0], node_map) != find_set(edge[1], node_map):
unioned_set = union(edge[0], edge[1], node_map, sets_map)
cost_map[edge[2]] = ...
1
Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates?
No.
In revision 8, it constructs a valid search tree on $y$.
The check in step 2 will almost always yield not satisfied.
The best I thought up, ignoring non-unique priority values:
Proceed the complete binary search tree ...
2
Any line can be represented in the form $\{p + xv : x \in \mathbb{R}\}$, or in other words, by a point $p$ on the line and a vector $v$ parallel to the line. Without loss of generality, we can take $v$ to have norm 1 (if not, replace $v$ with $v/\|v\|_2$). Also, if we ignore lines where the $z$-component of $v$ is zero, then without loss of generality we ...
1
Another possibility would be to store all the words in an array, sort it, and then do lookups on it using binary-search.
Disadvantages compared to a Trie:
Worse asymptotic time complexity for lookups ($O(\mathrm{log}\ n)$ average where n is the number of entries).
Probably less efficient to insert additional entries, as the array will need to be resized.
...
0
I would assume that it is a combination of the following aspects:
The worst-case of quick sort happens very rarely (and can be detected/circumvented)
Heapsort has to swap more often
Subproblems of quick sort are independent of each other and can thus be solved in parallel
1
1
For the first case, you had the right idea, but just had some algebra mistakes.
for i=1..n
j=1
while j*j <= i:
j = j + 1
Let $T(n)$ be the time complexity.
$$T(n) = \sum_{i=1}^n\sum_{j=1}^\sqrt{i}1\leq \sum_{i=1}^n\sqrt{n}=\leq n^{3/2}$$
$$= O(n^{3/2})$$
2
I'm assuming you meant the pseudocode below since it is more analogous to ...
4
If $k>N$, this cannot be done (as $\forall p_1,\dots, p_k\geq 0,\sum_{i=1}^k 2^{p_i}\geq k>N$)
If $k\leq N$: Write $N$ in binary, and denote by $n$ the number of $1$s. We have written $N$ as a sum of $n$ powers of two (which happen to all be distinct).
If $n\leq k$, then you can always split some of the powers of two (iteratively if needed) in order ...
Top 50 recent answers are included
