A or B


Problem Statement :


Consider four numbers: , , , and . You must change at most  bits in  and  to form the numbers  and  satisfying the equation . Here, the | symbol denotes the bitwise OR operation.

Given  sets of the numbers defined above, find and print the respective values of  and  on new lines; if no such value exists, print  instead. If there are multiple solutions, make  as small as possible; if there are still multiple solutions, make  as small as possible.

Input Format

The first line contains an integer, , denoting the number of queries. The subsequent lines describe each respective query as follows:

The first line contains a single integer denoting the value of .
Each of the next  lines contains a Hexadecimal (base 16) number describing the respective values of , , and .


Output Format

Print two lines of output for each query:

The first line should contain a Hexadecimal (base 16) number denoting the value of  A'.
The second line must contain a Hexadecimal (base 16) number denoting the value of B'.
If no valid answer exists, you must instead print one line of output with the integer  1.

Note: The letters in Hexadecimal numbers must be in uppercase.



Solution :



title-img


                            Solution in C :

In  C  :





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

int n;
char s[500000];
int a[500000],b[500000],c[500000];

void trans1(char s[],int a[]) {
    int i,l=strlen(s);
    for(i=0;i<l;i++) if (s[i]>='A') a[l-i-1]=s[i]-'A'+10; else a[l-i-1]=s[i]-'0';
}

void trans2(int a[],int l,char s[]) {
    int i;
    while(l>1 && a[l-1]==0) l--;
    for(i=0;i<l;i++) if (a[i]>=10) s[l-1-i]=a[i]-10+'A'; else s[l-1-i]=a[i]+'0';
    s[l]='\0';
}

int main() {
    int i,N,l1,l2,l3,l,j,aa,bb,cc,dd,ee;
    for(scanf("%d",&N);N--;) {
        scanf("%d",&n);
        scanf("%s",s);
        trans1(s,a);
        l1=strlen(s);
        scanf("%s",s);
        trans1(s,b);
        l2=strlen(s);
        scanf("%s",s);
        trans1(s,c);
        l3=strlen(s);
        l=l1;
        if (l2>l) l=l2;
        if (l3>l) l=l3;
        for(i=0;i<l && n>=0;i++) for(j=0;j<4 && n>=0;j++) {
            aa=(a[i]>>j)&1;
            bb=(b[i]>>j)&1;
            cc=(c[i]>>j)&1;
            if (!cc) {
                if (aa) a[i]&=15^(1<<j),n--;
                if (bb) b[i]&=15^(1<<j),n--;
            } else if (!aa && !bb) {
                b[i]|=1<<j,n--;
            }
        }
        for(i=l-1;i>=0 && n>0;i--) for(j=3;j>=0 && n>0;j--) {
            aa=(a[i]>>j)&1;
            bb=(b[i]>>j)&1;
            cc=(c[i]>>j)&1;
            if (aa && bb) a[i]&=15^(1<<j),n--;
            else if (aa && !bb && n>1) a[i]&=15^(1<<j),b[i]|=1<<j,n-=2;
        }
        if (n<0) {
            puts("-1");
            continue;
        }
        trans2(a,l,s);
        printf("%s\n",s);
        trans2(b,l,s);
        printf("%s\n",s);
    }
    return 0;
}
                        


                        Solution in C++ :

In  C ++  :








#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void PR(vi &v) { trav(x, v) cout << x << ' '; cout << endl; }

void unhex(char& c) {
	if (0 <= c && c < 10) c = (char)('0' + c);
	else c = (char)('A' + (c - 10));
}

void rehex(char& c) {
	if ('0' <= c && c <= '9') c = (char)(c - '0');
	else c = (char)(c - 'A' + 10);
}

string trim0(string& s) {
	trav(x, s) unhex(x);
	rep(i,0,sz(s)) {
		if (s[i] != '0') return s.substr(i);
	}
	return "0";
}

bool solve() {
	int K, N;
	string a, b, c;
	cin >> K;
	cin >> a >> b >> c;
	N = max(max(sz(a), sz(b)), sz(c));
	a = string(N-sz(a), '0') + a;
	b = string(N-sz(b), '0') + b;
	c = string(N-sz(c), '0') + c;
	trav(x, a) rehex(x);
	trav(x, b) rehex(x);
	trav(x, c) rehex(x);
	int bits[4] = {8,4,2,1};

	rep(i,0,N) trav(bi, bits) {
		if (!(c[i]&bi)) {
			if (a[i]&bi) {
				a[i] &= ~bi;
				--K;
			}
			if (b[i]&bi) {
				b[i] &= ~bi;
				--K;
			}
		}
		else {
			if (!((a[i]&bi) || (b[i]&bi))) {
				b[i] |= bi;
				--K;
			}
		}
	}

	if (K < 0) return false;

	rep(i,0,N) trav(bi, bits) {
		if (c[i]&bi) {
			if ((a[i]&bi) && (b[i]&bi) && K >= 1) {
				a[i] &= ~bi;
				K--;
			}
			else if ((a[i]&bi) && K >= 2) {
				a[i] &= ~bi;
				b[i] |= bi;
				K -= 2;
			}
		}
	}

	cout << trim0(a) << endl;
	cout << trim0(b) << endl;
	return true;
}

