วิธีลบหนึ่งองค์ประกอบออกจากสตริงไบนารีเพื่อให้ XOR กลายเป็นศูนย์ใน C++

ในปัญหานี้ เราได้รับสตริงไบนารี งานของเราคือนับจำนวนวิธีที่เราสามารถลบองค์ประกอบหนึ่งออกเพื่อให้ XOR กลายเป็นศูนย์

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

n = 11010

ผลลัพธ์

3

เพื่อแก้ปัญหานี้ เราต้องการตรรกะที่ว่าถ้าจำนวน 1 เป็นคู่ XOR ของสตริงจะเป็น 0 มิฉะนั้น เราจำเป็นต้องลบ 1 ตัวออกจากสตริง เราสามารถลบ 0 จำนวนเท่าใดก็ได้โดยไม่กระทบ XOR

โปรแกรมแสดงการใช้งานโซลูชันของเรา

ตัวอย่าง

#include<iostream>
#include<string.h>
using namespace std;
int wayXorZero(string binaryString){
   int oneCount = 0, zeroCount = 0;
   int n = binaryString.length();
   for (int i = 0; i < n; i++)
      if (binaryString[i] == '1')
         oneCount++;
      else
   zeroCount++;
   if (oneCount % 2 == 0)
      return zeroCount;
   return oneCount;
}
int main(){
   string binaryString = "10110100";
   cout<<"Number of ways to make XOR zero is "<<wayXorZero(binaryString);
   return 0;
}

ผลลัพธ์

Number of ways to make XOR zero is 4