bump
Any takers?

Ez modo because I don't have time atm.

From the base case 1 which I'll name n, the next level will be n . ~n where . is append

>>51255703
:)

i think this will make an interesting bitmap

It is easy, don't have time to analyze it atm. The pattern is the same as some ocd thing I used to do

>>51256009
how so?

It's kind of like Pascal's triangle.

wow. this is recursive on so many levels.

consider the first 7 levels:

1
10
1001
10010110
1001011001101001
10010110011010010110100110010110
1001011001101001011010011001011001101001100101101001011001101001

of course every 4 bits there's either 1001 or 0110. but if you replace these with 1 and 0 you get the same pattern.

>>51255414
Every N level has 2^n-1 children. A level is composed of the N-1 level and inverted N-1 level. This means that if a child is in the second half - it has been inverted. If this is the case - subtract the number by 2^n-1. Subtract the child count by the same amount (regardless of the child possition). repeat. Get the result by counting the number of inversions. Can't think of something better.

O(ln(n)) i think.

def fn(n, k):
    if n == 1:
        return 1
    if n == 2:
        if k == 1:
            return 1
        if k == 2:
            return 0
    halfway = 2 ** (n-2)
    if k <= halfway: # 1 case
        return fn(n - 1, k)
    else: # 0 case
        return fn(n - 1, k - halfway) ^ 1

>>51256670
This is O(n) in time and space, because each recursive call reduces n by 1.

Try seeing if you can give a lower "n" value in your recursive calls. Also, try making it tail recursive to save space.

>>51255414
convert k to a binary number, 0 means you go left, 1 means you go right
odd number of 0s -> 1
even number of 0s -> 0

>>51256723
Actually I made a mistake. You should convert k-1 to a binary number. Didn't know that the problem was retarded and started counting at 1.

>>51256739
k=3
bin(k-1)=bin(2) = 10
odd number of 0s -> 1
but the answer is zero?

>>51256768
whoops, it should be the other way around.

>>51256786
hm, I think this works. interesting! How did you come up with it?

I think this is log_2(k) though. Anyone think it is/isn't possible to find a O(1) solution (if arithmetic ops are O(1)...)?

>>51256697
You're fucking retarded. You can't get anything lower than O(n) because it takes O(n) time to just read the number k in the first place.

>>51256851

    import math
    def answer(n, k, flip=False):
        if n == 1 or k == 1:
            return 1 * (not flip)
            
        half = 2 ** (n - 2)
        if k - 1 >= half:
            k = k - half
            flip = not flip
        level = math.ceil(math.log(k, 2)) + 1
        return answer(level, k, flip)

>>51256912

    def answer(n, k, flip=False):

I'm not going to even bother reading your code, but this line here already makes your solution O(n).

>>51256950
I know I'm getting trolled, but

def answer(n, k, flip=False):
    return 1

Is this also O(n)?

>>51256970
Yup.

>>51256970
That is O(2^n)

>>51256912
Sure looks like O(n) to me.

(31.0, 805306368)
(29.0, 268435456.0)
(28.0, 134217728.0)
(27.0, 67108864.0)
(26.0, 33554432.0)
(25.0, 16777216.0)
(24.0, 8388608.0)
(23.0, 4194304.0)
(22.0, 2097152.0)
(21.0, 1048576.0)
(20.0, 524288.0)
(19.0, 262144.0)
(18.0, 131072.0)
(17.0, 65536.0)
(16.0, 32768.0)
(15.0, 16384.0)
(14.0, 8192.0)
(13.0, 4096.0)
(12.0, 2048.0)
(11.0, 1024.0)
(10.0, 512.0)
(9.0, 256.0)
(8.0, 128.0)
(7.0, 64.0)
(6.0, 32.0)
(5.0, 16.0)
(4.0, 8.0)
(3.0, 4.0)
(2.0, 2.0)
(1.0, 1.0)

>>51257066
okay, now I am confused.

30000000 30000000 False
26 30000000 False
25 13222784 True
24 4834176 False
21 639872 True
18 115584 False
17 50048 True
16 17280 False
11 896 True
10 384 False
8 128 True
7 64 False
6 32 True
5 16 False
4 8 True
3 4 False
2 2 True
1 1 False

>>51257148
k can be a number between 1 and 2^n-1. Arbitrarily limiting k like that proves nothing.

>>51257193
Okay, you are right. I got a bit confused, but saying O(logk) is the same as O(n), right?

Also, can you explain why it can't be less than that?

This has a name:
https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence

Bumping this thread

>>51257230
Because it takes O(n) time to even read the value of k. If you are doing it in less time, you are not even looking at all the bits of k. I can change any bit you don't look at arbitrarily, and your answer will still be the same.

>>51256697
technically it's O(log k) because it binary partitions the tree horizontally but it's O(n). You're right, still though

>>51255414

Link the source?

>>51257357
Some one sent it to me, but it's on codefights.

>>51257386
but it doesn't


closed form solution thanks to the article:

def one_zero_tree(level, index):
  odd = 1 # need inverse of morse sequence
  for i in bin(index)[2:]
    odd ^= int(i,2)
  return odd

>>51257532
This isn't closed form.

Here's my log(n) solution in haskell, I'm having trouble coming up with a closed form.

f 1 = 1
f n
    | even n = f $ quot n 2 
    | otherwise = 1 - (f $ quot (n-1) 2)

tree i j = f $ 2^(i-1)+(j-1)

tree 1 1 = 1
tree 2 2 = 0
tree 3 3 = 0 

>>51258459
That isn't log(n). That's log(2^n) which is just n.

>>51258459
wat

>>51256078
Holy fuck me too. Anyone else do it?

>>51258514
it divides by 2 each iteration, so it's not O(n).

>>51258589
I think you're looking at k, not n.