New answers tagged integers
1
No, breaking the algorithm by increasing n (the amount of numbers) makes this 100% not working in constant space.
To the question nobody asked:
You could easily modify the algorithm to get the space to be constant. (Only the solution given in the interview has this problem. The "best" solution does not have this problem.)
Basically the size of the sum ...
6
It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the ...
3
Resource usage always depends on your model of computation. If you're in a situation where integers can grow arbitrarily large then, yes, you need to take that into account.
One way of doing this is by assuming that integer variables take an amount of space that depends on the value stored. Another way is to use something like the word RAM model, which more ...
1
You can think of a bitvector as a set, by giving names to the various bits. For example, if we name the bits in an 8-bit integer using the numbers $0,\ldots,7$ (where $0$ is the LSB and $7$ is the MSB), then $00010010$ is the same as $\{1,4\}$.
Your first function asks whether the set has size $1$. If we name the bits using numbers as above, the second ...
2
This problem is NP-hard by a reduction from partition.
Let $X = \{x_1, \dots, x_n\}$, be an instance of partition and let $2M = \sum_{x \in X} x$ (assume that $M$ is an integer as otherwise the instance is trivial).
Assume that each $x_i$ is positive and let $\ell = \lceil \log 2M \rceil$.
I will now construct some values based on $X$. I will denote a ...
Top 50 recent answers are included