int main() {
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	int N;
	cin >> N;
	rep(i,0,N) {
		if (!solve()) cout << -1 << endl;
	}
}
                    


                        Solution in Java :

In  Java :







import java.io.*;
import java.math.BigInteger;
import java.util.*;



public class B
{
    String line;
    StringTokenizer inputParser;
    BufferedReader is;
    FileInputStream fstream;
    DataInputStream in;
    String FInput="";
    
    void openInput(String file)
    {

            if(file==null)is = new BufferedReader(new InputStreamReader(System.in));//stdin
            else
            {
                    try{
            
                            
                    fstream = new FileInputStream(file);
                    in = new DataInputStream(fstream);
                    is = new BufferedReader(new InputStreamReader(in));
                    }catch(Exception e)
                    {
                            System.err.println(e);
                    }
            }

    }
    
    void readNextLine()
	{
		try {
			line = is.readLine();
			inputParser = new StringTokenizer(line, " ,\t");
			//System.err.println("Input: " + line);
		} catch (IOException e) {
			System.err.println("Unexpected IO ERROR: " + e);
		}	
		catch (NullPointerException e)
		{
			line=null;
			
		}
		
	}
    
    long NextLong()
    {
            String n = inputParser.nextToken();
            
            long val = Long.parseLong(n);
            
             return val;
    }
    
    int NextInt()
    {
            String n = inputParser.nextToken();
            int val = Integer.parseInt(n);
            
            //System.out.println("I read this number: " + val);
            return val;
    }
    
    double NextDouble()
    {
            String n = inputParser.nextToken();
            double val = Double.parseDouble(n);
            
            //System.out.println("I read this number: " + val);
            return val;
    }
    
    String NextString()
    {
            String n = inputParser.nextToken();
            return n;
    }
    
    void closeInput()
    {
            try {
                    is.close();
            } catch (IOException e) {
                    System.err.println("Unexpected IO ERROR: " + e);
            }
                    
    }
    
    public static void main(String [] argv)
    {
            //String filePath="circles.in";
            String filePath=null;
            if(argv.length>0)filePath=argv[0];
            new B(filePath);
            
    }
    
    public B(String inputFile)
    {
    	openInput(inputFile);
		readNextLine();
		int T=NextInt();
		StringBuilder sb = new StringBuilder();
		for(int t=1; t<=T; t++)
		{
			readNextLine();
			int K = NextInt();
			readNextLine();
			//String A = line;
			//BigInteger a = new BigInteger(A, 16);
			boolean [] a = hexStringToBooleanArray(line);
			readNextLine();
			//String B = line;
			//BigInteger b = new BigInteger(B, 16);
			boolean [] b = hexStringToBooleanArray(line);
			readNextLine();
			//String C = line;
			//BigInteger c = new BigInteger(C, 16);
			boolean [] c = hexStringToBooleanArray(line);
			
			int len = a.length;
			len = Math.max(len, b.length);
			len = Math.max(len, c.length);
			boolean [] ra = new boolean[len];
			and(ra, a,c);
			boolean [] rb = new boolean[len];
			and(rb, b,c);
			boolean [] cxra = new boolean[len];
			xor(cxra, c, ra);
			or(rb, rb, cxra);
			boolean [] xa = new boolean[len];
			int da = xor(xa, ra, a);
			boolean [] xb = new boolean[len];
			int db = xor(xb, rb, b);
			if(da+db>K){
				sb.append("-1\n");
			}
			else{
				int dd = K - da - db;
				if(dd>0)
				{
					boolean [] X = new boolean[len];
					for(int i=0; i<ra.length&&dd>0; i++){
						if(ra[i])
						{
							if(dd==1&&!rb[i])continue;
							dd--;
							X[i]=true;
							if(!rb[i])dd--;
						}
					}
					xor(ra, ra, X);
					or(rb, rb, X);
				}
				sb.append(toStr(ra)+"\n");
				sb.append(toStr(rb)+"\n");
			}
			/*
			BigInteger ra = a.and(c);
			BigInteger rb = b.and(c).or(c.xor(ra));
			int da = a.xor(ra).bitCount();
			int db = b.xor(rb).bitCount();
			if(da+db>K)sb.append("-1\n");
			else
			{
				int dd = K - da - db;
				if(dd>0)
				{
					/*String x = ra.toString(2);
					BigInteger X = BigInteger.ZERO;
					for(int i=0; i<x.length()&&dd>0; i++){
						if(x.charAt(i)=='1')
						{
							if(dd==1&&!rb.testBit(x.length()-i-1))continue;
							dd--;
							X = X.setBit(x.length()-i-1);
							if(!rb.testBit(x.length()-i-1))dd--;
						}
					}
					ra = ra.xor(X);
					rb = rb.or(X);*
				}
				sb.append(ra.toString(16).toUpperCase()+"\n");
				sb.append(rb.toString(16).toUpperCase()+"\n");
			}*/
		}
		System.out.print(sb);
		
		closeInput();		
	}
    
