# ThoughtSpot 校园面过经

⾯试是另⼀个天竺哥，45分钟，前5分钟吹b套近乎，后⾯出了道hard，我还没做过。

⼀开始⽐较懵逼，然后写暴力解，之后分析时间复杂度，后来在提示下优化了一下，还是感觉不咋地。

⼀周多之后通知约电话⾯面试。让约一小时zoom。

Given a binary string of size N and a positive integer K, calculate the number of operations required to convert this string to zero string by applying the following operation any number of times.
Operation: Let X is the index of first ‘1’ bit from left side, then Flip all the X’th, X+K, X+2K, X+3K… bits of string.
1 <= N <= 10^6
1 <= K <= N

Sample:
Input: 100010010011110, K = 2
Step-1: 001000111001011
Step-2: 000010010011110
Step-3: 000000111001011
Step-4: 000000010011110
Step-5: 000000000110100
Step-6: 000000000011110
Step-7: 000000000001011
Step-8: 000000000000001
Step-9: 000000000000000

## Output=9

Brute force is easy; O(n^2 / k )

Optimization thought
I believe we need to use % operator here since X’th, X+K, X+2K, X+3K… that means x + pK where p= 1,2,3…
that left x as reminder.

Any thought how to solve this?

As per interviwer we can solve it in O(n) time and O(1) space