Need help with making something O(logn)
Go to solution
Solved by fizzlesticks,
Hate when these problems only give sample answers for small input you could just do by hand for testing.
Assuming my program is correct.
You don't need to do anything with the string at all. Instead just figure out what position of the original string N would get its value from and determine whether is needs to be flipped or not.
Spoilerimport math s1 = '1221' n = int(input('n: ')) - 1 closest_power = math.log(n+1, 4) closest_power = int(closest_power) if int(closest_power) == closest_power else int(closest_power) + 1 flip = False pos = n while closest_power > 1: length = int(math.pow(4, closest_power)) lengthm1 = length // 4 if lengthm1 <= pos < length - lengthm1: flip = not flip pos = pos % lengthm1 closest_power -= 1 ans = s1[pos] if flip: ans = '1' if ans == '2' else '2' print(ans)
P.S. screw 1 based indexing.
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now