    private String toStr(boolean[] rb) {
		StringBuilder sb = new StringBuilder();
		
		for(int i=0; i<rb.length; i++)
			if(rb[i])sb.append(1);
			else sb.append(0);
		BigInteger b = new BigInteger(sb.toString(), 2);
		return b.toString(16).toUpperCase();
	}

	private void or(boolean[] xa, boolean[] ra, boolean[] a) {
    	int len = xa.length;
		len = Math.min(len, ra.length);
		len = Math.min(len, a.length);
		for(int i=0; i<len; i++){
			xa[xa.length-i-1] = a[a.length - i - 1]|ra[ra.length - i - 1];
		}
	}
    
    private int xor(boolean[] xa, boolean[] ra, boolean[] a) {
    	int len = xa.length;
		len = Math.min(len, ra.length);
		len = Math.min(len, a.length);
		int ret = 0;
		for(int i=0; i<len; i++){
			xa[xa.length-i-1] = a[a.length - i - 1]^ra[ra.length - i - 1];
			if(xa[xa.length-i-1])ret++;
		}
		return ret;
	}

	private void and(boolean[] ra, boolean[] a, boolean[] b) {
    	int len = a.length;
		len = Math.min(len, b.length);
		len = Math.min(len, ra.length);
		for(int i=0; i<len; i++){
			ra[ra.length-i-1] = a[a.length - i - 1]&b[b.length - i - 1];
		}
	}

	public boolean [] hexStringToBooleanArray(String s) {
    	int len = s.length();
    	boolean [] ret = new boolean[len*4];
    	for(int i=0; i<len; i++){
    		int x = Character.digit(s.charAt(i), 16);
    		if((x&1)>0)ret[i*4+3] = true;
    		if((x&2)>0)ret[i*4+2] = true;
    		if((x&4)>0)ret[i*4+1] = true;
    		if((x&8)>0)ret[i*4] = true;
    	}
    	return ret;
    }
    
    public byte[] hexStringToByteArray(String s) {
        int len = s.length();
        byte[] data = new byte[len / 2];
        for (int i = 0; i < len; i += 2) {
            data[i / 2] = (byte) ((Character.digit(s.charAt(i), 16) << 4)
                                 + Character.digit(s.charAt(i+1), 16));
        }
        return data;
    }

}
                    


                        Solution in Python : 
                            
In  Python3 :







Q = int(input())
for _ in range(Q):
    k = int(input())
    A = bin(int(input(), 16))[2:]
    B = bin(int(input(), 16))[2:]
    C = bin(int(input(), 16))[2:]
    
    l = max(len(A), len(B), len(C))
    A = list('0' * (l - len(A)) + A)
    B = list('0' * (l - len(B)) + B)
    C = list('0' * (l - len(C)) + C)
    
    for i in range(l):
        if A[i] == B[i] == '0' and C[i] == '1':
            B[i] = '1'
            k -= 1
        
        if A[i] > C[i] or B[i] > C[i]:
            if A[i] == '1':
                A[i] = '0'
                k -= 1
            
            if B[i] == '1':
                B[i] = '0'
                k -= 1
    
    if k < 0:
        print(-1)
        
        continue
    
    for i in range(l):
        if A[i] == '1' and B[i] == '1' and k > 0:
            A[i] = '0'
            k -= 1
        
        if A[i] == '1' and B[i] == '0' and k > 1:
            A[i] = '0'
            B[i] = '1'
            k -= 2
    
    print("%X" % int(''.join(A), 2))
    print("%X" % int(''.join(B), 2))
                    


View More Similar Problems

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →