Array of products of all other numbers

Given an array A of size N, return another resulting array B of the same size N, where B[i] is the products of all numbers in A except for A[i].
EXAMPLE:
INPUT: A = [1,2,3,4]
OUTPUT: B = [24, 12, 8, 6]

My initial thoughts:
We can first compute the products of everything, in the example, this is 1*2*3*4 = 24. Then for each element in the resulting array, we divide the total products by that element in the original array, that is: 24 = 24/1; 12 = 24/2; 8 = 24/3; 6 = 24/4. We need to be careful with the edge cases: where there are zero(s). We cannot divide by zero. Hence, we modify the algorithm. We first compute the products of non-zeros and count the number of zeros in A. Then for position i in B, if A[i]=0, we check if there are at least 2 zeros, if yes, B[i]=0. If not, B[i] should be equal to the products of non-zeros. If A[i]\ne0, we check if there is at least 1 zero, if yes, B[i]=0. Otherwise, B[i] is the product of non-zeros divided by $A[i]$.

Codes:

public static long[] getArrayOfProducts(int[] original) {
        int zeroCounts = 0;
        long products = 1;
        for(int number : original) {
            if(number == 0)
                zeroCounts++;
            else
                products *= number;
        }
        
        long[] result = new long[original.length];
        for(int i = 0; i < result.length; ++i) {
            if(original[i] == 0) {
                if(zeroCounts > 1)
                    result[i] = 0;
                else
                    result[i] = products;
            } else if(zeroCounts > 0) {
            	result[i] = 0;
            } else {
                result[i] = products / original[i];
            }
        }
        
        return result;
    }

Better Solution:
According to the post here:

public static long[] getArrayOfProducts2(int[] original) {
    	long[] results = new long[original.length];
    	results[0] = 1;
    	for(int i = 1; i < original.length; ++i) {
    		results[i] = results[i-1]*original[i-1];
    	}
    	
    	long temp = 1;
    	for(int i = results.length - 1; i >= 0; --i) {
    		results[i] *= temp;
    		temp *= original[i];
    	}
    	return results;
    }

Notice:
If the product is too large so that we hit integer/long overflow, we need to handle that, probably by introducing additional variables to store temporary products.

Find the kth number with prime factors 3, 5 and 7

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

My initial thoughts:
The k-th number can not be larger than 7^{k}. Therefore we can enumerate all the satisfying numbers by iterating the exponent of 3, 5 and 7 from 0 to k. We then sort those numbers and retrieve the kth. Altogether it’s a O(k^{3}) algorithm.

My initial codes:

	public static int findKthNumber(int k) {
		int top = k;
		List<Integer> data = new ArrayList<Integer>();
		for (int i = 0; i <= top; ++i) {
			for (int j = 0; j <= top; ++j) {
				for (int l = 0; l <= (top + 2 - i - j); ++l) {
					if (l >= 0) {
						int number = (int) (Math.pow(3, i) * Math.pow(5, j) * Math
								.pow(7, l));
						data.add(number);
					}
				}
			}
		}
		Collections.sort(data);
		return data.get(k - 1);
	}

Solution:
Here is the algorithm:

  1. Initialize array magic and queues Q3, Q5 and Q7
  2. Insert 1 into magic.
  3. Insert 1*3, 1*5 and 1*7 into Q3, Q5 and Q7 respectively.
  4. Let x be the minimum element in Q3, Q5 and Q7. Append x to magic.
  5. If x was found in:
    • Q3 -> append x*3, x*5 and x*7 to Q3, Q5 and Q7. Remove x from Q3.
    • Q5 -> append x*5 and x*7 to Q5 and Q7. Remove x from Q5.
    • Q7 -> only append x*7 to Q7. Remove x from Q7.
    • Note: we do not need to append x*3 and x*5 to all lists because they will already be found in another list.

  6. Repeat steps 4 – 6 until we’ve found k elements.
	public static int getKthMagicNumber(int k) {
		if (k <= 0)
			return 0;
		int val = 1;
		Queue<Integer> Q3 = new LinkedList<Integer>();
		Queue<Integer> Q5 = new LinkedList<Integer>();
		Queue<Integer> Q7 = new LinkedList<Integer>();
		Q3.add(3);
		Q5.add(5);
		Q7.add(7);
		for (--k; k > 0; --k) { // We’ve done one iteration already.
			val = Math.min(Q3.peek().intValue(),
					Math.min(Q5.peek().intValue(), Q7.peek().intValue()));
			if (val == Q7.peek()) {
				Q7.remove();
			} else {
				if (val == Q5.peek()) {
					Q5.remove();
				} else { // must be from Q3
					Q3.remove();
					Q3.add(val * 3);
				}
				Q5.add(val * 5);
			}
			Q7.add(val * 7);
		}
		return val;
	}

Find a line which passes the most number of points

Given a two dimensional graph with points on it, find a line which passes the most number of points.

