Programming Praxis

An Odd Way To Square

February 26, 2013 9:00 AM

I’m not sure where this comes from; it could be an interview question, or some kind of programming puzzle:

Write a function that takes a positive integer n and returns n-squared. You may use addition and subtraction but not multiplication or exponentiation.

Your task is to write the squaring function described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

26 Responses to “An Odd Way To Square”

square 0 = 0
square n = (square (n-1)) + n + (n-1)

By ts on February 26, 2013 at 9:14 AM

[…] today’s Programming Praxis exercise, our goal is to implement an algorithm to square a number using only […]

By Programming Praxis – An Odd Way To Square | Bonsai Code on February 26, 2013 at 10:50 AM
My Haskell solution (see http://bonsaicode.wordpress.com/2013/02/26/programming-praxis-an-odd-way-to-square/ for a version with comments):

By Remco Niemeijer on February 26, 2013 at 10:50 AM

Hm, something went wrong in posting. Let’s try that again:

import Data.Bits
import Data.List

square :: Integer -> Integer
square n = sum $ genericReplicate n n

square2 :: Integer -> Integer
square2 n = sum [a | (i,a) <- unfoldr (\(i,p,a) -> if p <= n then
    Just ((i,a), (i+1,p+p,a+a)) else Nothing) (0,1,n), testBit n i]

By Remco Niemeijer on February 26, 2013 at 10:51 AM

[…] Question is from here. […]

By An Odd Way To Square (Java) | Exploring Java world on February 26, 2013 at 11:16 AM
My java solution here.

By javabloggi on February 26, 2013 at 11:17 AM
Isn’t it slightly cleaner to just add n directly? The time complexity remains the same.
```
(define (sq2 n)
(let loop ((x n) (s 0))
(if (zero? x ) s
(loop (- x 1) (+ s n)))))
```
By Janne on February 26, 2013 at 1:06 PM
Nobody’s done it this way yet…
```
(defun square (n)
  (apply '+ (make-list n n)))
```
By Mitchell on February 26, 2013 at 1:26 PM
[…] Pages: 1 2 […]

By An Odd Way To Square | My Blog on February 26, 2013 at 3:32 PM
Python

http://codepad.org/HKjnImYy

def poor_square(n): l = [n for i in range(n)] return sum(l)
n = 12 print poor_square(n)

By Andrew on February 26, 2013 at 4:49 PM

use shift operator, shift and add, see: http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add

unsigned int sqr(unsigned int n) {
     unsigned int sum = 0, x = n;
     for (int i = 0; x; x >>= 1, i++)
         if (x & 1) sum += n << i;
     return sum;
 }

By pip1984 on February 26, 2013 at 6:11 PM

def square_no_add(n, ctr=0):
    if n == ctr:
        return 0
    else:
        return n + square_no_add(n, ctr + 1)

By linesncodez on February 26, 2013 at 6:25 PM

And in forth:

: sqr.add ( n — n*n )
dup 1 > if dup dup 1 do over + loop swap drop then ;

By Matthew on February 26, 2013 at 7:19 PM
An O(log(N)) algorithm exploiting the binary representation of N. Assuming that N=2^k(1) + 2^k(2) + … + 2^k(t) the algorithm will add: N*2^k(1), N*2^k(2), … ,N*2^k(t)
```
def square(n, x, p, q):
	s = square(n, x, p + p, q + q) if p + p <= n else 0
	if p <= x[0] < p + p:
		x[0] -= p
		s += q
	return s

n = 16
print square(n, [n], 1, n)
```
By cosmin on February 27, 2013 at 1:55 AM

Python 3.3

based on the formula (n+1)**2 = n**2 + 2*n + 1

from itertools import accumulate, count, islice

def square(n):
    return next(islice(accumulate(n+n+1 for n in count()), n-1, n))

By Mike on February 27, 2013 at 9:13 AM

_start:
	mov	ecx, 5	; the number to square
	xor	ebx, ebx
	mov	eax, ecx
.sum:
	add	ebx, eax
	loop	.sum

	;; ebx now contains the square
	mov	eax, 1
	int	0x80

By x0j0c on February 27, 2013 at 8:44 PM

Here’s another O(n) one based on the fact that n*n is the sum of all odd integers less than 2n:
```
(define (square n)
  (let loop ((i (+ n n -1)) (s 0))
    (if (= i -1) s (loop (- i 2) (+ s i)))))
```
By Jamie Hope on February 28, 2013 at 5:44 PM
[Java]

private int squared(int n){
int result = 0;
for(int i = 0; i < n; ++i){
result += n;
}
return result;
}

By XtremePrime on March 3, 2013 at 2:02 PM
Haskell

link

By Davor (@davor_se) on March 5, 2013 at 4:40 PM
JavaScript

function OddSquare(n) { var result = 0; for (var i = 0; i < n; i++) { result += n; } return result; }
http://jsfiddle.net/jpkmt/

By spainmc on March 13, 2013 at 5:53 PM

#Python program to
#find square of number
# without using multiplication

def num_square(num):
	count = 0
	result = 0
	
	while count < num:
		result = result + num
		count+=1
	return result
	
n = input("Enter the number whose square has to be calculated:>")  

print(num_square(int(n)))

By Radhakrishna Lambu on April 11, 2013 at 10:44 AM

Java
int square(int n){
int sum = n;
for(int i = 1; i < n; i++){
sum += n;
}
return sum;
}

By Eitan on April 26, 2013 at 8:11 PM

Binary arithmetic yielding O(1):

public static uint Multiply(uint n1, uint n2) {
	uint res = 0;
	for (; n2 > 0; n2 >>= 1, n1 <<= 1) {
		if ((n2 & 1) == 1)
			res += n1;
	}
	return res;
}

By brooknovak on June 18, 2013 at 1:29 PM

Woops the binary arithmetic isnt really o(1), its dependent on position of the MSB that equals 1 of the unsigned int (n2). Worst case would be 32 iterations.
To improve on this you could swap n1 with n2 if n1 < n2.

By brooknovak on June 18, 2013 at 1:33 PM

Easy to follow Python method:

def main():
    count = 1
    square = 0
    number = int(input("Number?"))
    while count <= number:
        square = square + number
        count = count + 1
    print("Square of",number,"is",square) 
main()

By skuba713 on July 22, 2013 at 3:09 PM

[…] Find a square of a number. but you can only use addition or subtraction but no multiplication or division Odd way to Square […]

By JavaScript, CSS: interview questions | EugeneBichel's Blog on October 1, 2015 at 1:00 PM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

An Odd Way To Square

Share this:

Related

26 Responses to “An Odd Way To Square”

Leave a Reply