HackerRank Changing Bits problem solution

In this HackerRank Changing Bits problem solution, we have given A and B two binary numbers of length N and a list of commands. we need to create a string made of the results of each get_c call the only command that produces output.

Problem solution in Python.

def set_bit(val, i, bit):
    num = 1 << i

    if bit:
        return val | num

    return val & ~num

NQ = input()

two_ints = NQ.split()

N, Q = int(two_ints[0]), int(two_ints[1])

A = int(input(), 2)

B = int(input(), 2)

output = []
for i in range(Q):
    input_line = input()
    split_input = input_line.split()

    query = split_input[0]
    index = int(split_input[1])

    if query == 'set_a':
        val = int(split_input[2])
        A = set_bit(A, index, val)

    elif query == 'set_b':
        val = int(split_input[2])
        B = set_bit(B, index, val)

    elif query == 'get_c':
        C = A + B
        C_bit = int(bool(C & (1<<index)))
        output.append(str(C_bit))

print(''.join(output))

Problem solution in Java.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.*;
import java.util.*;


public class ChangingBits {
	
	public static void main(String[] args) throws IOException {
		final int N = IOFast.nextInt();
		final int Q = IOFast.nextInt();
		final char[] A_ = IOFast.next().toCharArray();
		final char[] B_ = IOFast.next().toCharArray();
		final int[] A = new int[N+1];
		final int[] B = new int[N+1];
		final List<TreeSet<Integer>> pos = new ArrayList<TreeSet<Integer>>(3);
		
		for(int i = 0; i < 3; i++) {
			pos.add(new TreeSet<Integer>());
		}
		
		for(int i = 0; i < N; i++) {
			A[i] = A_[N-1-i] - '0';
			B[i] = B_[N-1-i] - '0';
			final int sum = A[i] + B[i];
			pos.get(sum).add(i);
		}
		
		for(int i = 0; i < Q; i++) {
			final String q = IOFast.next();
			switch(q.charAt(4)) {
			
			case 'a': {
				final int idx = IOFast.nextInt();
				final int x = IOFast.nextInt();
				if(A[idx] != x) {
					pos.get(A[idx] + B[idx]).remove(idx);
					pos.get((A[idx]=x) + B[idx]).add(idx);
				}
				break;
			}
			
			case 'b': {
				final int idx = IOFast.nextInt();
				final int x = IOFast.nextInt();
				if(B[idx] != x) {
					pos.get(A[idx] + B[idx]).remove(idx);
					pos.get(A[idx] + (B[idx]=x)).add(idx);
				}
				break;
			}
			
			case 'c': {
				final int idx = IOFast.nextInt();
				int carry = 0;
				final Integer p2 = pos.get(2).lower(idx);
				if(p2 != null) {
					final Integer p0 = pos.get(0).lower(idx);
					if(p0 == null || p2 > p0) {
						carry = 1;
//						System.err.println(p0 + " " + p2 + " " + pos.get(0).size());
					}
				}
				IOFast.out.print((A[idx]+B[idx]+carry)&1);
				break;
			}
			
			}
		}
		IOFast.out.flush();
	}
	

	
	static class IOFast {
		private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		private static PrintWriter out = new PrintWriter(System.out);
		
		private static final int BUFFER_SIZE = 50 * 200000;
		private static int bufIndex, readLen;
		private static char[] buf = new char[BUFFER_SIZE];
		private static boolean endInput;
		private static boolean[] isDigit = new boolean[256];
		private static boolean[] isSpace = new boolean[256];

		static {
			for(int i = 0; i < 10; i++) {
				isDigit['0' + i] = true;
			}
			isDigit['-'] = true;
			isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
		}

		private static void readBuffer() throws IOException {
			if(bufIndex == readLen && !endInput) {
				readLen = in.read(buf);
				bufIndex = 0;
				if(readLen == -1) {
					endInput = true;
				}
			}
		}

		private static char firstChar() throws IOException {
			readBuffer();
			return buf[bufIndex];
		}

		private static char nextChar() throws IOException {
			readBuffer();
			return buf[bufIndex++];
		}

		private static int readNum() throws IOException {
			int ret = 0;
			for(char c; isDigit[c = nextChar()] && !endInput; ) {
				ret = ret * 10 + c - '0';
			}
			return ret;
		}

		private static int nextInt() throws IOException {
			for(; !isDigit[firstChar()] && !endInput; bufIndex++) {
				;
			}

			int ret;
			if(firstChar() == '-') {
				bufIndex++;
				ret = -readNum();
			} else {
				ret = readNum();
			}

			return ret;
		}
		
		private static long readNumLong() throws IOException {
			long ret = 0;
			for(char c; isDigit[c = nextChar()] && !endInput; ) {
				ret = ret * 10 + c - '0';
			}
			return ret;
		}
		
		private static long nextLong() throws IOException {
			for(; !isDigit[firstChar()] && !endInput; bufIndex++) {
				;
			}

			long ret;
			if(firstChar() == '-') {
				bufIndex++;
				ret = -readNum();
			} else {
				ret = readNum();
			}

			return ret;
		}



