Convert a Decimal Number into Binary Representation

This is very easy to implement.

Principle to Convert

A decimal number is converted into binary number by repeatedly dividing the number by 2 and prepending the remainder. So the first remainder is placed at Unit Place, Second remainder at Tens Place, Third remainder at Hundreds Place and so on.

	/**
	* Converts given Decimal number into Binary representation
	* @param m decimal number to converto to binary
	* @return Binary representation of input decimal number
	*/
	public String convert(int m) {
	String binary = "";
	while(m > 0) {
	binary = (m % 2) + binary; // append new remainder at the beginning
	m /= 2;
	}
	return binary;
	} // convert

view raw ConvertToBinary.java hosted with ❤ by GitHub

---

---

---

MIT Open Courseware - Introduction to Algorithms (2008)

This is just a bookmarks to MIT Open Courseware Course 6.006 (Introduction to Algorithms (2008)). Following are the links to the course pages:

• MIT Course Page
• Page to Links to Course Videos Only
• Page to Links to Recitation Videos
• Watch all videos in a pop-up in the same page

---

---

---

Binary Search, Limit Search, Bound Search and Range Query

Binary Search

Binary Search is the most efficient algorithm for searching in sorted array.

Implementation of Binary Search is pretty straightforward.

	//----------------------------------------------------------------------------------
	/**
	* Searches searchItem in the array using iterative binary search
	* @param a
	* @param searchItem
	* @return
	*/
	public static int search(int[] a, int searchItem) {
	int lo = 0;
	int hi = a.length - 1;
	while (lo <= hi) {
	int mid = (lo + hi) / 2;
	if(a[mid] == searchItem) return mid;
	else if(a[mid] > searchItem) hi = mid - 1;
	else lo = mid + 1;
	}
	return -1;
	} // search
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Lower Limit and Upper Limit

Binary search in a sorted list is straight forward. Binary search principle can also be applied to search for the lower limit and upper limit.

Lower Limit means the minimum index item, which is greater than or equal to the given search item.

Similarly, Upper Limit means the maximum index item, which less than or equal to the given search item.

Lower Limit

	//------------------------------------------------------------------------------------
	/**
	* Lower limit is the number greater than or equal to searchItem with minimum index in the array
	* @param a
	* @param searchItem
	* @return
	*/
	public static int searchLowerLimit(int[] a, int searchItem) {
	int lo = 0;
	int hi = a.length-1;
	if (hi == -1 || a[hi] < searchItem) { // no greater item, all items in the array are smaller than searchItem
	return -1;
	}
	while (lo <= hi) {
	int mid = (lo + hi)/2;
	if(a[mid] >= searchItem) {
	hi = mid - 1;
	} else {
	lo = mid + 1;
	}
	}
	return hi + 1;
	} // searchLowerLimit
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Upper Limit

	//------------------------------------------------------------------------------------
	/**
	* Upper limit is the number smaller than or equal to searchItem with maximum index in the array
	* @param a
	* @param searchItem
	* @return
	*/
	public static int searchUpperLimit(int[] a, int searchItem) {
	int lo = 0;
	int hi = a.length - 1;
	if (hi == -1 || a[0] > searchItem) { // no smaller item, all items in the array are greater than searchItem
	return -1;
	}
	while (lo <= hi) {
	int mid = (lo + hi)/2;
	if(a[mid] > searchItem) hi = mid - 1;
	else lo = mid + 1;
	}
	return lo - 1;
	} // searchUpperLimit
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Lower Bound and Upper Bound

Lower Bound means the minimum index item, which is greater than given search item.

Similarly, Upper Limit means the maximum index item, which less than given search item.

