## Adobe Interview Question for SDE-2s

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

We can turn one operand into binary format and calculating using shift like following:

``````public class Main{

public static int findMinimumAddition(int first,int second){
if(second == 0){
return 0;
}
if(second % 2 == 1){
return findMinimumAddition(first << 1, second / 2) + first;
}else{
return findMinimumAddition(first << 1, second / 2);
}
}

public static void main(String[] args){
}
}``````

It works only works with positive numbers. If we have negative numbers included, just do a preprocessing like setting an indicator to indicate if the result will be negative. And then deal with postive numbers first and come back to the indicator.

Comment hidden because of low score. Click to expand.
0

wont the ans be 0 every time????????

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use shift left and the rest fill with addition operations..

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;
int Multiply(int a, int b);
int reccursiveSum(int BigNum, int Smallnum);

int main()
{
int a = 19, b = 25, c = 0;;
cout << "enter first number :" << a;
//cin >> a;
cout << endl << "enter Second number :" << b;
//cin >> b;
c = Multiply(a,b);
cout << endl << "Multi value is :" << c;

// cin >> c;

return 0;
}

int Multiply(int a, int b)
{
int result = 0;

if (a > b)
{
result = reccursiveSum(a, b);
}
else
{
result = reccursiveSum(b,a);
}

return result;
}

int reccursiveSum(int BigNum, int Smallnum)
{
if (Smallnum == 1)
return BigNum;
int result =0; int NewNum = 0;

NewNum = Smallnum/2;
result = reccursiveSum(BigNum, NewNum);
result += result;

if(Smallnum % 2 != 0)
{
result += BigNum;
}
return result;
}

Comment hidden because of low score. Click to expand.
0

public int Multiply_twonumber(int m, int n)
{
if (n == 1) return m;

int temp= Multiply_twonumber(m, n / 2) ;
if (n % 2 == 0)
return temp + temp;
else
{
return m+temp + temp;
}

}

Comment hidden because of low score. Click to expand.
0

what is the logic here?

Comment hidden because of low score. Click to expand.
0

guys whenever you want to divide or multiply by 2
just use shifting not anything else
Its faster than * or / !!!

Comment hidden because of low score. Click to expand.
0

*sigh* shifting is NOT faster than * or / in any modern compiler. If you find a compiler where left shift is faster than multiplication by 2, run away and fast

Comment hidden because of low score. Click to expand.
0

EDIT: DELETED NONSENSE.

Comment hidden because of low score. Click to expand.
0

public int Multiply_twonumber(int m, int n)
{
if (n == 1) return m;

int temp= Multiply_twonumber(m, n / 2) ;
if (n % 2 == 0)
return temp + temp;
else
{
return m+temp + temp;
}
}

Here there is recursive call for Multiply_twonumber
and each time we get a result from Multiply_twonumber function we just need to sum up the result to itself i.e. log(n) complexity reduces use of sum operator. as sum is already available for last division.

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int Multiply_twonumber(int m, int n)
{
if (n == 1) return m;

int temp= Multiply_twonumber(m, n / 2) ;
if (n % 2 == 0)
return temp + temp;
else
{
return m+temp + temp;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Calc
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(multiply(3, 4));

}

private static int multiply(int n, int m) {
if (m == 1) return n;

return n + multiply(n, m - 1);
}
}

Comment hidden because of low score. Click to expand.
0