My initial thoughts:
A pair of points forms a line. We can iterate through all pairs and count for how many points are on each line. That is in total a O(n^{3}) algorithm. Naive algorithm.

My initial codes:

	public class Line {
		private double slope;
		private double intercept;

		private final double THRESHOLD = Math.pow(10, -8);

		public Line(double slope, double intercept) {
			super();
			this.slope = slope;
			this.intercept = intercept;
		}

		public Line(Pair<Double> p1, Pair<Double> p2) {
			this.slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
			this.intercept = (p2.getX() * p1.getY() - p1.getX() * p2.getY())
					/ (p2.getX() - p1.getX());
		}

		public boolean contains(Pair<Double> p) {
			double x = p.getX();
			double y = p.getY();
			return Math.abs(y - (slope * x + intercept)) < THRESHOLD;
		}
	}

	public static Line findLine(Set<Pair<Double>> points) {
		int maxNumber = -Integer.MAX_VALUE;
		int number = 0;
		Line result = null;
		for (Pair<Double> p1 : points) {
			for (Pair<Double> p2 : points) {
				if (!p1.equals(p2)) {
					number = 0;
					Line line = new Line(p1, p2);
					for (Pair<Double> p : points) {
						if (line.contains(p))
							number++;
					}
					if (number > maxNumber) {
						maxNumber = number;
						result = line;
					}

				}
			}
		}
		return result;
	}

Solution:
We have a bunch of line segments, represented as a slope and y-intercept, and we want to find the most common slope and y-intercept. How can we find the most common one? This is really no different than the old “find the most common number in a list of numbers” problem. We just iterate through the lines segments and use a hash table to count the number of times we’ve seen each line.

	public static Line findBestLine(GraphPoint[] points) {
		Line bestLine = null;
		HashMap<Line, Integer> line_count = new HashMap<Line, Integer>();
		for (int i = 0; i < points.length; i++) {
			for (int j = i + 1; j < points.length; j++) {
				Line line = new Line(points[i], points[j]);
				if (!line_count.containsKey(line)) {
					line_count.put(line, 0);
				}
				line_count.put(line, line_count.get(line) + 1);
				if (bestLine == null
						|| line_count.get(line) > line_count.get(bestLine)) {
					bestLine = line;
				}
			}
		}
		return bestLine;
	}

	public class Line {
		private static double epsilon = .0001;
		public double slope;
		public double intercept;
		private boolean infinite_slope = false;

		public Line(GraphPoint p, GraphPoint q) {
			if (Math.abs(p.x - q.x) > epsilon) { // if x’s are different
				slope = (p.y - q.y) / (p.x - q.x); // compute slope
				intercept = p.y - slope * p.x; // y intercept from y=mx+b
			} else {
				infinite_slope = true;
				intercept = p.x; // x-intercept, since slope is infinite
			}
		}

		public boolean isEqual(double a, double b) {
			return (Math.abs(a - b) < epsilon);
		}

		@Override
		public int hashCode() {
			int sl = (int) (slope * 1000);
			int in = (int) (intercept * 1000);
			return sl | in;
		}

		@Override
		public boolean equals(Object o) {
			Line l = (Line) o;
			if (isEqual(l.slope, slope) && isEqual(l.intercept, intercept)
					&& (infinite_slope == l.infinite_slope)) {
				return true;
			}
			return false;
		}
	}
  1. Be careful about the calculation of the slope of a line. The line might be completely vertical. We can keep track of this in a separate flag (infinite_slope). We need to check this condition in the equals method.
  2. Remember that when we perform division to calculate the slope, division is not exact. Therefore, rather than checking to see if two slopes are exactly equal, we need to check if they’re different by greater than epsilon.

Find a line to cut two squares in half

Given two squares on a two dimensional plane, find a line that would cut these two squares in half.

My initial thoughts:
The straight line that connects the two centers of the two squares will cut both of them into half.

My initial codes:

	public class Square {
		private double topLeftX;
		private double topLeftY;
		private double edge;

		public Square(double topLeftX, double topLeftY, double edge) {
			super();
			this.topLeftX = topLeftX;
			this.topLeftY = topLeftY;
			this.edge = edge;
		}

		Pair<Double> getCenter() {
			return new Pair<Double>(topLeftX + edge / 2, topLeftY - edge / 2);
		}
	}

	public class Line {
		private double slope;
		private double intercept;

		public Line(double slope, double intercept) {
			super();
			this.slope = slope;
			this.intercept = intercept;
		}
	}

	public static Line getLine(Square a, Square b) {
		Pair<Double> centerA = a.getCenter();
		Pair<Double> centerB = b.getCenter();

		if (centerA.equals(centerB)) {
			return new Line(centerA.getY() / centerA.getX(), 0);
		} else {
			double slope = (centerB.getY() - centerA.getY())
					/ (centerB.getX() - centerA.getX());
			double intercept = (centerB.getX() * centerA.getY() - centerA
					.getX() * centerB.getY())
					/ (centerB.getX() - centerA.getX());
			return new Line(slope, intercept);
		}
	}