Lower Bound

	//------------------------------------------------------------------------------------
	/**
	* Lower Bound is the number strictly greater than searchItem with minimum index in the array
	*
	* Only two changes required from above method
	* 1. if (hi == -1 || a[hi] < searchItem) ==> if (hi == -1 || a[hi] <= searchItem)
	* 2. if(a[mid] >= searchItem) ==> if(a[mid] > searchItem) {
	* @param a
	* @param searchItem
	* @return
	*/
	public static int searchLowerBound(int[] a, int searchItem) {
	int lo = 0;
	int hi = a.length-1;
	if (hi == -1 || a[hi] <= searchItem) { // no greater item, all items in the array are smaller than searchItem
	return -1;
	}
	while (lo <= hi) {
	int mid = (lo + hi)/2;
	if(a[mid] > searchItem) {
	hi = mid - 1;
	} else {
	lo = mid + 1;
	}
	}
	return hi + 1;
	} // searchLowerLimit
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Upper Bound

	//------------------------------------------------------------------------------------
	/**
	* Upper limit is the number strictly smaller than searchItem with maximum index in the array
	*
	* Only two changes required in above method
	* 1. if (hi == -1 || a[0] > searchItem) ==> if (hi == -1 || a[0] >= searchItem)
	* 2. if(a[mid] > searchItem) ==> if(a[mid] >= searchItem)
	* @param a
	* @param searchItem
	* @return
	*/
	public static int searchUpperBound(int[] a, int searchItem) {
	int lo = 0;
	int hi = a.length - 1;
	if (hi == -1 || a[0] >= searchItem) { // no smaller item, all items in the array are greater than searchItem
	return -1;
	}
	while (lo <= hi) {
	int mid = (lo + hi)/2;
	if(a[mid] >= searchItem) hi = mid - 1;
	else lo = mid + 1;
	}
	return lo - 1;
	} // searchUpperBound
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Test

	public static void main(String[] args) {
	//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
	int[] list = new int[]{1, 2, 5, 12, 17, 23, 24, 26, 45, 55, 77, 89, 91, 93, 95, 100, 113};
	verify(5, search(list, 23));
	verify(5, search(list, 23));
	verify(8, search(list, 45));
	verify(10, search(list, 77));
	verify(-1, search(list, 78));
	verify(14, search(list, 95));
	verify(16, search(list, 113));
	verify(0, search(list, 1));
	verify(-1, search(list, 3));
	verify(0, search(new int[]{3}, 3));
	verify(-1, search(new int[]{}, 3));
	verify(-1, search(new int[]{3}, 4));
	//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
	list = new int[]{1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 5, 8, 9, 10, 11, 11, 11, 33, 33, 44, 75, 87, 87, 87, 90, 90, 90, 90, 100};
	// Lower Limit Search
	verify(18, searchLowerLimit(list, 23));
	verify(0, searchLowerLimit(list, 1));
	verify(25, searchLowerLimit(list, 90));
	verify(29, searchLowerLimit(list, 100));
	verify(-1, searchLowerLimit(list, 101));
	verify(-1, searchLowerLimit(new int[]{}, 101));
	verify(0, searchLowerLimit(new int[]{10}, 9));
	verify(-1, searchLowerLimit(new int[]{10}, 11));
	// Lower Bound
	verify(29, searchLowerBound(list, 90));
	verify(12, searchLowerBound(list, 5));
	verify(-1, searchLowerBound(list, 100));
	verify(18, searchLowerBound(list, 11));
	verify(18, searchLowerBound(list, 25));
	verify(4, searchLowerBound(list, 1));
	// Upper Limit Search
	verify(17, searchUpperLimit(list, 23));
	verify(3, searchUpperLimit(list, 1));
	verify(28, searchUpperLimit(list, 90));
	verify(29, searchUpperLimit(list, 100));
	verify(29, searchUpperLimit(list, 101));
	verify(-1, searchUpperLimit(new int[]{}, 101));
	verify(-1, searchUpperLimit(new int[]{10}, 9));
	verify(0, searchUpperLimit(new int[]{10}, 11));
	// Upper Bound Search
	verify(17, searchUpperBound(list, 23));
	verify(-1, searchUpperBound(list, 1));
	verify(24, searchUpperBound(list, 90));
	verify(28, searchUpperBound(list, 100));
	verify(29, searchUpperBound(list, 101));
	verify(-1, searchUpperBound(new int[]{}, 101));
	verify(-1, searchUpperBound(new int[]{10}, 9));
	verify(0, searchUpperBound(new int[]{10}, 11));
	} // main
	//----------------------------------------------------------------------------------
	/**
	* Verify expected and actual values
	* @param expected
	* @param actual
	*/
	private static void verify(int expected, int actual) {
	if (expected == actual) {
	//System.out.println("Success");
	} else {
	System.out.println("*** Failed");
	}
	} // verify
	//----------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

Application of Limit Search

There can be several applications of these. One of the application could be using the lower and upper limit to find the number of items in the given range.

	//------------------------------------------------------------------------------------
	/**
	* Finds all the numbers in a sorted array in the given range
	* @param list input sorted array
	* @param @lowerLimit lower limit of the range
	* @param @upperLimit upper limit of the range
	* @return list of numbers in the range
	*/
	public static List findElementsInRange(int[] list, int lowerLimit, int upperLimit) {
	List result = new ArrayList();
	int start = searchLowerLimit(list, lowerLimit);
	if (start == -1) {
	return result;
	}
	int end = searchUpperLimit(list, upperLimit);
	if(end == -1) {
	return result;
	}
	while(start <= end) {
	result.add(list[start++]);
	}
	return result;
	} // findElementesInRange
	//------------------------------------------------------------------------------------

view raw BinarySearch.java hosted with ❤ by GitHub

---

---

---

Template File for Sublime Text - Customization

It is always easy to have file templates when we need have them created repeatedly. Today I am going to show file templates in Sublime Text 2.

SublimeFileTemplates - Installation and Usage

