HackerRank A or B problem solution

In this HackerRank A or B problem solution we have Given Q sets of the numbers defined above, find and print the respective values of A and B on new lines; if no such value exists, print -1 instead. If there are multiple solutions, make A as small as possible; if there are still multiple solutions, make B as small as possible.

Problem solution in Python.

def calculate(A,B,C,k):
    n = max(len(A), len(B), len(C))
    A,B,C = ([0]*(n-len(x)) + x for x in (A,B,C))
    for i,a,b,c in zip(range(n),A,B,C):
        #print(*(A,B,C), sep="\n")
        if a | b < c:
            B[i] = 1
            k -= 1
        elif a | b > c:
            k -= a + b
            A[i] = B[i] = 0
        if k < 0:
            return [-1]
        #print(k)
    for i,a,b in zip(range(n), A,B):
        if a > b and k >= 2:
            A[i],B[i] = 0, 1
            k -= 2
        elif a >= b >= 1 and k:
            A[i] = 0
            k -= 1
    A,B = (hex(int("".join(map(str, x)), 2))[2:].upper() for x in (A,B))
    return A,B

q = int(input())
for i in range(q):
    k = int(input())
    a,b,c = (list(map(int, bin(int(input(), 16))[2:])) for i in range(3))
    print(*calculate(a,b,c,k), sep="\n")

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {
    static byte[] hexStringToByteArray(String s) {
        int len = s.length();
        int bl = len/2;
        if(s.length()%2==1) bl++;
        byte[] data = new byte[bl];
        for (int i = 0; i < len/2; i += 1) {
            data[i] = (byte) ((Character.digit(s.charAt(i*2), 16) << 4)
                    + Character.digit(s.charAt(i*2+1), 16));
        }
        if(s.length()%2==1)data[bl-1]=(byte) ((Character.digit(s.charAt(len-1), 16) << 4));
        return data;
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for(int i1=0;i1<T;i1++){
            int k = in.nextInt();
            String s1 = in.next();
            String s2 = in.next();
            String tar = in.next();
            System.out.println(p(k,s1,s2,tar));
        }
     }
    static String p(int k, String s1, String s2,String tar){
        int n = s1.length();
        byte[] b1 = hexStringToByteArray(s1);
        byte[] b2 = hexStringToByteArray(s2);
        byte[] btar = hexStringToByteArray(tar);
        for(int i=0;i<b1.length;i++){
            for(int j=0;j<8;j++){
                int bit = (1<<j);
                if((btar[i] & bit)==0){
                    if((b1[i]&bit)!=0){
                        b1[i]= (byte)(b1[i]&(~bit));
                        k--;
                    }
                    if((b2[i]&bit)!=0){
                        b2[i]= (byte)(b2[i]&(~bit));
                        k--;
                    }
                }else{
                    if((b1[i]&bit)==0&&(b2[i]&bit)==0){
                        b2[i]= (byte)(b2[i]|(bit));
                        k--;
                    }
                }
            }
        }
        if(k<0) return "-1";
        for(int i=0;i<b1.length&&k>0;i++){
            for(int j=7;j>=0&&k>0;j--){
                int bit = (1<<j);
                if((b1[i] & bit)!=0){
                    if((b2[i]&bit)!=0){
                        b1[i]= (byte)(b1[i]&(~bit));
                        k--;
                    }else if(k>1){
                        b1[i]= (byte)(b1[i]&(~bit));
                        b2[i]= (byte)(b2[i]|(bit));
                        k-=2;
                    }
                }
            }
        }
        StringBuilder sb =new StringBuilder(2*n+1);
        putString(b1,sb,n);
        sb.append('\n');
        putString(b2,sb,n);
        return sb.toString();
    }
    private static void putString(byte[] b, StringBuilder sb, int n){
        boolean zero = true;
        int initlth = sb.length();
        for(int i=0;i<n/2;i++){
            char c1 = HEXES.charAt((b[i] & 0xF0) >> 4);
            char c2 = HEXES.charAt((b[i] & 0x0F));
            if(zero){
                if(c1!='0'){
                    zero = false;
                    sb.append(c1);
                }
            }else{
                sb.append(c1);
            }
            if(zero){
                if(c2!='0'){
                    zero = false;
                    sb.append(c2);
                }
            }else{
                sb.append(c2);
            }
        }
        if(n%2==1) sb.append(HEXES.charAt((b[n/2] & 0xF0) >> 4));
        if(sb.length() == initlth) sb.append('0');
    }
    private static final String    HEXES    = "0123456789ABCDEF";
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

string nextToken() {
    static const int MAX_LEN = 1000 * 1000 + 5;
    static char buffer[MAX_LEN];
    scanf("%s", buffer);
    return buffer;
}

vector<bool> readHex() {
    string s = nextToken();
    reverse(s.begin(), s.end());
    vector<bool> res;
    for (char c : s) {
        int x = (c >= '0' && c <= '9' ? (c - '0') : (c - 'A' + 10));
        for (int i = 0; i < 4; i++) {
            res.push_back((x & 1) ? true : false);
            x >>= 1;
        }
    }
    return res;
}

string toHex(vector<bool> v) {
    while (!v.empty() && !v.back()) v.pop_back();
    while (v.empty() || v.size() % 4 != 0) v.push_back(false);
    string res;
    for (int i = (int)v.size() - 1; i >= 0; i -= 4) {
        int cur = 0;
        for (int j = 0; j < 4; j++) {
            cur *= 2;
            if (v[i - j]) cur++;
        }
        res.push_back(cur <= 9 ? cur + '0' : cur - 10 + 'A');
    }
    return res;
}

void solve() {
    int k;
    scanf("%d", &k);
    vector<bool> A, B, C;
    A = readHex();
    B = readHex();
    C = readHex();
    int len = (int)max(A.size(), max(B.size(), C.size()));
    while ((int)A.size() < len) A.push_back(false);
    while ((int)B.size() < len) B.push_back(false);
    while ((int)C.size() < len) C.push_back(false);
    int cnt = 0;
    for (int i = 0; i < len; i++) {
        if (!C[i]) {
            if (A[i]) cnt++;
            if (B[i]) cnt++;
        }
        else {
            if (!A[i] && !B[i]) cnt++;
        }
    }
    if (cnt > k) {
        puts("-1");
        return;
    }
    int rem = k - cnt;
    for (int i = len - 1; i >= 0; i--) {
        if (!C[i]) {
            if (A[i]) A[i] = false;
            if (B[i]) B[i] = false;
        }
        else {
            if (!A[i] && !B[i]) {
                B[i] = true;
            }
            else {
                if (A[i] && B[i]) {
                    if (rem) {
                        A[i] = false;
                        rem--;
                    }
                }
                else if (A[i] && !B[i]) {
                    if (rem >= 2) {
                        A[i] = false;
                        B[i] = true;
                        rem -= 2;
                    }
                }
            }
        }
    }
    printf("%s\n%s\n", toHex(A).c_str(), toHex(B).c_str());
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

Problem solution in C.

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

#define Lim 50001
#define Siz 200000

static inline unsigned hctou(char c) {
    static char s[2]= {0, 0};
    *s=c;
    return strtoul(s, NULL, 16);
}

static inline char hex(unsigned x) {
    static char s[2];
    sprintf(s, "%X", x);
    return *s;
}

void output(char *X, char *s) {
    int i;
    for(i=Siz; i>4 && !(X[i-1]|X[i-2]|X[i-3]|X[i-4]); i-=4);
    char *p;
    for(p=s; i>0; i-=4)
        *p++=hex(X[i-1]<<3|X[i-2]<<2|X[i-3]<<1|X[i-4]);
    *p=0;
    puts(s);
}

void input(char *X, char *s) {
    scanf("%s", s);
    int l=strlen(s);
    bzero(X, Siz-4*l);
    for(int i=4*l; i>0; i-=4) {
        int v=hctou(*s++);
        for(int j=4; j; v>>=1)
            X[i-j--]=v&1;
    }
}

int main() {
    char *A = malloc(Siz*sizeof(char));
    char *B = malloc(Siz*sizeof(char));
    char *C = malloc(Siz*sizeof(char));
    char *s = malloc(Lim*sizeof(char));
    int Q, K;
    assert(1==scanf("%u", &Q));
    for(int a0=0; a0<Q; a0++) {
        assert(1==scanf("%d", &K));
        input(A, s);
        input(B, s);
        input(C, s);
        for(int i=Siz; i--; ) {
            if(A[i]&&!C[i])
                A[i]=0,K--;
            if(B[i]&&!C[i])
                B[i]=0,K--;
            if(C[i]&&!A[i]&&!B[i])
                B[i]=1,K--;
        }
        if(K<0) {
            puts("-1");
            continue;
        }
        for(int i=Siz; K&&i--; )
            if(K>1) {
                if(A[i]) {
                    A[i]=0,K--;
                    if(!B[i])
                        B[i]=1,K--;
                }
            } else {
                if(A[i]&&B[i])
                    A[i]=0,K--;
            }
        for(int i=Siz; K&&i--; )
            if(A[i]&&B[i])
                B[i]=0,K--;
        output(A, s);
        output(B, s);
    }
    return 0;
}