CareerCup

Sum of Odd numbers
1*1 = 1 // 1
2*2 = 4 // 1+3
3*3 = 9 // 1+3+5
4*4 =16// 1+3+5+7

and so on

int squareNum(int num){
	int answer = num;
	for(int i = 1; i<num; i++){
		answer = answer + num;
	}
	return answer;
	
}

int Sq(int n){
		int i=n, sq=0, count=1;
		if((i&1) == 1)
			sq += n;
		i >>= 1;
		while(i>0){
			if((i&1) == 1)
				sq += n<<count;
			i >>= 1;
			count++;
		}
		return sq;
	}

def mult_bitop(n):
  s=0
  c=n
  while (n>0):
    #print n,c,s
    if (n&1):
      s+=c
    c<<=1
    n>>=1
  return s

int Sq(int n)
{
if (n<2) return n;

int i = n>>1;
if (n&1) return ((Sq(i)<<2) + (i<<2) + 1);
else return (Sq(i)<<2);
}

Bad question for an interview, but a very interesting puzzle.

Anyway, here is a recursive method (in python), which is O(log n) arithmetic operations (which does not use * or exponentiation).

def square(n):
   if n == 1:
       return 1
   k = n/2
   x = square(k)
   if n % 2 == 0:
        # n = 2k, x = k^2
        return x << 2
   # n = 2k+1, x = k^2
   # n^2 = 4k^2 + 4k + 1
   return x << 2 + k << 2 + 1

And yeah, the interviewer needs a stick (get it? carrot, stick...).

square(n) = n times n(n+n+n+.......+nx where x = n)

public int square(int a) {
	return multiply(a, a);
}

public int multiply(int a, int b) {
	if (b == 1) {
		return a;
	}

	int temp = (b % 2) == 0 ? 0 : a;
	int ret = multiply(a, b / 2);
	return temp + ret + ret;
}

public int square(int a) {
	return multiply(a, a);
}

public int multiply(int a, int b) {
	if (b == 1) {
		return a;
	}

	int res= multiply(a, b / 2) << 1;
	return b % 2 == 0 ? res : res + a;
}

try with logarithm ?
ln(a²) = 2*ln(a) = ln(a) + ln(a)

public long square(long n) {
	return Math.round(Math.exp(Math.log(n) + Math.log(n)));
}

num/(1/num)

#include <iostream>
using namespace std;
int square(int n)
{
int sq_n=0,odd=1;
for(int i=1;i<=n;i++)
{
sq_n+=odd;
odd=odd+2;
}
return sq_n;
}
int main() {

cout<<(square(16))<<endl;
return 0;
}

Straight forward version

public static int square(int value) {
		return square(value, value);
	}
	
	public static int square(int value, int multiplier) {

		if (multiplier == 1) {
			return value;
		}
		
		if (multiplier % 2 == 0) 
			return square (value << 1, multiplier / 2);
		
		return square(value << 1, multiplier / 2) + value;
	}

They're looking for O(log(value)) performance. Here's recursive and iterative versions.

public static int square1(int value) {
		int multiplier = value;
		int original = value;
		boolean odd = value % 2 != 0;
		
		while (multiplier > 1) {
			value <<= 1;
			multiplier /= 2;
		}

		return odd ? value + original : value;
	}

	public static int square(int value) {
		return square(value, value);
	}
	
	public static int square(int value, int multiplier) {

		if (multiplier == 1) {
			return value;
		}
		
		if (multiplier % 2 == 0) 
			return square (value << 1, multiplier / 2);
		
		return square(value << 1, multiplier / 2) + value;
	}

It can be solved completely using bitwise operators in O(log(value))

unsigned long long square(unsigned n) {
  unsigned x;
  unsigned char bit;
  unsigned long long result=0;
  for(x=n, bit=0 ; x ; x>>=1, bit++) {
    if(x&0x1) result += n<<bit; 
  }
  return result;
}

int main() {
  unsigned number=9;
  printf("Sq(%d)=%u\n",number,square(number));
  return 0;
}