To create a file using a template, I have used Sublime File Templates Package for the Sublime Text. Installation and Usage is explained in the GitHub page of the package.

When you install the package, by default, some templates will be installed for some of the file types. If you are not satisfied with the default template, you have an option to customize it.

Here I am going to explain the template customization for the file type *.java

Template Customization for Java

You can locate the templates files for file types at

• ~/Library/Application Support/Sublime Text 2/Packages/FileTemplates/Templates (Unix)
• C:/Users//AppData/Roaming/Sublime Text 2/Packages/FileTemplates/Templates (windows)

There you can find template settings file - java.file-template and actual template file - java.java.

java.file-template

This file looks like

	<template>
	<!-- Or you set a path to a seperate Template File here -->
	<file>java.java</file>
	<!-- The filename for the new File, you can use the arguments to make it dynamic -->
	<filename>$name.java</filename>
	<!-- Optional: Add as much arguments as you need, they will be asked in the order specified -->
	<arguments>
	<name>Name (without extension):</name>
	</arguments>
	</template>

view raw java.file-template hosted with ❤ by GitHub

Here you can add as much arguments as you need, they will be asked in the order specified and can be used in the template file.

java.java

This is actual template file. When you create the file using this plugin, this file will look like this template file. In this template you can use the arguments defined in java.file-template. Following is an example template file

	/* File: $name.java
	* Created: $date2
	* Author: $author
	*
	* Copyright (c) $year https://manandharsabbirk.appspot.com
	*/
	import java.io.*;
	import java.util.*;
	public class $name{
	//---------------------------------------------------------------------------------
	/**
	* main method
	*/
	public static void main (String [] args) throws IOException{
	Scanner input = new Scanner(System.in);
	} // main
	//---------------------------------------------------------------------------------
	} // $name

view raw java.java hosted with ❤ by GitHub

The parameter $name in the template file is read from the template settings file java.file-template.

You might have also observed other parameters as $date2, $author and $year. Where are they coming from? Well these are defined in the file ~/Library/Application Support/Sublime Text 2/Packages/FileTemplates/FileTemplates.sublime-settings. You can again add as much attributes as you need and use in your template file.

FileTemplates.sublime-settings

	{
	"excluded_dir_patterns": [
	"tmp", "|.git", "|.svn"
	],
	"attrs": {
	"author": "Sabbir Manandhar",
	"company": "Hogwart",
	"email": "manandhar.sabbir@gmail.com",
	"github": "github.com/leosabbir"
	},
	"creation_time": {
	"day": "%d",
	"month": "%m",
	"year": "%Y",
	"short_weekdayname": "%a",
	"weekdayname": "%A",
	"short_monthname": "%b",
	"date": "%d/%m/%Y",
	"date2" : "%Y-%m-%d",
	"time": "%H:%M:%S"
	}
	}

view raw FileTemplates.sublime-settings hosted with ❤ by GitHub

---

---

---

Computation of Nth Fibonacci Number

Fibonacci Sequence

Fibonacci Sequence is the series of numbers which starts with two $1's$ in the beginning, then each number after that is the sum of two previous numbers in the sequence. So a fibonacci sequence is going to be:

1 1 2 3 5 8 13 21 34 .......

Computation of Nth Fibonacci Number

The definition of of Nth Fibonacci Number fib(n) is recursive in nature. i.e.

 
fib(n) = fib(n-2) + fib(n-1)
  

So the nth Fibonacci number can be easily computed using this recursive relation.

	//--------------------------------------------------------------------------
	/**
	* Compute nth Fibonacci number using Recursion
	*/
	public static long fib_recursion(int n) {
	if (n == 0) {
	return 0;
	}
	if (n == 1) {
	return 1;
	}
	return fib_recursion(n-2) + fib_recursion(n-1);
	} // fib
	//--------------------------------------------------------------------------

view raw Fibonacci.java hosted with ❤ by GitHub

Problem

The problem with this solution is we are going to be computing same computation over and over again.

As you can see from the recursion tree, fib() method is called multiple times for the same value. The time complexity of this solution is going to be ${\cal O}(2^n)$ and the space complexity if ${\cal O}(1)$.

Memoization Solution

Since we are computing same computation over and over again, we could store our intermediate result and use it instead of computing again.

	//--------------------------------------------------------------------------
	/**
	* Compute nth Fibonacci number using memoization
	*/
	public static long fib_memoization(int n, long[] mem) {
	if (n == 0 || n == 1) {
	mem[n] = n;
	return n;
	}
	if (mem[n] == 0) {
	mem[n] = fib_memoization(n-2, mem) + fib_memoization(n-1, mem);
	}
	return mem[n];
	} // fib
	//--------------------------------------------------------------------------

view raw Fibonacci.java hosted with ❤ by GitHub

Complexity

