Geek asks and answers

Algorithm for finding the value of a sequence element

The following sequence exists:

101001000100001 ...

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

public Element getValue(int index) {}

Maybe you need to use recursion ? I would be grateful for any ideas!

+5
source share
2 answers

Small dots indicate that this series will continue. So here is your solution:

Let's look at the index based on 1. You noticed 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.

, ( 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) ( )

+3

1, index + 1 . , , 8 + 1 - . , + 1 , oly, 8 * index + 9 - .

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

+1

More articles:


All Articles