JavaScript Program to Find i’th Index Character in a Binary String Obtained After n Iterations
Given a decimal number m, convert it into a binary string and apply n iterations. In each iteration, 0 becomes “01” and 1 becomes “10”. Find the (based on indexing) index character in the string after the nth iteration.
Input: m = 5, n = 2, i = 3
Output: 1
Input: m = 3, n = 3, i = 6
Output: 1
Approach 1
- Convert a decimal number into its binary representation and store it as a string ‘s’.
- Iterate ‘n’ times, and in each iteration, replace ‘0’ with “01” and ‘1’ with “10” in the string ‘s’ by running another loop over its length, storing the modified string in ‘s1’ after each iteration.
- After all, iterations, return the character at the ‘ith’ index in the final string ‘s’.
Javascript
// Javascript Program to find ith // character in a binary String. let s = "" ; // Function to store binary Representation function binary_conversion(m) { while (m !== 0) { let tmp = m % 2; s += tmp.toString(); m = Math.floor(m / 2); } s = s.split( "" ).reverse().join( "" ); } // Function to find ith character function find_character(n, m, i) { // Function to change decimal to binary binary_conversion(m); let s1 = "" ; for (let x = 0; x < n; x++) { let temp = "" ; for (let y = 0; y < s.length; y++) { temp += s[y] === '1' ? "10" : "01" ; } // Assign temp String in s String s = temp; } return s[i] === '1' ? 1 : 0; } let m = 5, n = 2, i = 8; console.log(find_character(n, m, i)); |
Output
1
Time Complexity: O(N)
Space Complexity: O(N), where N is the length of string.
Approach 2
- In this approach, we calculate the ith character in a binary string after n iterations.
- It converts a decimal number M into its binary representation, finds the block number where the character is, and handles special cases when k corresponds to the root digit.
- We use bitwise operations to efficiently determine whether to flip the root digit or not.
- The result is then printed, providing the desired character within the modified binary string.
Javascript
// Javascript program to find ith // Index character in a binary // string obtained after n iterations // Function to find // the i-th character function KthCharacter(m, n, k) { // Distance between two // consecutive elements // after N iterations let distance = Math.pow(2, n); let Block_number = Math.floor(k / distance); let remaining = k % distance; let s = new Array(32).fill(0); let x = 0; // Binary representation of M using a while loop while (m > 0) { s[x] = m % 2; m = Math.floor(m / 2); x++; } // kth digit will be // derived from root // for sure let root = s[x - 1 - Block_number]; if (remaining == 0) { console.log(root); return ; } // Check whether there is // need to flip root or not let flip = true ; while (remaining > 1) { if ((remaining & 1) > 0) { flip = !flip; } remaining = remaining >> 1; } if (flip) { console.log((root > 0) ? 0 : 1); } else { console.log(root); } } let m = 5, k = 5, n = 3; KthCharacter(m, n, k); |
Output
1
Time Complexity: O(log N)
Space Complexity: O(1)