Time complexity of this solution is ${\cal O}(n)$ and the Space Complexity is also ${\cal O}(n)$.

Dynamic Programming - Bottom Up Solution

Similar to Memoization, we can also solve it using Dynamic Programming - Bottom Up Approach.

	//--------------------------------------------------------------------------
	/**
	* Compute nth Fibonacci number using DP
	*/
	public static long fib_dp(int n) {
	long[] dp = new long[n+1];
	for (int i = 0; i <= n; i++) {
	if (i == 0 || i == 1) {
	dp[i] = i;
	continue;
	}
	dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[n];
	} // fib3
	//--------------------------------------------------------------------------

view raw Fibonacci.java hosted with ❤ by GitHub

Complexity

Time complexity of this solution is ${\cal O}(n)$ and the Space Complexity is also ${\cal O}(n)$.

Modified Dynamic Programming

We can see in the dynamic programming that to compute next fibonacci number we use only Two of the previous results. So we can infer that we don't need to store all previous results. Its enough to store only two previous results. Following is the solution using this principle.

	//--------------------------------------------------------------------------
	/**
	* Compute nth Fibonacci number using modified DP
	*/
	public static long fib_dp_modified(int n) {
	if (n == 0 || n == 1) {
	return n;
	}
	long first = 0;
	long second = 1;
	int k = 2;
	do {
	long temp = first + second;
	first = second;
	second = temp;
	if (k == n) {
	return second;
	}
	k++;
	} while (true);
	} // fib4
	//--------------------------------------------------------------------------

view raw Fibonacci.java hosted with ❤ by GitHub

Complexity

Time complexity of this solution is ${\cal O}(n)$ and the Space Complexity is ${\cal O}(1)$.

---

---

---

Kth Smallest Number in n x n Matrix

$\mathtt{REFERENCE}$ @ LeetCode

$\mathtt{RELATED\ PROBLEM\ -\ K\ Smallest\ Sum\ Pair}$

Task Description

Given an $n \times n$ integer Matrix sorted in non-decreasing order in row and column wise.

Find $kth$ smallest number in the matrix.

Solution 1 : Brute Force Solution

The naive solution would be to traverse through all the elements, sort them and find the $kth$ smallest item. There are $n^2$ elements in the matrix. Sorting them will take ${\cal O}(n^2log(n^2))$ time.

Solution 2: Efficient Solution

This Brute Force solution can be optimized by using Priority Queue. This solution is similar to the problem K Smallest Sum Pair.

    /**
    * Computes the Kth smallest item in the given row and column wise sorted 2D Matrix
    *
    */
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> smallestTracker = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                int x = matrix[a[0]][a[1]];
                int y = matrix[b[0]][b[1]];
                return x - y;
            }
        });
        
        for(int i = 0; i < matrix.length; i++) {
            smallestTracker.add(new int[]{i, 0});
        }
        
        int count = 0;
        int[] smallest = null;
        while (count < k) {
            smallest = smallestTracker.remove();
            if (smallest[1] < matrix.length - 1) {
                smallestTracker.add(new int[]{smallest[0], smallest[1] + 1});
            }
            count++;
        }
        return matrix[smallest[0]][smallest[1]];
    }

    

Time Complexity

Overall Time complexity is ${\cal O}(k log(n))$. The value $k$ can be $n^2$.
The space complexity is ${\cal O}(n)$ for the size of priority queue.

---

---

---

K Smallest Sum Pairs

$\mathtt{REFERENCE}$ @ LeetCode

$\mathtt{RELATED\ PROBLEM\ -\ Kth\ Smallest\ Numer\ in\ Sorted\ Matrix}$

Task Description

Given two integer arrays nums1 and nums1 sorted in non-decreasing order and an integer k.

Define a pair (u, v) consisting one element from the first array and one element from the second array.

Find k pairs with smallest sums.

Solution 1 : Brute Force Solution

The naive solution would be to find all possible pairs and find the best k pairs from it. If the two array contain n and m items, then there are nm possible pairs. Retrieving $k$ best pairs will take ${\cal \theta}(klog(mn))$ time.

Solution 2: Efficient Solution

This Brute Force solution can be optimized by using Priority Queue. The Priority Queue will hold sequence of number pairs (i, j) where $i$ is index in the first array and $j$ is that in the second array. Priority of the queue is determined by the sum of numbers at these indices.

  PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>(){
      @Override
      public int compare(int[] a, int[] b) {
          return nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]];
      }
  });

    

Initially, for $i\ =\ 0$, all pairs with the second array is inserted into the priority queue. At this time, the first priority element is minimum element.

  for (int i = 0; i < nums2.length; i++) {
      queue.offer(new int[]{0, i});
  }

    

