Table of Contents
Changing Bits – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 100010;
int a[maxn], b[maxn], c[maxn];
int n, q;
char ss[maxn*5];
int l[maxn*2], r[maxn*2], s[maxn*2], tn;
int build(int ll, int rr)
{
if(ll>=rr)
return -1;
int ret = tn++;
if(ll + 1 == rr)
{
l[ret] = r[ret] = -1;
s[ret] = c[ll];
return ret;
}
int mid = (ll + rr) / 2;
l[ret] = build(ll, mid);
r[ret] = build(mid, rr);
s[ret] = (s[l[ret]] == s[r[ret]] ? s[l[ret]] : 2);
return ret;
}
void init() {
scanf("%d%d", &n, &q);
//printf("%d %d\n", n, q);
memset(c, 0, sizeof(c));
scanf("%s", ss);
//printf("%s\n", ss);
for(int i=0; i<n; ++i) {
a[i] = c[i] = ss[n - i - 1] - '0';
}
scanf("%s", ss);
//printf("%s\n", ss);
for(int i=0; i<n; ++i) {
b[i] = ss[n - 1 - i] - '0';
c[i] += ss[n - 1 - i] - '0';
if(c[i] >= 2)
{
c[i] -= 2;
c[i+1] ++;
}
}
a[n] = b[n] = 0;
//memset(a, 0, sizeof(a));
//memset(b, 0, sizeof(b));
//memset(c, 0, sizeof(c));
n++;
tn = 0;
build(0, n);
}
void push_down(int id) {
if(s[id] == 2)
return;
if(l[id] < 0)
return;
s[l[id]] = s[r[id]] = s[id];
}
int findright(int id, int ll, int rr, int i, int bit)
{
if(rr <= i)
return -1;
if(s[id] == bit)
return i < ll ? ll : i;
if(s[id] == (bit ^ 1))
return -1;
push_down(id);
int mid = (ll + rr) / 2;
int t = findright(l[id], ll, mid, i, bit);
if(t >= 0)
return t;
return findright(r[id], mid, rr, i, bit);
}
void change(int id, int ll, int rr, int bl, int br, int bit)
{
if(br <= ll || rr <= bl)
return;
if(bl <= ll && rr <= br)
{
s[id] = bit;
return;
}
push_down(id);
int mid = (ll + rr) / 2;
change(l[id], ll, mid, bl, br, bit);
change(r[id], mid, rr, bl, br, bit);
if(s[l[id]] == s[r[id]])
s[id] = s[l[id]];
else
s[id] = 2;
}
int getbit(int id, int ll, int rr, int i)
{
if(i<ll || i>=rr)
return 0;
if(s[id] < 2)
return s[id];
int mid = (ll + rr) / 2;
if(i < mid)
return getbit(l[id], ll, mid, i);
else
return getbit(r[id], mid, rr, i);
}
void work() {
int i, bit;
int pn = 0;
char cmd[10];
while(q--) {
scanf("%s", cmd);
//printf("%s ", cmd);
if(cmd[4]=='a' || cmd[4] == 'b')
{
scanf("%d%d", &i, &bit);
//printf("%d %d\n", i, bit);
if(cmd[4] == 'a' && a[i] == bit)
continue;
if(cmd[4] == 'b' && b[i] == bit)
continue;
if(cmd[4] == 'a') a[i] = bit;
else b[i] = bit;
int lmb = findright(0, 0, n, i, bit ^ 1);
if(lmb == -1)
lmb = n;
change(0, 0, n, i, lmb, bit ^ 1);
change(0, 0, n, lmb, lmb + 1, bit);
}
else
{
scanf("%d", &i);
//printf("%d\n", i);
ss[pn++] = getbit(0, 0, n, i) + '0';
//printf("%c\n", ss[pn-1]);
}
}
ss[pn] = 0;
printf("%s\n", ss);
}
int main() {
init();
work();
}
Java rep HackerRank Solution
import java.io.*;
import java.util.Random;
import java.util.StringTokenizer;
public class Solution {
// leave empty to read from stdin/stdout
private static final String TASK_NAME_FOR_IO = "";
// file names
private static final String FILE_IN = TASK_NAME_FOR_IO + ".in";
private static final String FILE_OUT = TASK_NAME_FOR_IO + ".out";
BufferedReader in;
PrintWriter out;
StringTokenizer tokenizer = new StringTokenizer("");
public static void main(String[] args) {
new Solution().run();
}
int n;
int[] a, b, c;
private void solve() throws IOException {
// stress();
// timing();
n = nextInt();
int q = nextInt();
n++;
a = toArray(nextToken());
b = toArray(nextToken());
c = sum(a, b);
initFastStructures();
for (int k = 0; k < q; k++) {
String command = nextToken();
if ("set_a".equals(command)) {
int idx = nextInt();
int value = nextInt();
setSummandBitAndChangeSumFast(a, idx, value);
} else if ("set_b".equals(command)) {
int idx = nextInt();
int value = nextInt();
setSummandBitAndChangeSumFast(b, idx, value);
} else {
int idx = nextInt();
int value = getSumNumberOfDigitsToTheRight(idx, 1) > 0 ? 1 : 0;
out.print(value);
}
}
}
Random r = new Random(123456789L);
private int randomInt(int lo, int hi) {
return lo + r.nextInt(hi - lo + 1);
}
private int[] randomBitArray() {
int[] result = new int[n];
// the last bit is always empty
for (int i = 0; i < n - 1; i++) {
result[i] = randomInt(0, 1);
}
return result;
}
private void stress() throws IOException {
for (; ; ) {
n = randomInt(10, 20);
int bitChanges = randomInt(100000, 100000);
System.out.println("N = " + n + ", BitChanges = " + bitChanges);
n++;
a = randomBitArray();
b = randomBitArray();
c = sum(a, b);
initFastStructures();
for (int k = 0; k < bitChanges; k++) {
int command = randomInt(0, 1);
if (command == 0) {
int idx = randomInt(0, n - 2);
int value = 1 - a[idx];
setSummandBitAndChangeSumFast(a, idx, value);
} else {
int idx = randomInt(0, n - 2);
int value = 1 - b[idx];
setSummandBitAndChangeSumFast(b, idx, value);
}
// validate all bits
c = sum(a, b);
for (int idx = 0; idx < n; idx++) {
int vSlow = c[idx];
int vFast = getSumNumberOfDigitsToTheRight(idx, 1) > 0 ? 1 : 0;
if (vSlow != vFast) {
throw new IllegalStateException("Step " + k + ": difference in bit " + idx + " out of " + n);
}
}
}
}
}
private void timing() throws IOException {
n = 100000;
int q = 500000;
n++;
a = randomBitArray();
b = randomBitArray();
c = sum(a, b);
initFastStructures();
for (int k = 0; k < q; k++) {
int command = randomInt(0, 2);
if (command == 0) {
int idx = randomInt(0, n - 2);
int value = 1 - a[idx];
setSummandBitAndChangeSumFast(a, idx, value);
} else if (command == 1) {
int idx = randomInt(0, n - 2);
int value = 1 - b[idx];
setSummandBitAndChangeSumFast(b, idx, value);
} else {
int idx = randomInt(0, n - 2);
getSumNumberOfDigitsToTheRight(idx, 1);
}
}
}
private void setSummandBitAndChangeSumFast(int[] summand, int idx, int value) {
if (summand[idx] == 0) {
if (value == 0) {
// do nothing, no bit change
} else {
summand[idx] = 1;
increaseSumFast(idx);
}
} else {
if (value == 1) {
// do nothing, no bit change
} else {
summand[idx] = 0;
decreaseSumFast(idx);
}
}
}
private void increaseSumFast(int idx) {
// 0 -> 1 (numberOfOnes = 0)
// 11111110 -> 00000001 (numberOfOnes > 0)
int numberOfOnes = getSumNumberOfDigitsToTheRight(idx, 1);
inverseSumBits(idx, idx + numberOfOnes);
}
private void decreaseSumFast(int idx) {
// 1 -> 0 (numberOfOnes = 0)
// 00000001 -> 10000000 (numberOfOnes > 0)
int numberOfZeroes = getSumNumberOfDigitsToTheRight(idx, 0);
inverseSumBits(idx, idx + numberOfZeroes);
}
// inverses all bits in ['lo', 'hi'] range
private void inverseSumBits(int idxLo, int idxHi) {
inverseTree(1, 0, tSize - 1, idxLo, idxHi);
}
// returns the number of consecutive digit 'digit' to the right of 'idx'
private int getSumNumberOfDigitsToTheRight(int idx, int digit) {
return searchTree(1, 0, tSize - 1, idx, tSize - 1, digit);
}
// converts string to number
private int[] toArray(String s) {
int[] result = new int[n];
for (int i = 0; i < s.length(); i++) {
result[i] = s.charAt(s.length() - (i + 1)) - '0';
}
return result;
}
// calculates sum of a and b. the sum will always fit into the length
private int[] sum(int[] a, int[] b) {
int[] result = new int[n];
for (int i = 0, carry = 0; i < n; i++) {
int d = a[i] + b[i] + carry;
result[i] = d & 1;
carry = d >> 1;
}
return result;
}
int tSize;
TreeNode[] md;
class TreeNode {
boolean needToInverseChildren;
boolean isLeaf;
int lo, hi, len;
int[] cntToRight = new int[2];
TreeNode(boolean isLeaf, int lo, int hi) {
this.isLeaf = isLeaf;
this.lo = lo;
this.hi = hi;
this.len = hi - lo + 1;
}
void inverse() {
int t = cntToRight[0];
cntToRight[0] = cntToRight[1];
cntToRight[1] = t;
needToInverseChildren = !needToInverseChildren;
if (isLeaf) {
needToInverseChildren = false;
}
}
void recalc(TreeNode l, TreeNode r) {
for (int i = 0; i <= 1; i++) {
cntToRight[i] = l.cntToRight[i];
if (l.cntToRight[i] == l.len) {
cntToRight[i] += r.cntToRight[i];
}
}
}
}
private void doPushdown(int k) {
if (md[k].needToInverseChildren) {
{
int posL = k << 1;
md[posL].inverse();
}
{
int posR = (k << 1) + 1;
md[posR].inverse();
}
md[k].needToInverseChildren = false;
}
}
private int searchTree(int k, int a, int b, int lo, int hi, int digit) {
if (hi < a || lo > b || a > b || lo > hi) {
return 0;
}
if (a == lo && b == hi) {
return md[k].cntToRight[digit];
}
int posL = k << 1;
int posR = posL + 1;
int mid = (a + b) / 2;
doPushdown(k);
int cntL = searchTree(posL, a, mid, lo, Math.min(hi, mid), digit);
int cntR = searchTree(posR, mid + 1, b, Math.max(lo, mid + 1), hi, digit);
md[k].recalc(md[posL], md[posR]);
int result = cntL;
int lenL = Math.max(Math.min(hi, mid) - lo + 1, 0);
if (cntL == lenL) {
result += cntR;
}
return result;
}
private void inverseTree(int k, int a, int b, int lo, int hi) {
if (hi < a || lo > b || a > b || lo > hi) {
return;
}
doPushdown(k);
if (a == lo && b == hi) {
// inverse
md[k].inverse();
return;
}
int posL = k << 1;
int posR = posL + 1;
int mid = (a + b) / 2;
inverseTree(posL, a, mid, lo, Math.min(hi, mid));
inverseTree(posR, mid + 1, b, Math.max(lo, mid + 1), hi);
md[k].recalc(md[posL], md[posR]);
}
private TreeNode buildTree(int k, int a, int b) {
if (k >= tSize) {
int kIdx = k - tSize;
if (kIdx < n) {
// we are hitting a real node, so see what bit is that
md[k] = new TreeNode(true, a, b);
md[k].cntToRight[c[kIdx]]++;
} else {
// fake zero node
md[k] = new TreeNode(true, a, b);
md[k].cntToRight[0]++;
}
return md[k];
}
int mid = (a + b) / 2;
TreeNode l = buildTree(k << 1, a, mid);
TreeNode r = buildTree((k << 1) + 1, mid + 1, b);
md[k] = new TreeNode(false, a, b);
md[k].recalc(l, r);
return md[k];
}
private void initFastStructures() {
// build a tree out of d^p products
tSize = 1;
while (tSize < n) {
tSize <<= 1;
}
// 1 2 3 4 5 6 7
// [tsize - 1] [tsize]
int alloc = tSize << 1;
md = new TreeNode[alloc];
buildTree(1, 0, tSize - 1);
}
public void run() {
long timeStart = System.currentTimeMillis();
boolean fileIO = TASK_NAME_FOR_IO.length() > 0;
try {
if (fileIO) {
in = new BufferedReader(new FileReader(FILE_IN));
out = new PrintWriter(new BufferedWriter(new FileWriter(FILE_OUT)));
} else {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}
solve();
in.close();
out.close();
} catch (IOException e) {
throw new IllegalStateException(e);
}
long timeEnd = System.currentTimeMillis();
if (fileIO) {
System.out.println("Time spent: " + (timeEnd - timeStart) + " ms");
}
}
private String nextToken() throws IOException {
while (!tokenizer.hasMoreTokens()) {
String line = in.readLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer.nextToken();
}
private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
}
Python 3 rep HackerRank Solution
Python 2 rep HackerRank Solution
import sys
def main():
# get parameters
parameters = raw_input().split()
bitLength = int(parameters[0])
numQueries = int(parameters[1])
# get values for A and B
numA = int(raw_input(), 2)
numB = int(raw_input(), 2)
# run queries
for queryNum in range(numQueries):
query = raw_input().split()
command = query[0]
index = int(query[1])
if command == "set_a":
set = query[2]
if set == "1":
numA = setBit(numA, index)
else:
numA = clearBit(numA, index)
elif command == "set_b":
set = query[2]
if set == "1":
numB = setBit(numB, index)
else:
numB = clearBit(numB, index)
elif command == "get_c":
bit = testBit(numA + numB, index)
sys.stdout.write(bit)
def testBit(number, offset):
mask = 1 << offset
if number & mask:
return "1"
else:
return "0"
def setBit(number, offset):
mask = 1 << offset
return(number | mask)
def clearBit(number, offset):
mask = ~(1 << offset)
return(number & mask)
if __name__ == "__main__":
main()
C rep HackerRank Solution
#define MAX_NUM ((unsigned int)-1)
#define WORD_SIZE 32
#define DATA_TYPE unsigned int
#include <stdio.h>
int main()
{
DATA_TYPE A[3500] = {0}, B[3500] = {0}, C[3500] = {0};
unsigned int CARRY[3500] = {0};
int N, Q, N2;
int idx, x, lowest_modified_idx=0;
int i, j, rem;
char cmd[10];
char bit_string[100001];
scanf("%d %d", &N, &Q);
scanf("%s", bit_string);
N2 = N/WORD_SIZE;
rem = N % WORD_SIZE;
for ( i = 0 ; i < N2 ; ++i )
for ( j = 0 ; j < WORD_SIZE ; ++j )
if ( bit_string[N - 1 - (i*WORD_SIZE + j)] == '1' )
A[i] |= 1ULL << j;
if ( rem )
for ( j = 0 ; j < rem ; ++j )
if ( bit_string[ rem - j - 1 ] == '1' )
A[N2] |= 1ULL << j;
scanf("%s", bit_string);
for ( i = 0 ; i < N2 ; ++i )
for ( j = 0 ; j < WORD_SIZE ; ++j )
if ( bit_string[N - 1 - (i*WORD_SIZE + j)] == '1' )
B[i] |= 1ULL << j;
if ( rem )
for ( j = 0 ; j < rem ; ++j )
if ( bit_string[ rem - j - 1 ] == '1' )
B[N2] |= 1ULL << j;
for ( ; Q ; --Q )
{
scanf("%s %d", cmd, &idx);
switch(cmd[4])
{
case 'a':
scanf("%d", &x);
if ( x == 1 )
A[idx/WORD_SIZE] |= (1ULL << (idx%WORD_SIZE));
else
A[idx/WORD_SIZE] &= ~(1ULL << (idx%WORD_SIZE));
if ( idx < lowest_modified_idx )
lowest_modified_idx = idx;
break;
case 'b':
scanf("%d", &x);
if ( x == 1 )
B[idx/WORD_SIZE] |= (1ULL << (idx%WORD_SIZE));
else
B[idx/WORD_SIZE] &= ~(1ULL << (idx%WORD_SIZE));
if ( idx < lowest_modified_idx )
lowest_modified_idx = idx;
break;
case 'c':
if ( idx >= lowest_modified_idx )
{ for ( i = lowest_modified_idx/WORD_SIZE ; i <= idx/WORD_SIZE ; ++i )
{
CARRY[i+1] = 0;
if ( MAX_NUM - A[i] < B[i])
CARRY[i+1] = 1;
else if (A[i] < B[i] )
{ if ( MAX_NUM - A[i] - CARRY[i] < B[i] )
CARRY[i+1] = 1;
}
else if ( MAX_NUM - B[i] - CARRY[i] < A[i] )
{ CARRY[i+1] = 1;
}
C[i] = A[i] + B[i] + CARRY[i];
}
lowest_modified_idx = idx;
}
printf("%d", (C[idx/WORD_SIZE] & (1ULL << (idx%WORD_SIZE)))?1:0);
break;
// case 'd':
// for ( j = rem ; j >= 0 ; --j )
// printf("%d", (C[N/WORD_SIZE] & (1<<(j)))?1:0);
//
// for ( i = N/WORD_SIZE - 1 ; i >= 0; --i )
// for ( j = WORD_SIZE-1; j >= 0 ; --j )
// printf("%d", (C[i] & (1<<j))?1:0);
// printf("\n");
// break;
}
}
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
