How to swap two variables without using extra temporary variable?

This is one of the popular interview questions. If you are given two variables and you have to swap the value of those two two variables (or array locations) without using extra memory space, how would you do that?

There are two ways of doing it:

  • Using Numeric Operation (+ / -)
  • Using Bitwise XOR Operation (^).

The following java program shows how this is done in Java.

package com.icodejava.blog;

import java.util.Arrays;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Mar 6, 2014
 * Last Modified On - Mar 6, 2014
 */
public class InPlaceVariableSwap {

	public static void main(String args[]) {
		int[] data = { 5, 6 };
		swapUsingNumericOperators(data);
		swapUsingBitwiseOperator(data);
	}

	/**
	 * @param data
	 *            - sample size 2 integer array. This method will swap data[0]
	 *            and data[1] without using extra variable using numeric
	 *            operation.
	 * 
	 *            Formula: a = b - a; b = b - a; a = a + b
	 */
	private static void swapUsingNumericOperators(int[] data) {
		if (data == null || data.length > 2) {
			return;
		}
		System.out.println("\nIN PLACE SWAP USING NUMERIC OPERATOR");
		System.out.println("Input:" + Arrays.toString(data));

		data[0] = data[1] - data[0];
		data[1] = data[1] - data[0];
		data[0] = data[0] + data[1];

		System.out.println("Swapped:" + Arrays.toString(data));

	}

	/**
	 * @param data
	 *            - sample size 2 integer array. This method will swap data[0]
	 *            and data[1] without using extra variable using bitwise XOR
	 *            operation.
	 * 
	 *            Formula: a = a ^ b; b = a ^ b; a = a ^ b
	 */
	private static void swapUsingBitwiseOperator(int[] data) {
		if (data == null || data.length > 2) {
			return;
		}
		System.out.println("\nIN PLACE SWAP USING BITWISE XOR OPERATOR");
		System.out.println("Input:" + Arrays.toString(data));

		data[0] = data[0] ^ data[1];
		data[1] = data[0] ^ data[1];
		data[0] = data[0] ^ data[1];
		System.out.println("Swapped:" + Arrays.toString(data));

	}
}

Here is the output of running the above program.


IN PLACE SWAP USING NUMERIC OPERATOR
Input:[5, 6]
Swapped:[6, 5]

IN PLACE SWAP USING BITWISE XOR OPERATOR
Input:[6, 5]
Swapped:[5, 6]

Rotating a two dimensional integer array In-Place and using extra memory

A 3×3 Two dimensional matrix

This is one of the popular interview questions. Interviewees are asked to rotate to the right or to the left an array. Make sure you ask the right question before you begin:

  • What kind of array are you rotating (Integer/ String / Objects?)
  • Do you want the rotation to be in place? (In case there is no extra memory available)
  • Or do you have extra space to do the rotation?

I have used integer array for rotation. However, you should be able to modify it for other data types easily. The example below does rotations using two ways:

  • In-place
  • Using extra space

I tried to calculate the time taken to do the rotation, but with my high end laptop, the time taken to rotate a 4×4 array was below zero ms. It could be different on your machine depending on the speed of your computing device.

Java Implementation:

package com.icodejava.blog.datastructure;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Mar 1, 2014
 * Last Modified On - Mar 1, 2014
 */
public class Matrix2DRotate {

	static int[][] twoDimensionalArray = new int[][]
			{ { 1, 2, 3, 4 },
			{ 5, 6, 7, 8 },
			{ 9, 10, 11, 12 },
			{ 13, 14, 15, 16 }

	};

	public static void main(String[] args) {

		System.out.println("\n\nINPUT ARRAY");

		printTwoDimensionalArray(twoDimensionalArray);

		System.out.print("\n\nROTATED WITH EXTRA SPACE:");

		int[][] rotatedArray = rotate2DArray(twoDimensionalArray);

		printTwoDimensionalArray(rotatedArray);

		System.out.print("\n\nROTATED WITH IN PLACE ROTATION:");

		rotatedArray = rotateInPlace(twoDimensionalArray, 4);

		printTwoDimensionalArray(rotatedArray);
	}

