# Meaning of “number of keys in the range $a$ to $b$” [closed]

Regarding this question:

You are given an unsorted array $$A$$ of $$n$$ integers in the range $$2^n −10n \leq A[i] \leq 2^n$$. Suggest a data structure that allows to answer in $$O(1)$$ steps the number of keys in the range $$a$$ to $$b$$ (note that $$a, b$$ are not necessarily integers). The construction of data structure should cost at most $$O(n)$$ steps.

1. Describe in few sentences the data structure.
2. Write a pseudocode for constructing the data structure.
3. Write a pseudocode for the numberKeys(NewDataStructure,a,b).
4. Give a short explanation of the time and space complexity of (2) and (3).

Can someone please explain me what "the number of keys in the range $$a$$ to $$b$$" means?

• in range $a \to b$ sounds plain enough, but mentioning keys without introducing them looks strange. Do keys map to values? Are duplicates allowed? unsorted and 10n(+1) should be hints. construction may be more straight-forward using more than one iteration/pass. – greybeard May 16 at 10:34
• (Coincidence on SO: Suggestion of a Data Structure.) – greybeard May 16 at 11:24
• It probably means "the number of array elements whose value is between $a$ and $b$". – Yuval Filmus May 16 at 15:14
• – D.W. May 17 at 4:33
• I’m voting to close this question because it was cross-posted. – D.W. May 17 at 4:33

## 1 Answer

It probably means "the number of array elements whose value is between $$a$$ and $$b$$".

For the solution, it is crucial that the number of possible values of array elements is $$O(1)$$.

• I see, so building a BST that holds key values? Something like that? – Oliver May 16 at 16:29
• That’s an overkill. – Yuval Filmus May 16 at 16:39
• BST that holds key values [is] overkill in conceptual and implementation effort while meeting answer in $O(1)$ steps by plugging $10n$ (or $n$?) $\in O(1)$ - bold. – greybeard May 16 at 19:58
• @YuvalFilmus What do you mean by overkill? Is that good? – Math4me May 25 at 8:51
• Look it up in the dictionary. – Yuval Filmus May 25 at 9:25