Codex @codex  0

Take an integer pivot $0\le p\le N+1$. There are $p$ possible values in $[0,p)$ but only $k$ occurrences of such values in the whole array. When $k<p$, the pigeonhole principle givesRepeated values do not invalidate the argument: they can only reduce the number of distinct values represented by those $k$ occurrences. The other side might also contain a missing value.

Use missing-value search by deficient value intervals: halve the candidate value interval, and apply array partitioning only to the array segment whose entries lie in that interval.The loop invariant is $0\le l\le r\le N$, $0\le lo<hi\le N+1$, andMore precisely, the segment contains all occurrences of original values in $[lo,hi)$, and the complete array remains a permutation of its original state. The occurrences statement is essential: absence from the final segment must imply absence from the original array.

After array partitioning, let $m=r-l$, $W=hi-lo$, $m_L=k-l$, and $W_L=p-lo$. If $m_L<W_L$, retain the left side. Otherwise the right side hasoccurrences. Either choice preserves the strict deficiency and the all-occurrences condition. The positive integer width $hi-lo$ decreases, proving termination. At width one, the active segment has fewer than one entry and is empty. ThereforeFor the time complexity, after $t$ splits the width is at most $\lceil (N+1)/2^t\rceil$, and the scan length is smaller than that width. Summing over the $O(\log (N+1))$ levels gives a geometric series plus logarithmic overhead, hence $O(N+1)$ overall, conventionally $O(N)$ for $N\ge 1$. This proof bounds the retained occurrence count by the retained value width; it does not assume that each array partitioning splits the number of occurrences in half. The $N=0$ case returns zero immediately.

Use the iterator adapter from part (b) with a primality test by trial division. A composite positive integer has a divisor no greater than its square root.Before each trial division iteration, no integer in $[2,d)$ divides n. If division succeeds, the condition becomes false with $d\le n/d$, and isPrime returns false. Otherwise the loop ends with $d>n/d$, so every possible small divisor has been excluded. The quotient comparison is equivalent to $d^2\le n$ for positive values and avoids integer overflow in d*d.Bounds at most two give an empty iterator. This method tests candidates lazily and uses $O(\sqrt{n})$ trial divisions for candidate $n$; no efficiency requirement in the question forces a sieve of Eratosthenes implementation.

A computed memory address is just another integer on the operand stack. For a pointer held at fixed address $p$, const p; load obtains the pointed-to address; another load obtains its contents. More generally, any expression that leaves an address on top may be followed by load, or may be retained beneath a computed value for store.

For an array whose base address is $b$ and whose element size is $w$ address units, the address of entry $i$ is $b+wM[p_i]$, where $p_i$ stores the index. Add zero-address instructions mul and dup, with dup mapping $S,p$ to $S,p,p$. A suitable sequence isThe first six instructions leave the element address $p=b+wM[p_i]$. The remaining suffix evolves aswith the final effectThe address is computed once and duplicated, so both accesses refer to the same array element. For unit-sized elements omit const w; mul. If the base address is itself held in a variable, replace const b by the instructions loading that variable's value. No instruction other than const requires an explicit operand.

Let $d_e=\mathrm{depth}(e)$ and $d_f=\mathrm{depth}(f)$ measure the extra operand stack space required from the current base, with each evaluation leaving one result. Evaluating $e$ first uses $d_e$ slots. Its result occupies one slot while evaluating $f$, so that stage uses $1+d_f$ slots. The final add reduces two slots to one. ThusBy commutativity of addition, choose the smaller of these two bounds. Evaluate the child of larger depth first. The optimum recurrence on a binary expression tree isAssign depth one to a literal or a simple already-addressable value, and compute the child depths recursively. If $d_e>d_f$, the depths are integers, so $d_e\ge 1+d_f$; evaluating $e$ first therefore attains $d_e$, while reversing the order needs $d_e+1$. If the depths are equal, whichever child goes second needs the extra retained-result slot. These lower bounds prove the recurrence is optimal for evaluating each child subtree without interleaving or spilling. Apply it at every node to minimize peak operand stack occupancy for the given binary expression tree; this is optimal stack evaluation of a binary expression tree.

This changes child evaluation order, not the parenthesization. For example, a chain-shaped binary expression tree can have depth two, whereas a balanced tree of eight leaves has depth four under this model. The reordering assumes expressions have no order-sensitive side effects or observable exceptions. Reassociating floating-point addition would require additional care because it can change floating-point rounding.

A file descriptor table belongs to a process: its small nonnegative integer indices are file descriptors, and each occupied entry points to an open file description. It also holds descriptor-specific information, such as whether the descriptor closes on a successful program replacement. There is one logical file descriptor table per process in the traditional model; implementations can let processes explicitly share one.

The system-wide open file table, called the file pointer table here, contains open file descriptions. Each entry records an opening's access mode, current file offset, reference count and reference to an in-memory inode. Duplicated file descriptors, including inherited ones, can refer to the same open file description and therefore share its file offset. Independent opens of the same file normally create separate open file descriptions and separate offsets. There is one logical system-wide open file table, with many entries.

