JavaScript Program to Check if all Bits can be made Same by Single Flip

Read

Discuss

In this article, we will explore how to determine if it’s possible to make all bits the same in a binary string by performing a single flip operation. We will cover various approaches to implement this in JavaScript and provide code examples for each approach.

Examples:

Input: 1101
Output: Yes
Explanation: In 1101, the 0 can be flipped  to make it all 1
            
Input: 11
Output: No
Explanation: No matter whichever digit you 
           flip, you will not get the desired string.
Input: 1
Output: Yes
Explanation: We can flip 1, to make all 0's

Table of Content

Counting 0’s and 1’s
XOR Operation in JavaScript

Approach 1: Counting 0’s and 1’s

To check if all bits can be made the same by a single flip in JavaScript, you can follow these steps:

Count the number of 0s and 1s in the given binary sequence.
If the count of 0s is 1 or the count of 1s is 1, then it’s possible to make all bits the same by a single flip. Otherwise, it’s not possible.

Syntax:

for (statement 1 ; statement 2 ; statement 3){
    code here...
}

Example: Below is the implementation of the above approach

Javascript

function canMakeAllBitsSameBySingleFlip(binaryString) { 
    let countZeros = 0; 
    let countOnes = 0; 
  
    for (let i = 0; 
        i < binaryString.length; 
        i++) { 
        if (binaryString[i] === '0') { 
            countZeros++; 
        } else if (binaryString[i] === '1') { 
            countOnes++; 
        } else { 
          
            // If the input contains non-binary  
            // characters, return false 
            return false; 
        } 
    } 
  
    // Check if it's possible to make  
    // all bits the same by a single flip 
    return countZeros === 1 || countOnes === 1; 
} 
  
// True, because you can flip one  
// '0' to '1' to make all bits the same. 
const binaryString1 = "1101"; 
  
// False, because you can flip one '1' to '0' . 
const binaryString2 = "11"; 
  
// False, because it contains a non-binary character. 
const binaryString3 = "1010a"; 
  
console.log(canMakeAllBitsSameBySingleFlip(binaryString1)); 
console.log(canMakeAllBitsSameBySingleFlip(binaryString2)); 
console.log(canMakeAllBitsSameBySingleFlip(binaryString3));

Output

true
false
false

Time complexity: O(n) where n is the length of the string.

Approach 2: XOR Operation in JavaScript

Here we uses the XOR (exclusive OR) operation, is a bit manipulation technique to determine if it’s possible to make all bits in a binary string the same by a single flip. Let’s break down how this approach works:

Initialize XOR Result: Start with an initial XOR result of 0. This result will be used to track the parity (odd or even) of the number of ‘1’s encountered in the binary string.
Iterate Through the Binary String: Traverse the binary string character by character from left to right.
XOR Operation: For each ‘1’ encountered in the binary string, perform the XOR operation with the current XOR result. XORing a bit with 1 toggles its value: 0 XOR 1 = 1, and 1 XOR 1 = 0.

Syntax:

a^b

Example: Below is the implementation of the above approach

Javascript

function Approach2(binaryString) { 
  
    // Check for invalid characters 
    if (/[^01]/.test(binaryString)) { 
        console.log(`"${binaryString}" -> false`); 
        return false; 
    } 
  
    let xorResult = 0; 
    let hasOne = false; 
    let hasZero = false; 
  
    for (let i = 0; 
        i < binaryString.length; 
        i++) { 
        if (binaryString[i] === '1') { 
            xorResult ^= 1; 
            hasOne = true; 
        } else
            if (binaryString[i] === '0') { 
                xorResult ^= 0; 
                hasZero = true; 
            } 
    } 
  
/*  If xorResult is 0 or 1 and  
       both '0' and '1' are present,  
    it's possible to make all bits  
    the same by a single flip  
*/
    const result = 
        (xorResult <= 1) && 
        (hasOne && hasZero); 
    console.log(`"${binaryString}" -> ${result}`); 
    return result; 
} 
// Example usage: 
const binaryString1 = "1101"; 
const binaryString2 = "11"; 
const binaryString3 = "111"; 
const binaryString4 = "1010a1"; 
  
Approach2(binaryString1); // true 
Approach2(binaryString2); // false 
Approach2(binaryString3); // false 
Approach2(binaryString4); // false

Output

"1101" -> true
"11" -> false
"111" -> false
"1010a1" -> false

Time complexity: O(n) where n is the length of the string.

Whether you're preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, GeeksforGeeks Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we've already empowered, and we're here to do the same for you. Don't miss out - check it out now!

Last Updated : 03 Nov, 2023