[LeetCode #1 ] Two Sum

One of the interesting problem to solve is Two Sum
First Solution
My first assumption from the problem was that input will be always sorted, and obviously leetcode bot rejected the solution.

	public class Solution {
		public int[] twoSum(int[] numbers, int target) {
			int[] result = new int[2];
			int l = 0;
			int r = numbers.length - 1 ;
			while (l < r) {
				if (numbers[l] + numbers[r] == target) {
					result[0] = l + 1;
					result[1] = r + 1;
					break;
				} else if (numbers[l] + numbers[r] < target) {
					l++;
				} else {
					r--;
				}
			}
			return result;
		}
	}

After fixing that issue, I forget about duplicate entries

public class Solution {
		public int[] twoSum(int[] numbers, int target) {
			
			java.util.Map<Integer, Integer> numMap = new java.util.HashMap<Integer,Integer>();
			for ( int i = 0; i < numbers.length; i++) {
				numMap.put(numbers[i], i + 1);
			}
			Arrays.sort(numbers);
			
			int[] result = new int[2];
			int l = 0;
			int r = numbers.length - 1 ;
			while (l < r) {
				if (numbers[l] + numbers[r] == target) {
					result[0] = numMap.get(numbers[l]);
					result[1] = numMap.get(numbers[r]);
					break;
				} else if (numbers[l] + numbers[r] < target) {
					l++;
				} else {
					r--;
				}
			}
			return result;
		}
	}


Here is the accepted Solution

	public class Solution {
		public int[] twoSum(int[] numbers, int target) {

			java.util.Map<Integer, java.util.List<Integer>> numLocationMap = new java.util.HashMap<Integer, java.util.List<Integer>>();
			for (int i = 0; i < numbers.length; i++) {
				java.util.List<Integer> indexList = numLocationMap
						.get(numbers[i]);
				if (indexList == null) {
					indexList = new java.util.ArrayList<Integer>();
					numLocationMap.put(numbers[i], indexList);
				}
				indexList.add(i + 1);
			}
			Arrays.sort(numbers);

			int[] result = new int[2];
			int l = 0;
			int r = numbers.length - 1;
			while (l < r) {
				if (numbers[l] + numbers[r] == target) {
					if (numLocationMap.get(numbers[l]).size() == 1) {
						result[0] = numLocationMap.get(numbers[l]).get(0);
						result[1] = numLocationMap.get(numbers[r]).get(0);
					} else {
						result[0] = numLocationMap.get(numbers[l]).get(0);
						result[1] = numLocationMap.get(numbers[r]).get(1);
					}
					break;
				} else if (numbers[l] + numbers[r] < target) {
					l++;
				} else {
					r--;
				}
			}
			Arrays.sort(result);
			return result;
		}
	}
Advertisements

My Haskell Experiment with Project Euler – 2

Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

mfib :: Int -> Integer
mfib = (map fib [0 ..] !!)
  where fib 0 = 0
        fib 1 = 1
        fib n = mfib (n-2) + mfib (n-1)


sum [ y | x <- [1..1000], let y = mfib(x), y < 4000000, y `mod` 2  == 0 ]

My Haskell Experiment with Project Euler – 1

I was planning to learn one of the function programming language and finally settled on Haskell. Just started reading Learn You a Haskell for Great Good!, and decided to solve the problems from Project Euler.

Problem

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Here is my first solution using haskell

sum [ x | x <- [0..999], x `mod` 3 == 0 || x `mod` 5 == 0]