Then we keep on polling an element from the queue and insert into the result. For each poll, we will insert into the queue, $i + 1$ pairing with its corresponding unpaired index so far in the second array. This is repeated untill the queue is not empty or untill we have all the $k$ pairs required.

  while(!queue.isEmpty() && res.size() < k) {
      int[] item = queue.poll();
      res.add(new int[]{nums1[item[0]], nums2[item[1]]});
      
      if (item[0] == nums1.length - 1) {
          continue;
      } else {
          queue.offer(new int[]{item[0] + 1, item[1]});
      }
  }

    

Full Code

    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> res = new ArrayList<int[]>();
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b) {
                return nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]];
            }
        });
        
        if(nums1.length == 0 || nums2.length == 0) {
            return res;
        }
        
        for (int i = 0; i < nums2.length; i++) {
            queue.offer(new int[]{0, i});
        }
        
        while(!queue.isEmpty() && res.size() < k) {
            int[] item = queue.poll();
            res.add(new int[]{nums1[item[0]], nums2[item[1]]});
            
            if (item[0] == nums1.length - 1) {
                continue;
            } else {
                queue.offer(new int[]{item[0] + 1, item[1]});
            }
        }
    
        return res;
    }

    

Time Complexity

Initial insertion into the priority queue takes ${\cal O}(m)$ time. During the iteration, for each minimum element polled from the queue, we insert at maximum only one element, hence the size of the queue is maintained ${\cal O}(m)$ and each iteration take ${\cal O}(log(m))$ time. The iteration is repeated untill we have all the $k$ results or the queue is empty. $\therefore$ Overall Time complexity is ${\cal O}(k log(m)) \approx {\cal O}(k log(n))$. The space complexity is ${\cal O}(n)$ for the size of priority queue.

---

---

---

Number Pairs Whose Sum is Multiple of a Number X

$\mathtt{DOWNLOAD\ SOLUTION}$

Task Description

Kelly gives Ashley N chocolates each having a price pi, (where pi is the price of ith chocolate), and an integer X. She asks her to group the N chocolates in to pairs such that sum of prices of chocolates in each pair is a multiple of X.

Output yes if its possible to group the chocolates in to pairs and No if its not possible.

Solution 1: Considering all possible $nC2$ pairs

The first solution is to try to form pairs and satisfies our constraint. If at any point, if the constraint is not satisfied, we will need to Backtrack and try out different pairs.

For the size of array $n$, there are total of $nC2 \approx n^2$ possible combinations. So the complexity will be ${\cal O}(n^2)$.

Solution 2: Optimization of Solution 1

Consider four numbers $a,\ b,\ c,\ d$
Let,

            a + c is a multiple of X
       and, b + d is a multiple of X
    

So the numbers can be paired as $[a,\ c]$ and $[b,\ d]$

Now,what will happen if $a + b$ is also a multiple of X?

  a + c = CONST1 * X
  b + d = CONST2 * X
  a + b = CONST3 * X

  a + b + c + d = (CONST1 + CONST2) * X
  CONST3 * X + (c + d) = (CONST1 + CONST2) * X
  c + d = (CONST1 + CONST2 - CONST3) * X

This proves that (c + d) is also a multiple of X.

So in general, if

• $a$ and $d$ pairs up,
• $a$ pairs up with a set of numbers $S1$ and
• $d$ pairs up with a set of numbers $S2$

Then, $a$ and $d$ can pair up with any number in the sets $S1$ and $S2$.

With this conclusion, we can optimise our Solution 1 by eliminating the Backtrack. We can keep on pairing up numbers. If all numbers have pairs, we can return True. If any number does not have a pair, we can return False.

	//-------------------------------------------------------------------------------
	/**
	* Linear Time solution to determine if all the numberes pairs up
	* O(n^2) solution
	* @param N number of elements in the array
	* @param X
	* @param p array of inputs
	* @return max profit
	*/
	public static void bruteForce(int N, int X, int[] p) {
	int[] paired = new int[N];
	boolean pairFound = false;
	if (N % 2 == 0) {
	for(int i = 0; i < N; i++) {
	if (paired[i] == 1) {
	continue;
	}
	pairFound = false;
	for(int j = i+1; j < N; j++) {
	if (i == j || paired[j] == 1) {
	continue;
	}
	int sum = p[i] + p[j];
	if (sum % X == 0) {
	pairFound = true;
	paired[i] = 1;
	paired[j] = 1;
	break;
	}
	}
	if (!pairFound) {
	break;
	}
	}
	}
	if (pairFound) {
	System.out.println("Yes");
	} else {
	System.out.println("No");
	}
	}
	//--------------------------------------------------------------------------------

view raw PairNumberByMultipleOfX.java hosted with ❤ by GitHub

Time Complexity

Even after the optimization, at worst case, for each element we need to go through all elements. $\therefore$ Total Time complexity is ${\cal O}(n^2)$. The space complexity is ${\cal O}(n)$ for the array paired.

Solution 3: Linear Time Solution

