#include <bits/stdc++.h>
using namespace std;


// hamming code implementation

int parity(int k) {
    int r = 0;
    while ((1 << r) < k + r + 1) r++;
    return r;
}


void encode(vector<int> &data, vector<int> &code) {
    int k = data.size();
    int n = code.size();
    int r = n - k;

    for (int i = 0; i < r; i++) {
        int p = 1 << i;
        int cnt = 0;
        int x = 0;
        bool flag = true;
        for (int j = p - 1; j < n; j++) {
            if (p == cnt) {
                flag = !flag;
                cnt = 0;
            }
            if (!flag) {
                cnt++;
            } else {
                if (code[j] != -1)
                    x ^= code[j];
                cnt++;
            }
        }

        code[p - 1] = x;
    }

}


int check_error(vector<int> &code) {
    int n = code.size();
    int r = log2(n);
    int error = 0;
    for (int i = 0; i <= r; i++) {
        int p = 1 << i;
        int cnt = 0;
        int x = 0;
        bool flag = true;
        for (int j = p - 1; j < n; j++) {
            if (p == cnt) {
                flag = !flag;
                cnt = 0;
            }
            if (!flag) {
                cnt++;
            } else {
                if (cnt != 0)
                    x ^= code[j];
                cnt++;
            }
        }
        if (x != code[p - 1]) {
            error += p;
        }
    }
    return error;
}

void correct_error(vector<int> &code, int error) {
    if (error == 0) return;
    code[error - 1] ^= 1;
}







int main() {
    char ch = 'y';
    do {
        cout << "1 - Encode\n";
        cout << "2 - Check and Correct Error\n";

        cout << "Enter your choice: (1/2) : ";
        int choice;
        cin >> choice;

        if (choice == 1) {
            cout << "Enter the number of data bits: ";
            int k;
            cin >> k;

            cout << "Enter the data bits: ";

            vector<int> data(k);
            string s;
            cin >> s;

            for (int i = 0; i < k; i++) {
                data[i] = s[i] - '0';
            }

            int r = parity(k);
            int n = k + r;
            vector<int> code(n);

            for (int i = 0; i < r; i++) {
                code[(1 << i) - 1] = -1;
            }


            int j = k - 1;
            for (int i = 0; i < n; i++) {
                if (code[i] != -1) {
                    code[i] = data[j--];
                }
            }
            encode(data, code);
            cout << "The encoded data is: ";
            for (int i = 0; i < n; i++) cout << code[i] << " ";
            cout << endl;
        } else {

            cout << "Enter the number of code bits: ";
            int n;
            cin >> n;
            cout << "Enter the code bits: ";
            string s;
            cin >> s;
            vector<int> code(n);
            for (int i = 0; i < n; i++) {
                code[i] = s[i] - '0';
            }

            int error = check_error(code);
            if (error != 0) {
                cout << "Error at position: " << error << endl;
                correct_error(code, error);
                cout << "Corrected code is: ";
                for (int i = 0; i < n; i++) cout << code[i] << " ";
                cout << endl;
            } else {
                cout << "No error detected\n";
            }

        }
        cout << "Do you want to continue? (y/n) : ";
        cin >> ch;
        ch = tolower(ch);
    } while (ch == 'y');

    cout << '\n';
    cout << "Thank you for using this program\n";

    return 0;
}