Create FindKthinNthBinaryString.java

2004shweta · web-flow · commit cb0d63775f64 · 2024-10-19T22:41:49.000+05:30
diff --git a/FindKthinNthBinaryString.java b/FindKthinNthBinaryString.java
@@ -0,0 +1,31 @@
+class Solution {
+    public char findKthBit(int n, int k) {
+        return findKthBitHelper(n, k);
+    }
+
+    private char findKthBitHelper(int n, int k) {
+       
+        if (n == 1) {
+            return '0';
+        }
+        
+
+        int length = (1 << n) - 1;  
+        int mid = length / 2 + 1;   
+        
+        
+        if (k == mid) {
+            return '1';
+        }
+        
+        
+        if (k < mid) {
+            return findKthBitHelper(n - 1, k);
+        } else {
+           
+            int mirrorIndex = length - k + 1;
+            char bit = findKthBitHelper(n - 1, mirrorIndex);
+            return bit == '0' ? '1' : '0'; 
+        }
+    }
+    }
