You have an Array of length n. If you pick a sub-array from the array, it must contain at least one unique element. The sub-array could be of any length but must contain consecutive/successive elements.

The question is what is the minimum number of characters you need to ensure that your array has the property mentioned and how should those elements be placed in the array? the answer needs to be in terms of n.

For Instance,

Let n be 10. Then you can place n different characters in it.

a, b, c, d, e, f, g, h, i, j

such that any sub-array would contain all unique elements. In this case the answer is n. But, of course this is not optimal as you need only one unique element in the sub-array.

In the same example of to pick 2 elements a and b and place them as

a, b, a, b, a, b, a, b, a, b

and you pick a sub-array of the first 4 elements a, b, a, b then you do not have any unique element. In this case the answer is 2 but is Incorrect.

So, what is the minimum number of unique element (and their placement in the array) you need to ensure your array has the property mentioned.


closed as unclear what you're asking by D.W., David Richerby, Juho, Ran G., lPlant May 25 '15 at 3:33

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ You are given an array of length n. If you pick any sub-array from it it must contain at least one unique element. To ensure you have such an array what is the minimum number of unique characters to fill the array and how will you place those characters in the array? The answer need to be in terms of n. $\endgroup$ – Dipped Bits May 19 '15 at 6:43
  • 2
    $\begingroup$ OK, so the question was changed drastically. Now, what have you tried, and where did you get stuck? We expect you to make a significant effort before asking, and to show us in the question what you've tried. $\endgroup$ – D.W. May 19 '15 at 7:00
  • $\begingroup$ @D.W.: Who is this "We" you are referring to? and BTW ... It was a question I saw online and solved it, and wanted to share it with people here as it seemed like a nice problem. And I don't have to show anything or prove anything. Being an Ass is easy, it's being social that matters. This is what this site is about. $\endgroup$ – Dipped Bits May 19 '15 at 7:28
  • 1
    $\begingroup$ @DippedBits "we" means the community, and this site isn't actually about being social (not a criticism of you or the site), it's about amassing a collection of useful, quality questions and answers. Hence when you post a question, the implicit statement is that you have a problem you can't solve, and need help. (cont.) $\endgroup$ – Luke Mathieson May 19 '15 at 8:22
  • 1
    $\begingroup$ @DippedBits (pt 2) To discourage abuse and laziness, it is expected that a question shows research effort (hover over the voting buttons for a question, you will see this is one of the criteria for voting up or down). If you want to post a neat puzzle, this isn't really the place. Question and answers should primarly be useful. $\endgroup$ – Luke Mathieson May 19 '15 at 8:22

$\lceil \lg n \rceil$.

For example, for $n=10$, try ABACABADAB. See if you can work out the pattern.

(I'll leave it at that, as this is a nice exercise problem and I'll let you have the joy of solving it on your own.)


Not the answer you're looking for? Browse other questions tagged or ask your own question.