Algorithm to find element value of sequence

Question

There is the following sequence:

101001000100001...

How to define a method that takes an element's index of the sequence and returns the value (0 or 1) ​​of this element?

public Element getValue(int index) {}

Maybe there's need to use recursion? I would be grateful for any ideas!

Answer 1

Little dots indicate that this series will go on. So here is your solution:

Lets consider 1 based index. You notice that 1 occurs at index 1, (1+2)=3, (1+2+3)=6, (1+2+3+4)=10 etc. We have a formula for this. Its n*(n+1)/2 .

So for given index(now this is 0 based as java array begins at index 0) do the following:

index = index + 1;   // now it is 1 based index and our formula would fit in nicely.
index = index * 2;
sqroot = integer part of square root of index;
if( sqroot * (sqroot+1) == index)
  print 1;
else 
  print 0;

Also there is no need for recursion as this is O(1) solution(not considering complexity of square root function)