Faulty Key
Ninja is trying to write a function that takes two integers and returns their sum. But, due to some faults in his keyboard, he can not use the “+”, operator, which means he is not able to simply return ‘A’ + ‘B’, where ‘A’ and 'B' are the numbers to be added. You need to help Ninja in finding the sum of two numbers without using the "+" operator anywhere in your code.

Note:

You should also not use the increment "++" operator too.

For example :

You are given A = 4, B = 6, their sum = 10, you need to return 10.

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows. The first and only line of each test case contains two space-separated integers denoting ‘A’ and ‘B’ respectively.

Output Format:

For each test case, print the sum of the two numbers without using the “+” operator. Print the output of each test case in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1

Question

Faulty Key

Ninja is trying to write a function that takes two integers and returns their sum. But, due to some faults in his keyboard, he can not use the “+”, operator, which means he is not able to simply return ‘A’ + ‘B’, where ‘A’ and 'B' are the numbers to be added. You need to help Ninja in finding the sum of two numbers without using the "+" operator anywhere in your code.

Note:

 You should also not use the increment "++" operator too.

For example :

You are given A = 4, B = 6, their sum = 10, you need to return 10.

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first and only line of each test case contains two space-separated integers denoting ‘A’ and ‘B’ respectively.

Output Format:

For each test case, print the sum of the two numbers without using the “+” operator.

Print the output of each test case in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 100
-10000 <= A, B <= 10000

where ‘T’ is the number of test cases and ‘A’ and ‘B’ are the two integers.

Time limit: 1 sec

Accepted Answer

Using a subtraction operator.

This is a very basic approach. In this approach, we will be simply subtracting the negative of the second number from the first number.

For example: A = 4, B = 6
Now, negative of second number = -6
Subtracting this from the first number = 4 - (-6) = 4 + 6 = 10
So, for this approach, you simply need to return A - (- B)

Space Complexity: O(1)Explanation:

O(1)

Since we are not using any extra space, the overall space complexity is O(1).

Time Complexity: O(1)Explanation:

O(1)

Since we are using a simple arithmetic operation, the overall time complexity is O(1).

Java (SE 1.8)

/*

	Time complexity: O(1) 

	Space complexity: O(1)

*/



public class Solution {

	public static int getSum(int a, int b) {



		// Initialise a variable and store the negative of the second number in it.

		int x = (-b);



		// Subtract this number from the first number and store it in another variable.

		int ans = a - x;



		// Return ans.

		return ans;

	}

}

C++ (g++ 5.4)

/*

	Time complexity: O(1) 

	Space complexity: O(1)

*/





int getSum(int a, int b)

{

    // Initialise a variable and store the negative of the second number in it.

    int x = (-b);



    // Subtract this number from the first number and store it in another variable.

    int ans = a - x;



    // Return ans.

    return ans;

}

Python (3.5)

'''

    Time complexity: O(1) 

	Space complexity: O(1)

'''



def getSum(a, b):

    

    # Store the negative of the second number.

    x = -b

    # Subtract this number from the first number.

    ans = a - x

    

    return ans

Accepted Answer

Extending the Half Adder logic

In this approach, we will use the logic behind the half adder that is used to find the sum of single bits and extend it so that we could add integers.

We will start with XOR of the two numbers A and B.
Then we will find the AND of A and B in order to find the carry, and then left shift the carry until it becomes 0.
Finally we will do the OR of XOR and Carry to get the sum of the numbers.

To understand it better, let’s take an example of some numbers that use carry:

Suppose A = 6 and B = 7:

Binary conversion gives: A = 6 = 00110 and B = 7 = 00111
First you find the carries:
- that is all positions where both a and b has its bit set:
  - int carry = (a & b) ;
Then it does the addition of digits, ignoring the carry, and stores it in a:
- a = a ^ b:
  - This will respond to 6+7=3 in the example.
The last part shifts the carry to the next digit position, i.e. ensuring the 1-carry in the example is "moved" from the 1's to the 10's:
- carry << 1;
The while loop continues as long as there are carries that has not been included in the sum.

NOTE: We can also use the “print” to find the sum, by using “%*s”, Here, the “%*s” specifier print value of a variable, the value of variable times, and printf return how many characters print on the screen., but this approach will not work in case of negative numbers, hence not included in this question.

Space Complexity: O(1)Explanation:

O(1)

Since we are not using any extra space, overall space complexity is O(1).

Time Complexity: O(logn)Explanation:

O(log(MAX(A, B)), where MAX(A, B) denotes the maximum integer between ‘A’ and ‘B’.

Since we are looping and doing some arithmetic operations until the carry becomes zero and the loop can run for log(MAX(A, B)) times in the worst case. So the overall time complexity will be O(log(MAX(A,B)).

C++ (g++ 5.4)

/*

	Time complexity: O(log(MAX(A, B))) 

	Space complexity: O(1)

	

    where MAX(A, B) denotes the maximum integer between ‘A’ and ‘B’. 

*/



int getSum(int a, int b)

{

    

    // Traverse until there is no carry left.

    while (b != 0) 

    {



        // Initialise a variable that will store the common set bits.

        int carry = a & b;



        // Update first number with the sum of bits of both number 

        // when at least one of the bits is not set.

        a = a ^ b;



        // Shift the carry by one.

        b = carry << 1;

    }



    // Return updated first number.

    return a;

}

Python (3.5)

'''

    Time complexity: O(log(MAX(A, B))) 

	Space complexity: O(1)

	

    where MAX(A, B) denotes the maximum integer between â€˜Aâ€™ and â€˜Bâ€™. 

'''



# 32 bit mask in hexadecimal.

mask = 0xffffffff



def getSum(a, b):

    

    while (b & mask > 0):



        # Store carry.

        carry = (a & b)

        

        # Update first number of sum of bits.

        a = a ^ b

        

        # Shift carry by one.

        b = carry << 1

        

    return (a & mask) if b > 0 else a

Java (SE 1.8)

/*

	Time complexity: O(log(MAX(A, B))) 

	Space complexity: O(1)

	

    where MAX(A, B) denotes the maximum integer between 'A' and 'B'. 

*/



public class Solution {

	public static int getSum(int a, int b) {

		// Traverse until there is no carry left.

		while (b != 0) {



			// Initialise a variable that will store the common set bits.

			int carry = a & b;



			// Update first number with the sum of bits of both number

			// when at least one of the bits is not set.

			a = a ^ b;



			// Shift the carry by one.

			b = carry << 1;

		}



		// Return updated first number.

		return a;

	}

}

Note:

For example :

Input Format:

Output Format:

Note:

Constraints:

Top INCA INFOTECH TECHNOLOGIES Software Developer interview questions & answers

Popular interview questions of Software Developer