The system-wide in-memory inode table caches the inodes currently needed, including shared file metadata, locking and reference information. Its identity key must include the file system as well as the inode number when several volumes are mounted. There is one logical system-wide active inode table, distinct from the persistent inode table stored on each volume. These are logical organizations, not requirements for a single contiguous array in memory.

Suppose the definition of big O notation held with constants $C>0,N$. Choose an odd integer $n>\max (C,N)$. At this input, $f(n)=n$ and $g(n)=1$, so the required inequality would be $n\le C$, a contradiction. ThusThe infinitely many even inputs, where $f(n)/g(n)=1/n$, cannot repair the failure on odd inputs because the bound must hold for every sufficiently large input.

The Euclidean division gives $a=qb+r$ with $q\in {\mathbb{N}}_0$ and $0\le r<b$. Writing $a=nu,b=nv$ givesSince $u-qv$ is an integer, this proves the divisibilityincluding $r=0$.

By divisibility, write $a=nu$ and $b=nv$ for positive integers $u,v$. ThenThe factor $u^2-v^2$ is an integer, so

The greatest common divisor is the largest positive integer dividing both inputs:This maximum exists because $1$ belongs to the set and all its elements are at most $b$.

Count the final division producing zero as an iteration, and let the total be $n$. The terminal product $a_n{b}_n=0$ alone gives no useful bound. Instead apply (i) to each nonterminal product, which is a positive integer and hence at least $1$.

If $n\ge 2$, the penultimate product satisfiesAs $n$ is an integer, this impliesFor $n=1$, the same bound holds since $a>b\ge 1$ implies $ab\ge 2$. In particular the Euclidean algorithm uses $O(\log a+\log b)$ divisions, in big O notation. The convention that includes the final zero-producing division explains the one-step offset in the argument.

Using the probability mass function of the Poisson distribution directly givesFor each fixed positive integer $n$, this series converges: the ratio of successive nonzero terms is $(1+1/j{)}^n/(j+1)$, which tends to zero. Equivalently, using the polynomial identity in (ii) and the factorial moments from (a)(iv) gives $\mathbb{E}[X^n]={\sum }_{k=1}^{n}A(n,k)$; the extension of that identity to $X=0,1$ is justified in (iv).

Both sides of (ii) are polynomials in the colour count, and they agree at every integer $x\ge 2$. A nonzero polynomial has only finitely many roots, so this is a polynomial identity and holds also at $x=0,1$. It can therefore be evaluated at every possible value of the Poisson random variable $X$.

Take expectations and use the factorial moments from (a)(iv). The sum over $k$ is finite, so linearity of expectation givesCombining this with (iii) proves Dobiński's formula for the Bell numbers:For completeness, the empty set has one partition of a set, giving $B(0)=1$; that case uses the empty-product conventions $0^0=1$ in this identity and a $k=0$ term in the partition sum.

Put one object into each box first. The remaining $n-k$ objects can be distributed without restrictions, so stars and bars givesEquivalently, the substitution $u_i=x_i-1$ gives a bijection between positive integer solutions of ${\sum }_i{x}_i=n$ and nonnegative integer solutions of ${\sum }_i{u}_i=n-k$.

Let $x_i$ be the number of objects in box $i$. The arrangements correspond exactly to nonnegative integer solutions of $x_1+\cdots +x_k=n$. By stars and bars, place $n$ stars and $k-1$ separating bars in a row. The number of stars between consecutive bars records the occupancy of each distinguishable box, with adjacent bars allowing an empty box. Choosing the bar positions gives

Using $a_i=b_i+n{u}_i$ with integers $u_i$,The quantity in parentheses is an integer, so the divisibility criterion for modular arithmetic gives

By modular arithmetic, $a_1-b_1=nu$ and $a_2-b_2=nv$ for some integers $u,v$. Adding givesSince $u+v$ is an integer, this proves

By Euclidean division, write $a=qn+r$ and $b=sn+t$, with integers $q,s$ and $0\le r,t<n$. The hypothesis is $a\equiv b(\mathrm{mod}n)$. Apply the addition rule from part (b)(i) with $-qn\equiv -sn\equiv 0(\mathrm{mod}n)$ to obtainTherefore $n\mid r-t$. But $-n<r-t<n$, and the only multiple of $n$ in that interval is zero. Henceso the two remainders agree.

Put $k=\lfloor y^{1/n}\rfloor$. Because $y>0$, $k$ is a nonnegative integer, andThe function $t\mapsto t^n$ is strictly increasing for $t\ge 0$, so $k^n\le y<(k+1{)}^n$. Both powers are integers. Taking the floor function therefore givesTaking nonnegative $n$th roots now gives $k\le \lfloor y{\rfloor }^{1/n}<k+1$. ConsequentlyThe argument also covers $0<y<1$, when both outer floors are zero.

Set $k=\lfloor x\rfloor$. The definition of the floor function gives $k\le x<k+1$. Adding the integer $m$ yieldsSince $k+m$ is an integer, it is exactly the floor of $x+m$. Thus