Solution:

	public class Square {
		public double left;
		public double top;
		public double bottom;
		public double right;

		public Square(double left, double top, double size) {
			this.left = left;
			this.top = top;
			this.bottom = top + size;
			this.right = left + size;
		}

		public Point middle() {
			return new Point((this.left + this.right) / 2,

			(this.top + this.bottom) / 2);
		}

		public Line cut(Square other) {
			Point middle_s = this.middle();
			Point middle_t = other.middle();
			if (middle_s == middle_t) {
				return new Line(new Point(left, top), new Point(right, bottom));
			} else {
				return new Line(middle_s, middle_t);
			}
		}
	}

Implement *, -, and / operators using only +

Write a method to implement *, – , / operations You should use only the + operator.

My initial thoughts:
a * b can be implemented as adding a for b times.
a – b can be implemented as addition of a and -b.
a / b can be implemented as finding how many times you need to add b, until getting a.

My initial codes:

	public static int multiply(int a, int b) {
		int multiplier = (a < b ? a : b);
		int multiplicant = (multiplier == a ? b : a);
		int result = 0;
		for (int i = 0; i < multiplier; i = i + 1) {
			result = result + multiplicant;
		}
		return result;
	}

	public static int substract(int a, int b) {
		return a + (~b + 1);
	}

	public static int divide(int a, int b) {
		if (a == b)
			return 1;
		int result = 1;
		int mul = b;
		while (mul < a) {
			mul = mul + b;
			result = result + 1;
		}
		return result;
	}

Comments after running:
Two many errors.

  1. Multiplication and division can’t handle negative numbers!
  2. Division can only handle who quotient. For example, 8/3 will yield 3, which is wrong.
  3. Error condition of division: can’t divide by 0.

Revision (Solution):

	public static int negate(int number) {
		return ~number + 1;
	}

	public static int abs(int number) {
		return number < 0 ? negate(number) : number;
	}

	public static int multiply(int a, int b) {
		int multiplier = Math.min(abs(a), abs(b));
		int multiplicant = (multiplier == abs(a) ? abs(b) : abs(a));
		int result = 0;
		for (int i = 0; i < multiplier; i = i + 1) {
			result = result + multiplicant;
		}
		if (abs(a) == a) { // a >= 0
			if (abs(b) == b) // b >= 0
				return result;
			else
				// b < 0;
				return negate(result);
		} else { // a < 0
			if (abs(b) == b) // b >= 0
				return negate(result);
			else
				// b < 0;
				return result;
		}
	}

	public static int substract(int a, int b) {
		return a + negate(b);
	}

	public static int divide(int a, int b) {
		if (b == 0) {
			throw new java.lang.ArithmeticException("Divide by 0.");
		}

		int divident = abs(a);
		int divisor = abs(b);
		int quotient = 0;

		while (divident >= divisor) {
			divident = substract(divident, divisor);
			quotient = quotient + 1;
		}

		if (abs(a) == a) { // a >= 0
			if (abs(b) == b) // b >= 0
				return quotient;
			else
				// b < 0;
				return negate(quotient);
		} else { // a < 0
			if (abs(b) == b) // b >= 0
				return negate(quotient);
			else
				// b < 0;
				return quotient;
		}
	}

Determine whether two lines would intersect on a Cartesian plane

Given two lines on a Cartesian plane, determine whether the two lines would intersect.

My initial thoughts:
On a Cartesian plane, if two lines do not intersect, they must be parallel with each other. Hence, their slopes must be the same. If their slopes are different, they would intersect. A line is represented as ax+by+c=0 on a Cartesian plane and the slope is given by -\frac{a}{b}. Therefore if -\frac{a_{0}}{b_{0}} \neq -\frac{a_{1}}{b_{1}} for two lines, they will intersect.

Solution:

	public class Line {
		static final double epsilon = 0.000001;
		public double slope;
		public double yintercept;

		public Line(double s, double y) {
			slope = s;
			yintercept = y;
		}

		public boolean intersect(Line line2) {
			return Math.abs(slope - line2.slope) > epsilon
					|| Math.abs(yintercept - line2.yintercept) < epsilon;
		}
	}

Comments:

  1. Two lines can be the same. In that case, we assume they intersects (overlap).
  2. We need to consider the floating system in a computer. Never use == to compare two floating numbers.

Probability of collision among ants walking on the sides of a triangle

There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle?
Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon.

My initial thoughts:
For each single ant, it can move towards two directions. Denote them as 0 or 1. If two ants are moving towards two different directions (clockwise and counter-clockwise), they will eventually meet. Therefore the only case for not having a collision is 0, 0, 0 for the three ants. There are 2^3=8 possible combination of directions. Hence 7/8 probability to have a collision.
For general case, it’s (2^n-1)/2^n.

Solution:
I forgot the case 1, 1, 1, which can also avoid collision. Therefore, for three ants, it’s (8-6)/8=3/4 and in general, it’s (2^n-2)/2^n.

Previous Older Entries