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; }