java - 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

小圆点表示这个系列将继续进行。所以这是你的解决方案：

让我们考虑基于 1 的索引。您注意到 1 出现在索引 1、(1+2)=3、(1+2+3)=6、(1+2+3+4)=10 等处。我们有一个公式。它的 n*(n+1)/2 。

因此，对于给定的索引（现在这是基于 0，因为 java 数组从索引 0 开始）执行以下操作：

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;

也不需要递归，因为这是 O(1) 解决方案（不考虑平方根函数的复杂性）

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