Its a very simple one. My Answer is

import java.util.*;
class Square
{
public static void main(String []s)
{
Scanner scan=new Scanner(System.in);
System.out.println("Enter the value to find its square");
int num=scan.nextInt();
// Print the square of the number
int square=0;
for(int i=0;i<num;i++)
{
square+=num;
}
System.out.println("Square is"+square);
}
}

int n = 4;
int result = 0;
for (int i=0; i<n; i++)
{
result = result + n;
}

System.out.println(result);

If this is double/float

double sq(double input){
if(input!=0){
return exp(2.*log(fabs(input)));
}else{
return 0}
}

If this is double/float

double sq(double input){
if(input!=0){
return exp(2.*log(fabs(input)));
}else{
return 0}
}

public static void Sqaure(int number){
     
     int square =0;
     
     for ( int i =0 ; i< number; i++) {
    square = square + number ; 
     
   }
     System.out.println(square);
 }

#include<iostream>
using namespace std;

int square_num(int num)
{
    int square_val=0;
    if (num == 1 || num == 0) {
        return num;
    }
    // Check for negative number and convert it to positive
    if (num < 0) {
        num = num - num - num;
    }
    // Lets square the number
    for (int i=0; i < num; i++) {
        square_val = square_val + num;
    }
    return square_val;
}

int main()
{
    int num, square_val=0;
    cout << "Enter a number to be squared: ";
    cin >> num;
    square_val=square_num(num);
    cout << "Square of the the number "<< num << " is= " << square_val << endl;
    return 0;
}

#include <iostream>
using namespace std;

int main() {
	int a;
	int b;

	// number = a ^ b 
	cin >> a;
	cin >> b;

	double sum = 0;
	for (int i = 1; i <= b; i++)
		sum += log(a);

	cout << exp(sum);
	return 0;
}

#include <iostream>
using namespace std;

int main() {
	int a;
	int b;

	// number = a ^ b 
	cin >> a;
	cin >> b;

	double sum = 0;
	for (int i = 1; i <= b; i++)
		sum += log(a);

	cout << exp(sum);
	return 0;
}

@import Foundation;

int squareNum(int num){
int answer = num = num > 0 ? num : -num;
for(int i = 1; i < num; i++)
answer = answer + num;
return answer;
}

int main() {
@autoreleasepool {
NSLog(@"%d", squareNum(-3));
} return 0;
}

def square(a):
	if a<0:	
	    b=-a
	else:
	    b=a
	c=0
	while(b>0):
		c += a; b-=1
		
	if a<0:
		c = -c
	return c
	
	
print(square(2))
print(square(24))
print(square(-24))
print(square(0))

-(NSInteger)square:(NSInteger)number {
    NSInteger result = 0;
    for (NSInteger i=0; i<ABS(number); i++) {
        result+=ABS(number);
    }
    return result;
}

-(NSInteger)square:(NSInteger)number {
    NSInteger result = 0;
    NSInteger firstNumber = ABS(number);
    NSInteger secondNumber = ABS(number);
    
    while (firstNumber) {
        if (firstNumber&1) {
            result+=secondNumber;
        }
        firstNumber>>=1;
        secondNumber<<=1;
    }
    return result;
}

Use Python and cost is o(log2(n))

def square(x):
		if x<0:
			return square(-x)
		else:
			return mul(x,x)
		
	def mul(x, y):
		if y==1:
			return x
		elif y==0:
			return 0
		else:
Return mul(x,y>>1)<<1+mul(x,y-(y>>1)<<1)

int square(int n)
{
int sq = 0;
int in = n;
while(n)
{
sq += in << (int)(log2(n & (-n)));
n = n ^ (n & (-n));
}
printf("Square of %d = %d \n", in,sq);
return sq;
}

this should be a one liner

int
main ()
{
int i =5;

print (" twice of i is %d", (i<<1));
return (i<<1);
}

If you remember your Kindergarten math, m * m is nothing but m summed up m times