The problem can be solved in linear time by traversing the array only once.

Principle

If sum of two numbers a and b is multiple of a number X,

Then,

      (a % X) + (b % X) = X     if a % x > 0
                        = 0     if a % X == 0
    

So, in order for all numbers to pair up,

      number of elements in the array with modulo X value C  
          == number of elements in the array with module X value X - C
    

Following are the linear time solutions.

Solution Using Array

	//--------------------------------------------------------------------------------
	/**
	* Linear Time solution to determine if all the numberes pairs up
	* O(n) solution
	* @param N number of elements in the array
	* @param X
	* @param p array of inputs
	* @return max profit
	*/
	public static void efficient(int N, int X, int[] p) {
	int[] counts = new int[X]; // max value of X is 2000
	boolean unmatchFound = true;
	if (N % 2 == 0) { // no pairing for odd inputs
	for (int i = 0; i < N; i++) { // O(n)
	int idx = p[i] % X;
	counts[idx]++;
	}
	if (counts[0] % 2 != 1) {
	for (int i = 1; i <= X/2; i++) { // O(X)
	unmatchFound = false;
	if (counts[i] != counts[X-i]) {
	unmatchFound = true;
	break;
	}
	}
	}
	}
	if (unmatchFound) {
	System.out.println("No");
	} else {
	System.out.println("Yes");
	}
	}
	//---------------------------------------------------------------------------------------

view raw PairNumberByMultipleOfX.java hosted with ❤ by GitHub

Solution Using Hash Map

	//---------------------------------------------------------------------------------------
	/**
	* Linear Time solution to determine if all the numberes pairs up
	* O(n) solution
	* @param N number of elements in the array
	* @param X
	* @param p array of inputs
	* @return max profit
	*/
	public static void efficient2(int N, int X, int[] p) {
	Map<Integer, Integer> pairTracker = new HashMap<Integer, Integer>();
	boolean unmatchFound = true;
	if (N % 2 == 0) { // no pairing for odd inputs
	for (int i = 0; i < N; i++) { // O(n)
	int remainder = p[i] % X;
	if (!pairTracker.containsKey(remainder)) {
	pairTracker.put(remainder, 1);
	} else {
	pairTracker.put(remainder, pairTracker.get(remainder) + 1);
	}
	}
	if (!pairTracker.containsKey(0) || pairTracker.get(0) % 2 != 1) {
	for (int i = 1; i <= X/2; i++) { // O(X)
	unmatchFound = false;
	int count1 = pairTracker.containsKey(i) ? pairTracker.get(i) : 0;
	int count2 = pairTracker.containsKey(X-i) ? pairTracker.get(X-i) : 0;
	//System.out.println(i + " : " + (X-i) + " || " + count1 + " : " + count2);
	if (count1 != count2) {
	unmatchFound = true;
	break;
	}
	}
	}
	}
	if (unmatchFound) {
	System.out.println("No");
	} else {
	System.out.println("Yes");
	}
	}
	}

view raw PairNumberByMultipleOfX.java hosted with ❤ by GitHub

Time Complexity

In this solution, we traverse through the input array only once. Important thing to note here is, the size of the array count is the value of input integer X. So if there is no constraint over the value of X, then the solution could be Pseudo-Polynomial. Otherwise , the overall time complexity is ${\cal O}(n)$. The Space complexity is ${\cal O}(X)$.

---

---

---

Maximum Profit from given array of Stock Prices - Programming Problem

$\mathtt{REFERENCE}$ @ Interve Cake

Problem Definition

You are given an array of Stock Prices. Index of the array represents the time corresponding to a price. Smaller index represents past time and larger index represents future time.

Now you need to write a method that takes the array as an input and returns the best profit that could be made by buying 1 stock and selling 1 stock.

Example

  int[] stockPrices = new int[] {15, 5, 10, 25, 55, 1};

  getMaxProfit(stockPrices); // returns 50 (buy at $5 and sell at $55)

    

Only the stock bought at past can be sold in the future. So the time difference must be at least 1 for conducting the transaction.

Brute Force Solution

Brute Force solution would be to consider every valid pair and keep updating the maximum profit that can be made.

  /**
   * Brute Force Approach to calculate the profit
   * @param stockPrices input stock prices
   * @return max profit
   */
  public static int getMaxProfit(int[] stockPrices) {
    int maxProfit = Integer.MIN_VALUE;

    for (int i = 0; i < stockPrices.length; i++) {
      for (int j = i+1; j < stockPrices.length; j++) {
        int profit = stockPrices[j] - stockPrices[i];
        if (profit > maxProfit) {
          maxProfit = profit;
        }
      }
    }

    return maxProfit;
  } // getMaxProfit

    

Time Complexity

The outer loop runs for all the prices i.e. $n$ times $n$ being the number of stock prices.