This code will give exception if I pass (3,0). Have to add one more check I guess

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Multiplication {
private HashMap<String, Integer> map = new HashMap<String, Integer>();
public int getMultiplicationOfTwoNumber(int number, int times){
if(times==1){
return number;
}
if(number < times){
int temp = number;
number = times;
times = temp;
}
String key = number + "," + times;
Object value = map.get(key);
if(value!=null){
return map.get(key);
}
int leftTimes = times/2;
int rightTimes = times - leftTimes;
int leftResult = getMultiplicationOfTwoNumber(number, leftTimes);
int rightResult = getMultiplicationOfTwoNumber(number, rightTimes);
int result = leftResult + rightResult;
map.put(key, result);
return result;
}
public static void main(String[] args){
Multiplication code = new Multiplication();
System.out.println(code.getMultiplicationOfTwoNumber(200, 200));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````{

private static Scanner in;

public static void main(String[] args) {

in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();

int result;
if (a < b) {
System.out.println( b + " is added " + a + " times.");
} else {
System.out.println( a+ " is added " + b + " times.");
}

System.out.println("recursiveAdd result is " + result);

}

static int recursiveAdd(int num, int times) {

if (times > 0) {
return num + recursiveAdd(num, times - 1);
} else {
return 0;
}
}

}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess the aim of this is to achieve a complexity of logn here...

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int multiplyTwoNumbers(int a,int b){
if (b==0) {
return 0;
}
return a+multiplyTwoNumbers(a, b-1);``````

Comment hidden because of low score. Click to expand.
0

Hi, SachinK,
I like your solution. You only used one addtion operation here which tends to be the minimum.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static int mult(int m , int n) {

if(n<=1)
return m;

int res= mult(m, n / 2) ;
if (n % 2 == 0)
return res + res;
else
{
return m+res + res;
}

}``````

Comment hidden because of low score. Click to expand.
0

ultimately using n '+' operations

Comment hidden because of low score. Click to expand.
0

check for n==0 also.. bug.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Note that a * b = (2 * a) * (b / 2).
So we'll use the recursive formula multiply(a, b) = multiply(2 * a, b / 2) with base case b equal to 0. (We also have to be a bit careful when b is not a multiple of two, in that case we use a * b = a + (2 * a) * ((b - 1) / 2)).
This will use O(log(b)) operations. We can optimize a bit and make sure b is the smallest of the two numbers and then we get O(log(min(a, b))).
Here is the code in Java:

``````int multiply(int a, int b) {
if (Math.abs(a) >= Math.abs(b)) {
return multiplyHelper(a, b);
}
return multiplyHelper(b, a);
}

int multiplyHelper(int largerNumber, smallerNumber) {
if (smallerNumber == 0) {
return 0;
}
if (smallerNumber % 2 == 0) {
return multiplyHelper(largerNumber * 2, smallerNumber / 2);
}
if (smallerNumber > 0) {
retrurn largerNumber + multiplyHelper(largerNumber * 2, smallerNumber / 2);
}
retrurn -largerNumber + multiplyHelper(largerNumber * 2, smallerNumber / 2);
}``````

Comment hidden because of low score. Click to expand.
0

Nicely done!

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
int mult(int a,int b)
{
if(b==1)
{
return a;
}
if(b%2==0)
{
a=a<<1;
b=b>>1;
a=mult(a,b);
}
else
{
int tempa;
tempa=a;
a=a<<1;
b=(b-1)>>1;
a=tempa+mult(a,b);
}
}
int main()
{
printf("%d\n",mult(9,9));
}

/*if b%2 == 0
a*b=(2*a)*(b/2)
else
a*b=a+(2*a)(b-1)/2*/

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution:
Write a recursive method to get the multiplication of two numbers such that there are minimum number of addition operations.....
Solution..

package com.shashikumar.com;

public class multiplication {
public static void main(String []args)
{

multiplication t=new multiplication();
int a=10,b=88;//should give 880 when we multiply.
System.out.print(t.multiply(a,b));

}
public int multiply(int x,int y)
{
if(y==1)
return x;
else
return (sumNumbers(x,y));

}
public int sumNumbers(int m,int n)
{

if(n==1)
return m;
else

return m+sumNumbers(m,n-1);

}

}
output:
---------------------------
880

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int mult_1(int x, int y)
{
cout << "mult_1 x = " << x << " y = " << y << endl;

if (!x || !y) return 0;       // basis case 0
if (x == 1)   return y;       // basis case 1
if (y == 1)   return x;       // basis case 2

int pow = power2(x);
if (pow)
return y << pow;

pow = power2(y);
if (pow)
return x << pow;

if (x < y)
{
if ((x & 0x01) == 0)      // x is even
return mult_1(x>>1,y<<1);
return y + mult_1(x-1, y);
}

if ((y & 0x01) == 0)          // y is even
return mult_1(x<<1,y>>1);
return x + mult_1(x, y-1);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int mul(int a,int b){
if (a==1) return b;
if (a&1){
return b+((mul(a-1,b)));
}
return ((mul((a>>1),b))<<1);
}

int main(){
int a,b;
cin >> a>>b;
if (a<b)
cout <<mul(a,b)<<endl;
else
cout <<mul(b,a)<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````long multiply(int no1,int no2)
{
int size = sizeof(int)*8;
long result = 0;
for(int i=0;i<size;i++){
if((1<<i)&no2){
result = (result + (no1<<i) );
}
}
return result;
}``````

This will execute for all cases in constant no of times, either 32 times or 64 times according to the size of integer. And only work for integers as shift operators not allowed to floats or doubles

Comment hidden because of low score. Click to expand.
0
of 0 vote

class RecursiveMultiplication{

public static int recMultiply(int num1, int num2){
if(num2 == 1){
return num1;
}
if(num2 == 0){
return 0;
}
return num1 + recmultiply(num1, num2-1);
}
public static void main(String[] args){
recMultiply(15,15);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Full Code including handling of negative numbers based on ravio's approach

``````#include <iostream>

struct signedInt {
bool isPositive;
int positive;
};

// Assuming that use of <  and > operators are not allowed either
signedInt makePositive(uint x) {
signedInt s;
uint positiveNum = (x<<1)>>1;
if(x!=positiveNum) {
s.isPositive = false;
s.positive = (int)(~x + 1);
std::cout << "Is negative" << " Positive becomes " << s.positive << std::endl;
}
else {
s.isPositive = true;
s.positive = (int)x;
std::cout << "Is positive" << " Positive becomes " << s.positive << std::endl;
}
return s;
}

int multMinAdd(int a, int b) {
if(b==0) { return 0; }
if(b%2==1) {
}
}

int multiply(int a, int b) {
signedInt A = makePositive(a);
signedInt B = makePositive(b);
std::cout << "Multiplying: " << A.positive << " and " << B.positive <<  std::endl;
if(A.isPositive ^ B.isPositive == true) {
C = ~C + 1;
}
return C;
}

int main() {
int a = -10;
int b = -3;
std::cout << multiply(a,b) << std::endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static void main(String[] args){

int result=recursiveMultiply(3, 6);
System.out.println(result);

}

static int recursiveMultiply(int a,int b){
if(b==0)
return 0;

return a+recursiveMultiply(a,b-1);
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.