Algorithm to find element value of sequence [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

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)

Answer 2

Return 1 if index + 1 is a triangular number. x is triangular, if and only if 8x + 1 is a square. So index + 1 is triangular, if and oly if 8*index+9 is a square.

public int getValue(int index) {
    int i = (int)Math.round( Math.sqrt(8*index + 9));
    if (i*i == 8*index+9)
        return 1;
    else
        return 0;
}

http://ideone.com/8L9A96