We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Bit Manipulation
  4. A or B
  5. Discussions

A or B

Sort by

recency

|

38 Discussions

|

  • jmcparland
     + 0 comments

    Haskell

    Only half the points -- the others give a non-descript "Runtime Error", which I'd presume is memory. (I checked a few of the missed ones -- the answers are correct.) I'd rewrite it to process chunks, keeping things in the original hex until needed, etc. -- just not for 25 more points today X-)

    module Main where

-- https://www.hackerrank.com/challenges/aorb/problem

import Control.Monad (replicateM_)
import Data.Bits (Bits (shiftL, shiftR, (.&.)))
import Data.Char (toUpper)
import Data.Maybe (listToMaybe)
import Numeric (readHex, showHex)

-- utility functions

intToBinList :: Integer -> [Integer]
intToBinList 0 = [0]
intToBinList n = reverse (go n)
  where
    go 0 = []
    go x =
        let bit = x .&. 1
         in bit : go (x `shiftR` 1)

-- specifics

parseInputs :: (Integer, String, String, String) -> Maybe (Integer, Integer, Integer, Integer)
parseInputs (k, a, b, c) = do
    a' <- fst <$> listToMaybe (readHex a)
    b' <- fst <$> listToMaybe (readHex b)
    c' <- fst <$> listToMaybe (readHex c)
    return (k, a', b', c')

normalizeInputs :: (Integer, Integer, Integer, Integer) -> (Integer, [(Integer, Integer, Integer)])
normalizeInputs (k, a, b, c) =
    -- base arrays
    let al = intToBinList a
        bl = intToBinList b
        cl = intToBinList c
        -- normalize arrays, prepending zeros
        width = maximum [length al, length bl, length cl]
        a' = replicate (width - length al) 0 ++ al
        b' = replicate (width - length bl) 0 ++ bl
        c' = replicate (width - length cl) 0 ++ cl
     in -- return normalized inputs
        (k, zip3 a' b' c')

forcedPass :: (Integer, [(Integer, Integer, Integer)]) -> Maybe (Integer, [(Integer, Integer, Integer)])
forcedPass (k, zs) = do
    let (k', zs') = go k zs []
    if k' < 0
        then Nothing
        else Just (k', zs')
  where
    go k [] acc = (k, reverse acc)
    go k ((a, b, 0) : zs) acc = go (k - a - b) zs ((0, 0, 0) : acc)
    go k ((0, 0, 1) : zs) acc = go (k - 1) zs ((0, 1, 1) : acc)
    go k ((a, b, c) : zs) acc = go k zs ((a, b, c) : acc) -- leave it for now

discretionaryPass :: (Integer, [(Integer, Integer, Integer)]) -> (Integer, [(Integer, Integer, Integer)])
discretionaryPass (k, zs) = go k zs []
  where
    go k [] acc = (k, reverse acc) -- stopping condition
    go 0 (z : zs) acc = go 0 zs (z : acc) -- run it out
    go k ((0, 0, 0) : zs) acc = go k zs ((0, 0, 0) : acc) -- leave it
    go k ((0, 1, 1) : zs) acc = go k zs ((0, 1, 1) : acc) -- leave it
    go k ((1, 0, 1) : zs) acc =
        if k >= 2
            then go (k - 2) zs ((0, 1, 1) : acc)
            else go k zs ((1, 0, 1) : acc) -- leave it
    go k ((1, 1, 1) : zs) acc = go (k - 1) zs ((0, 1, 1) : acc)
    go k ((a, b, c) : zs) acc = error $ "discretionaryPass: unexpected values encountered: " ++ show (a, b, c)

reassemble :: (Integer, [(Integer, Integer, Integer)]) -> (Integer, Integer, Integer, Integer)
reassemble (k, zs) =
    let (as, bs, cs) = unzip3 zs
        a = foldl (\acc x -> acc `shiftL` 1 + x) 0 as
        b = foldl (\acc x -> acc `shiftL` 1 + x) 0 bs
        c = foldl (\acc x -> acc `shiftL` 1 + x) 0 cs
     in (k, a, b, c)

display :: (Integer, Integer, Integer, Integer) -> IO ()
display (k, a, b, c) = do
    putStrLn $ map toUpper $ showHex a ""
    putStrLn $ map toUpper $ showHex b ""

solve :: (Integer, String, String, String) -> Maybe (Integer, Integer, Integer, Integer)
solve inputs = do
    parsed <- parseInputs inputs
    let normalized = normalizeInputs parsed
    forced <- forcedPass normalized
    let discretionary = discretionaryPass forced
    return $ reassemble discretionary

main :: IO ()
main = do
    cases <- readLn :: IO Int
    replicateM_ cases $ do
        k <- readLn :: IO Integer
        aHex <- getLine
        bHex <- getLine
        cHex <- getLine
        let inputs = (k, aHex, bHex, cHex)
        case solve inputs of
            Just sol -> display sol
            Nothing -> putStrLn "-1"

  • callummequigley
     + 0 comments

    python3

    def aOrB(k, a, b, c):  
    # Convert a, b, c to (0-left-padded) binary arrays
    bin_len = 4*max(map(len, [a, b, c]))
    a_bin, b_bin, c_bin = map(lambda x: [*map(int, f'{int(x, 16):0>{bin_len}b}')], [a, b, c])
    
    # First pass: perform minimal bit changes to satisfy a'|b'==c
    a_new, b_new = [], []
    for x, y, z in zip(a_bin, b_bin, c_bin):
        if (x | y) ^ z == 1:
            if (x | y) == 0:
                y = 1  # only change bit in b, to keep a' minimal
                k -= 1
            else:
                k -= x+y
                x, y = 0, 0
        a_new.append(x)
        b_new.append(y)
    
    # If after initial pass k<0, then no solution
    if k < 0:
        print(-1)
    else:
        # If k>0, can look for further minimizations
        for i in range(bin_len):
            if k == 0:
                break
            elif (a_new[i], b_new[i]) == (1, 1):
                a_new[i] = 0
                k -= 1
            elif ((a_new[i], b_new[i]) == (1, 0)) and (k > 1):
                a_new[i], b_new[i] = 0, 1
                k -= 2
        
        a_new_hex, b_new_hex = map(lambda x: hex(int(''.join(map(str, x)), 2))[2:].upper(), [a_new, b_new])
        print('\n'.join([a_new_hex, b_new_hex]))

  • mryo531
     + 0 comments

    Simple python solution that follows the methodology described by the editorial

    Note: My initial implementation used masks to read and set the bits, but I found this wasn't fast enough for the last 3 tests. Converting to an array and accessing the bits by index proved to be much faster.

    #!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'aOrB' function below.
#
# The function accepts following parameters:
#  1. INTEGER k
#  2. STRING a
#  3. STRING b
#  4. STRING c
#

def aOrB(k, a, b, c):
    # Write your code here
    a_arr = [int(i) for i in bin(int(a, 16))[2:]]
    b_arr = [int(i) for i in bin(int(b, 16))[2:]]
    c_arr = [int(i) for i in bin(int(c, 16))[2:]]
    
    a_mod = 4 - len(a_arr) % 4
    b_mod = 4 - len(b_arr) % 4
    c_mod = 4 - len(c_arr) % 4
    if a_mod < 4:
        a_arr[:0] = [0] * a_mod
    if b_mod < 4:
        b_arr[:0] = [0] * b_mod
    if c_mod < 4:
        c_arr[:0] = [0] * c_mod

    swap = 0
    for i in range(len(c_arr)):
        if c_arr[i]:
            if not a_arr[i] and not b_arr[i]:
                b_arr[i] = 1
                swap += 1
        else:
            if a_arr[i]:
                a_arr[i] = 0
                swap += 1
            if b_arr[i]:
                b_arr[i] = 0
                swap += 1

        if swap > k:
            print(-1)
            return
    
    left_over = k - swap
    for i in range(len(c_arr)):
        if left_over == 0:
            break
            
        if a_arr[i]:
            if b_arr[i]:
                a_arr[i] = 0
                left_over -= 1
            elif left_over >= 2:
                a_arr[i] = 0
                b_arr[i] = 1
                left_over -= 2
    
    a = int(''.join([str(i) for i in a_arr]), 2)
    b = int(''.join([str(i) for i in b_arr]), 2)
    print(hex(a)[2:].upper())
    print(hex(b)[2:].upper())
        

if __name__ == '__main__':
    q = int(input().strip())

    for q_itr in range(q):
        k = int(input().strip())

        a = input()

        b = input()

        c = input()

        aOrB(k, a, b, c)

  • jankeshchakrava1
     + 0 comments

    Can anyone help me what is wrong with below code? For this particular problem, there could be multiple solutions. void aOrB(int k, char* a, char* b, char* c) { long long num_a, num_b, num_c; //printf("sizeof num_a = %d \n",sizeof(num_a)); num_a = my_atoi(a); num_b = my_atoi(b); num_c = my_atoi(c); /printf("a:%s -->%ld ",a,num_a); printf("b:%s -->0x%x ",b,num_b); printf("c:%s -->0x%x \n",c,num_c);/

    // First clear the bits from value a
num_a &= num_c;


// Clear the bits from value b
num_b &= num_c;


// Now first OR a and b, then find how many bits 
// temp is short off and it's bit position.
long long temp = num_a | num_b;

temp ^= num_c;

num_a |= temp;


if ((num_a | num_b) == num_c) 
    printf("num_a: 0x%x | num_b:0x%x = 0x%x\n",num_a, num_b, num_c);

int count = (countOne(my_atoi(a)^num_a)) + (countOne(my_atoi(b)^num_b));

if ( count > k)
    printf("-1");
else {
    printf("%ld \n",num_a);
    printf("%ld \n",num_b);
}

printf("\n-------\n");

  • dehaka
     + 1 comment

    question is quite straightforward, but lots of things to consider, and very long code

    vector<bitset<4>> HexToBinary (string x) {
    vector<bitset<4>> result;
    for (int i=0; i < x.size(); i++) {
        int k;
        if (x[i] <= 57) {
            k = x[i] - 48;
        } else {
            k = x[i] - 55;
        }
        bitset<4> temp(k);
        result.push_back(temp);
    }
    return result;
}

string BinaryToHex (vector<bitset<4>> x) {
    string result;
    for (int i=0; i < x.size(); i++) {
        int k = x[i].to_ulong();
        if (k < 10) {
            result.push_back(static_cast<char>(k+48));
        } else {
            result.push_back(static_cast<char>(k+55));
        }
    }
    int index = 0;
    while (index < result.size()-1) {
        if (result[index] != '0') {
            break;
        }
        index++;
    }
    result.erase(result.begin(), result.begin()+index);
    return result;
}

void aOrB(int k, string a, string b, string c) {
    vector<bitset<4>> binaryA = HexToBinary(a);
    vector<bitset<4>> binaryB = HexToBinary(b);
    vector<bitset<4>> binaryC = HexToBinary(c);
    int changesRemaining = k;
    
    //make necessary changes to A and B
    int d1 = binaryA.size() - binaryC.size();
    int d2 = binaryB.size() - binaryC.size();
    for (int i=0; i < d1; i++) {
        changesRemaining = changesRemaining - binaryA[i].count();
    }
    for (int i=0; i < d2; i++) {
        changesRemaining = changesRemaining - binaryB[i].count();
    }
    binaryA.erase(binaryA.begin(), binaryA.begin()+d1);
    binaryB.erase(binaryB.begin(), binaryB.begin()+d2);
    d1 = binaryA.size() - binaryC.size();
    d2 = binaryB.size() - binaryC.size();
    binaryA.insert(binaryA.begin(), abs(d1), bitset<4>());
    binaryB.insert(binaryB.begin(), abs(d2), bitset<4>());
    for (int i=0; i < binaryC.size(); i++) {
        for (int j=3; j >= 0; j--) {
            if (binaryC[i][j] == 0) {
                changesRemaining = changesRemaining - binaryA[i][j] - binaryB[i][j];
                binaryA[i][j] = 0;
                binaryB[i][j] = 0;
            }
            if (binaryC[i][j] == 1 and (binaryA[i][j] | binaryB[i][j]) == 0) {
                binaryB[i][j] = 1;
                changesRemaining--;
            }
        }
    }
    if (changesRemaining < 0) {
        cout << -1 << "\n";
        return;
    }
    
    //optimize A and B, try to make A the smallest possible
    for (int i=0; i < binaryC.size(); i++) {
        for (int j=3; j >= 0; j--) {
            if (changesRemaining == 0) {
                cout << BinaryToHex(binaryA) << "\n" << BinaryToHex(binaryB) << "\n" ;
                return;
            }
            if (binaryC[i][j] == 1) {
                if ((binaryA[i][j]&binaryB[i][j]) == 1) {
                    binaryA[i][j] = 0;
                    changesRemaining--;
                } else if (binaryA[i][j] == 1 and binaryB[i][j] == 0 and changesRemaining >= 2) {
                    binaryA[i][j] = 0;
                    binaryB[i][j] = 1;
                    changesRemaining = changesRemaining - 2;
                }
            }
        }
    }
    cout << BinaryToHex(binaryA) << "\n" << BinaryToHex(binaryB) << "\n" ;
}