For the first outer loop, the inner loop runs for $n-1$ times
For the second outer loop, the inner loop runs for $n-2$ times
For the third outer loop, the inner loop runs for $n-3$ times and so on until 0.

So, the two loops run for $(n-1) + (n-2) + (n-3) + ...... + 2 + 1 + 0 \approx n^2$ times. Operations inside the loops are constant time operations.

$\therefore$ Total Time complexity is ${\cal O}(n^2)$. The space complexity is ${\cal O}(1)$.

Linear Time Solution

The problem can be solved in linear time by traversing the array only once. For each item traversed, we store the minimum value of the stock seen so far and update the maximum profit greedily.

  /**
   * Linear Time solution to find the max profit
   * @param stockPrices input stock prices
   * @return max profit
   */
  public static int getMaxProfit(int[] stockPrices) {
    int maxProfit = Integer.MIN_VALUE;
    int minPrice = stockPrices[0];

    for (int i = 1; i < stockPrices.length; i++) {
      int profit = stockPrices[i] - minPrice;
      if (maxProfit < profit) {
        maxProfit = profit;
      }

      if (minPrice > stockPrices[i]) {
        minPrice = stockPrices[i];
      }

    }
    return maxProfit;
  } // getMaxProfit

    

Time Complexity

In this solution, the stock prices are accessed only once. And for the stock price the processing is constant time.

$\therefore$ The overall time complexity is ${\cal O}(n)$. The Space complexity remains ${\cal O}(1)$.

Implementation

	/* File: StockBenefit.java
	* Created: 2018-04-04
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	/**
	* Compute potential max profit
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class StockBenefit {
	public static void main(String[] args) {
	int[] stocks = new int[] {10, 7, 5, 8, 11, 9};
	int profit = getMaxProfit(stocks);
	int expectedProfit = 6;
	verify(expectedProfit, profit);
	stocks = new int[] {15, 5, 10, 25, 55, 1};
	profit = getMaxProfit(stocks);
	expectedProfit = 50;
	verify(expectedProfit, profit);
	stocks = new int[] {10, 9, 8, 7, 6, 5};
	profit = getMaxProfit(stocks);
	expectedProfit = -1;
	verify(expectedProfit, profit);
	stocks = new int[] {10, 10, 10, 10, 10, 10};
	profit = getMaxProfit(stocks);
	expectedProfit = 0;
	verify(expectedProfit, profit);
	stocks = new int[] {10, 7, 5, 8, 11, 9};
	profit = getMaxProfit_2(stocks);
	expectedProfit = 6;
	verify(expectedProfit, profit);
	stocks = new int[] {15, 5, 10, 25, 55, 1};
	profit = getMaxProfit_2(stocks);
	expectedProfit = 50;
	verify(expectedProfit, profit);
	stocks = new int[] {10, 9, 8, 7, 6, 5};
	profit = getMaxProfit_2(stocks);
	expectedProfit = -1;
	verify(expectedProfit, profit);
	stocks = new int[] {10, 10, 10, 10, 10, 10};
	profit = getMaxProfit_2(stocks);
	expectedProfit = 0;
	verify(expectedProfit, profit);
	} // main
	//-------------------------------------------------------------------------------------
	/**
	* Assertion method to verify two values
	* @param expected
	* @param actual
	*/
	public static void verify(int expected, int actual) {
	if (expected != actual) throw new AssertionError();
	} // verify
	//-------------------------------------------------------------------------------------
	/**
	* Brute Force Approach to calculate the profit
	* @param stockPrices input stock prices
	* @return max profit
	*/
	public static int getMaxProfit(int[] stockPrices) {
	int maxProfit = Integer.MIN_VALUE;
	for (int i = 0; i < stockPrices.length; i++) {
	for (int j = i+1; j < stockPrices.length; j++) {
	int profit = stockPrices[j] - stockPrices[i];
	if (profit > maxProfit) {
	maxProfit = profit;
	}
	}
	}
	return maxProfit;
	} // getMaxProfit
	//-------------------------------------------------------------------------------------
	/**
	* Linear Time solution to find the max profit
	* @param stockPrices input stock prices
	* @return max profit
	*/
	public static int getMaxProfit_2(int[] stockPrices) {
	int maxProfit = Integer.MIN_VALUE;
	int minPrice = stockPrices[0];
	for (int i = 1; i < stockPrices.length; i++) {
	int profit = stockPrices[i] - minPrice;
	if (maxProfit < profit) {
	maxProfit = profit;
	}
	if (minPrice > stockPrices[i]) {
	minPrice = stockPrices[i];
	}
	}
	return maxProfit;
	} // getMaxProfit_2
	} // StockBenefit

view raw StockBenefit.java hosted with ❤ by GitHub

---

---

---

Building a Smart IDE: Identifying comments - HackerRank Problem

Difficulty: $\mathtt{Very\ Very\ Easy}$

