Find Kth Bit in Nth Binary String LeetCode solution in C++

1
class Solution {
2
 public:
3
  string Reverse(string s) {
4
    for (int i = 0; i < s.length() / 2; i++) {
5
      swap(s[i], s[s.length() - 1 - i]);
6
    }
7
    return s;
8
  }
9

10
  string invert(string s) {
11
    for (int i = 0; i < s.length(); i++) {
12
      if (s[i] == '1')
13
        s[i] = '0';
14
      else
15
        s[i] = '1';
16
    }
17
    return s;
18
  }
19

20
  string S(int n) {
21
    if (n == 1) {
22
      return "0";
23
    }
24
    return S(n - 1) + "1" + Reverse(invert(S(n - 1)));
25
  }
26

27
  char findKthBit(int n, int k) {
28
    if (n == 1) return '0';
29
    string s = S(n - 1) + "1" + Reverse(invert(S(n - 1)));
30
    return s[k - 1];
31
  }
32
};