Adobe Interview Question SDE-2s
Country: India
Interview Type: In-Person
#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;
}
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;
}
}
guys whenever you want to divide or multiply by 2
just use shifting not anything else
Its faster than * or / !!!
*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
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.
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);
}
}
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));
}
}
{
public class MinRecursiveAdd {
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) {
result = recursiveAdd(b, a);
System.out.println( b + " is added " + a + " times.");
} else {
result = recursiveAdd(a,b);
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;
}
}
}
}
public static int multiplyTwoNumbers(int a,int b){
if (b==0) {
return 0;
}
return a+multiplyTwoNumbers(a, b-1);
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;
}
}
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);
}
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
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);
adds++;
return y + mult_1(x-1, y);
}
if ((y & 0x01) == 0) // y is even
return mult_1(x<<1,y>>1);
adds++;
return x + mult_1(x, y-1);
}
#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;
}
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
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) {
return multMinAdd(a<<1,b/2) + a;
}
return multMinAdd(a<<1,b/2);
}
int multiply(int a, int b) {
signedInt A = makePositive(a);
signedInt B = makePositive(b);
std::cout << "Multiplying: " << A.positive << " and " << B.positive << std::endl;
int C = multMinAdd(A.positive,B.positive);
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;
}
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){ System.out.println(findMinimumAddition(9, 9)); System.out.println(findMinimumAddition(6, 3)); } }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.
- ravio September 07, 2014