Find the problem definition @ HackerRank

Solution

Simply travers thorugh each line and display the line when you know the line or part of it is comment

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        boolean comment = false;
        while(sc.hasNext()) {
            String line = sc.nextLine();
            
            if (line.trim().startsWith("/*")) comment = true;
            
            if (comment || line.trim().startsWith("//")) {
                System.out.println(line.trim());
            } else if (line.contains("//")) {
                int index = line.indexOf("//");
                System.out.println(line.substring(index));
            }
            
            if (line.endsWith("*/")) {
                comment = false;
            }
        }
    }
}

    

Time Complexity

The while loop in the code runs for $n$ number of times $n$ being the number of lines in the input. Time complexity of each loop depends upon the time taken by the methods like startsWith(), trim(), contains(), indexOf(), endsWith() and substring() of the String class.

Assuming all these methods are optimised to have the complexity ${\cal O})(n)$, $n$ being lenght of each line, overall complexity of the above solution is ${\cal O})(N)$, $N$ being total length of all lines.

Notes

Above solution doesn't considers special cases as:

• Comments like /* Comment */ is nested inside a code.
• String like // is a part of String constant in a code
• String like /* */ is a part of String constant in a code

---

---

---

Electronics Shop - HackerRank Problem

Find the problem definition @ HackerRank

Brute-Force Solution

Using the Brute-Force method, this problem can be solved by considering every possible pairs. If the considered pair gives better result (i.e > max) and satisfies the constraints (i.e. <= s), then we select current pair as the solution. Result is returned after all the pairs have been considered.

  /**
   * Brute Force Solution
   * @param s
   * @param keyboards
   * @param drives
   * @return
   */
  public int getMoneySpent(int s, int[] keyboards, int[] drives) {
    int max = -1;
    for (int i = 0; i < keyboards.length; i++) {
      for (int j = 0; j < drives.length; j++) {
        int amount = keyboards[i] + drives[j];
        if (amount > max && amount <= s ) {
          if (max == s) return max;
          max = amount;
        }
      }
    }
    return max;
  }    
    

Time Complexity

Time Complexity of this solution depends upon the number of pairs considered. Since there are $n\ keyboards$ and $m\ drives$, total of $n \times m$ pairs are considered. Processing time for each pair, as we can see in the code, is constant time operation ${\cal O}(1)$. $\therefore$ The time complexity of this solution is ${\cal O}(n \times m)$. The space complexity is ${\cal O}(1)$ since we haven't use any extra data structure to hold inputs.

Better Solution

The problem could be optimized to solve in better time complexity. We can Sort one of the array and iterate through other array. While iterating through the other array, we apply the Binary Search on the sorted array to obtain the best pair. In order to keep the complexity low (Do the maths on your own ), I am going to sort the array with lower number of elements and iterate over the other one.

/**
   * Computes using Binary Search
   * @param keyboards
   * @param drives
   * @param s
   * @return
   */
  public int getMoneySpent(int[] keyboards, int[] drives, int s) {
    int max = -1;
    int[] larger = keyboards.length > drives.length ? keyboards : drives;
    int[] smaller = keyboards.length > drives.length ? drives : keyboards;

    Arrays.sort(smaller); // O(k logk)

    for (int i = 0; i < larger.length; i++) {  // O(n)
      if (larger[i] < s) {
        int pair = search(smaller, s - larger[i], 0, smaller.length); // O(logk)
        if (pair == -1) continue;
        if (max < smaller[pair] + larger[i]) {
          max = smaller[pair] + larger[i];
        }
      }
    }
    return max;
  } // getMoneySpent
  
  //----------------------------------------------------------------------------------

  /**
   * Searches the best pair using Binary Search
   * @param in
   * @param item
   * @param lo
   * @param hi
   * @return
   */
  public int search(int[] in, int item, int lo, int hi) {
    if (item < in[lo]) return -1;
    while (hi - lo > 1) {
      int midIdx = (lo + hi) / 2;
      if (item == in[midIdx]) return midIdx;
      else if (item > in[midIdx]) {
        lo = midIdx;
      } else {
        hi = midIdx;
      }
    }
    return lo;
  } // search

    

Time Complexity

Time Complexity of the solution depends upon the sorting of smaller array, iteration of larger array and the binary search on the sorted array.

Let, $n =$ Number of Elements in the larger array
       $k =$ Number of Elments in the smaller array

Then,

1. Time Complexity of Sorting = ${\cal O})(k\ logk)$
2. Time Complexity of iteration = ${\cal O}(n)$
3. Time Complexity of Binary Serach = ${\cal O}(logk)$

$\therefore$ The overall Time Complexity is ${\cal O}(k\ logk + n\ logk) \approx {\cal O}(n\ logk)$. The Space Complexity is ${\cal O}(1)$

---

---

---