	/**
	 * @param array - two dimensional array
	 * @return Array rotated to right using extra space.
	 */
	private static int[][] rotate2DArray(int[][] array) {
		long startTime = System.currentTimeMillis();
		int length = array[0].length;
		int[][] tempArray = new int[length][length];

		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				tempArray[i][j] = array[length - 1 - j][i];
			}

		}

		long endTime = System.currentTimeMillis();
		printTimeTaken(startTime, endTime);

		return tempArray;
	}

	private static void printTimeTaken(long startTime, long endTime) {

		// System.out.print("StartTime: " + startTime +" endTime: " + endTime);

		if (startTime <= 0 || endTime <= 0 || startTime > endTime) {
			return;
		}

		System.out.println("Took " + (endTime - startTime) + " ms");

	}

	/**
	 * This method rotates a two dimensional matrix in layers.
	 * Portion of this code is taken from Cracking The Coding Interview Book
	 * @param matrix - Two Dimensional Matrix
	 * @param size - size of Matrix
	 * @return In Place Rotated Matrix
	 */
	public static int[][] rotateInPlace(int[][] matrix, int size) {

		long startTime = System.currentTimeMillis();

		for (int layer = 0; layer < size / 2; ++layer) {

			int first = layer;
			int last = size - 1 - layer;

			for (int i = first; i < last; ++i) { 				int offset = i - first; 			 				//Saves the top value 				int top = matrix[first][i];  				 				// left -> top
				matrix[first][i] = matrix[last - offset][first];

				// bottom -> left
				matrix[last - offset][first] = matrix[last][last - offset];

				// right -> bottom
				matrix[last][last - offset] = matrix[i][last];

				// top -> right
				matrix[i][last] = top; // right 			}
		}

		long endTime = System.currentTimeMillis();
		printTimeTaken(startTime, endTime);

		return matrix;
	}

	/**
	 * This method prints the two dimensional array to System Console
	 */
	private static void printTwoDimensionalArray(int[][] intArray) {
		for (int i = 0; i < intArray[0].length; i++) {
			for (int j = 0; j < intArray[i].length; j++) {
				System.out.print(intArray[i][j] + "\t");
			}
			System.out.println();
		}

	}
}

Output of running above program:

INPUT ARRAY
1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

ROTATED WITH EXTRA SPACE:Took 0 ms
13	9	5	1
14	10	6	2
15	11	7	3
16	12	8	4

ROTATED WITH IN PLACE ROTATION:Took 0 ms
13	9	5	1
14	10	6	2
15	11	7	3
16	12	8	4

Finding Mean Value Of An Integer Array In Java

In Basic Algebra, mean is nothing but just an average of all the points and is calculated as a sum of all the numbers divided by the total count. Don’t be surprised if you are asked to write a java program that can calculate mean value of an array of integers.

The interviewer might be trying to test your coding style, clean coding ability and ability to think about the boundary conditions and user errors. As you can see in the program below, I have written the method to be fail proof from null value or an empty integer.

package com.icodejava.blog.datastructure;

import java.util.Arrays;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 21, 2014
 * Last Modified On - Feb 21, 2014
 * 
 * This class can be used to find the mean value in an array
 */
public class AlgebraMeanFinder {
	
	public static void main(String args []) {
		int [] numbers = {5,5,7,2,3,9,8,9,2,6,7,8,1};
		/**
		 * Finding mean number of a valid integer array
		 */
		findMeanValue(numbers);
		
		/**
		 * Testing for null array
		 */
		findMeanValue(null);
		
		/**
		 * Passing an empty array
		 */
		findMeanValue(new int[] {});
	}

	/**
	 * @param numbers - array of numbers whose mean has to be found
	 * Mean is a simple average value of all numbers.
	 * This method is capable of handling boundary conditions.
	 */
	public static double findMeanValue(int[] numbers) {

		double sum = 0;
		if (numbers == null || numbers.length < 1) {
			System.out.println("\nInvalid Input. Returning 0. Input was:" + Arrays.toString(numbers));
			return sum;
		}

		for (int index = 0; index < numbers.length; index++) {
			sum += numbers[index];
		}

		double mean = (sum / numbers.length);
		System.out.println("\nInput Array is: " + Arrays.toString(numbers));
		System.out.println("Sum:" + sum + " Count:" + numbers.length + " Mean Value is: " + mean);

		return mean;

	}

}

Here is the output of this program.


Input Array is: [5, 5, 7, 2, 3, 9, 8, 9, 2, 6, 7, 8, 1]
Sum:72.0 Count:13 Mean Value is: 5.538461538461538

Invalid Input. Returning 0. Input was:null

Invalid Input. Returning 0. Input was:[]