		private static String next() throws IOException {
			while(isSpace[firstChar()] && !endInput) {
				bufIndex++;
			}

			StringBuffer sb = new StringBuffer(1024);
			for(char c; !isSpace[c = nextChar()] && !endInput; ) {
				sb.append(c);
			}

			return sb.toString();
		}

		private static double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

	}
}

Problem solution in C++.

#include <stdio.h>
#include <iostream>
#include <set>
using namespace std;

const int maxn = 100001;
unsigned char a[maxn], b[maxn];

int main()
{
	char cmd[20];
	int N, Q;
	cin >> N >> Q;
	char ch;
	for (int i = N - 1; i >= 0; i--)
	{
		cin >> ch;
		a[i] = ch - '0';
	}
	for (int i = N - 1; i >= 0; i--)
	{
		cin >> ch;
		b[i] = ch - '0';
	}
	a[N] = b[N] = 0;

	int i, v;
	set<int> s;
	set<int>::iterator it;
	for (int i = N - 1; i >= 0; i--)
		if (a[i] == b[i])
			s.insert(-i);
	for (int q = 0; q < Q; q++)
	{
		scanf("%s", &cmd);
		if (cmd[4] == 'a')
		{
			scanf("%d", &i);
			scanf("%d", &v);
			if (a[i] != v)
			{
				a[i] = v;
				if (a[i] == b[i])
					s.insert(-i);
				else
					s.erase(-i);
			}
		}
		else if (cmd[4] == 'b')
		{
			scanf("%d", &i);
			scanf("%d", &v);
			if (b[i] != v)
			{
				b[i] = v;
				if (a[i] == b[i])
					s.insert(-i);
				else
					s.erase(-i);
			}
		}
		else
		{
			scanf("%d", &i);
			if (i == 0) printf("%d", (a[0] ^ b[0]) );
			else
			{
				it = s.upper_bound(-i);
				if (it == s.end())
					printf("%d", (a[i] ^ b[i]));
				else
					printf("%d", (a[i] ^ b[i] ^ a[-(*it)]));
			}
		}
	}
	cout << endl;
	return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned int word_t;
typedef unsigned long int sum_t;

#define WORD_SIZE (sizeof(word_t) * 8)


int bit_words(int bits) {
    return (bits + (WORD_SIZE - 1)) / WORD_SIZE;
}
void set_bit(word_t* bits, int bit_idx, int val) {
    int word_idx = bit_idx / WORD_SIZE;
    int mask = 1 << (bit_idx % WORD_SIZE);

    if (!!val)
        bits[word_idx] |= mask;
    else
        bits[word_idx] &= ~mask;
}

int get_bit(word_t* bits, int bit_idx) {
    int word_idx = bit_idx / WORD_SIZE;
    return (bits[word_idx] >> (bit_idx % WORD_SIZE)) & 0x1;
}

void sum_bits(word_t* res, word_t* x, word_t* y, int num_bits) {
    memset(res, 0, bit_words(num_bits + 1) * sizeof(word_t));
    for (int i = 0; i < bit_words(num_bits); ++i) {
        sum_t sum = (sum_t)(x[i]) + (sum_t)(y[i]) + (sum_t)(res[i]);
        res[i] = sum;
        if (sum >> (sizeof(word_t) * 8))
            res[i + 1] = 1;
    }
}

void parse_bits(word_t** bits, int num_bits) {
    int num_words = bit_words(num_bits);
    *bits = (word_t*) malloc(num_words * sizeof(word_t));
    memset(*bits, 0, num_words * sizeof(word_t));

    char cbits[num_bits + 1];    
    scanf("%s", cbits);
    for (int i = 0; i < num_bits; ++i) {
        if (cbits[num_bits - i - 1] == '1')
            set_bit(*bits, i, 1);
    }
}

int main() {
    int num_bits, num_tests;
    scanf("%d %d", &num_bits, &num_tests);

    word_t num_words = bit_words(num_bits);

    word_t* A;
    word_t* B;

    parse_bits(&A, num_bits);
    parse_bits(&B, num_bits);

    int c_words = bit_words(num_bits + 1);
    word_t* C = (word_t*) malloc(c_words * sizeof(word_t));

    char cmd[5 + 1];
    int bit_idx;
    int val;

    int prev_cmd_was_c = 0;

    for (int i = 0; i < num_tests; ++i) {
        scanf("%s %d", cmd, &bit_idx);

        switch(cmd[4]) {
            case 'c':
                if (!prev_cmd_was_c) {
                    sum_bits(C, A, B, num_bits);
                    prev_cmd_was_c = 1;
                }
                printf("%d", get_bit(C, bit_idx));
                break;
            case 'a':
            case 'b':
                prev_cmd_was_c = 0;
                scanf("%d", &val);
                set_bit(cmd[4] == 'a' ? A : B, bit_idx, val);
                break;
            default:
                printf("=== ERROR!!\n");
        }
    }

    free(A);
    free(B);
    free(C);

    return 0;
}