iamthuypham
1/25/2018 - 6:37 PM

Algorithm - The Different Way to Learn

Learn Algorithm for a better world, not a better job

ReverseInteger.js
content_copyfile_download
function reverse2(n){
  var m = n.toString().split('')
  var i = 0
  while (i < m.length/2){
    var left = m[i]
    // Move right to left
    m[i] = m[m.length-1-i]
    //Move left to right
    m[m.length-1-i] = left
    i++
  }
  m = parseInt(m.join(''))
  return m 
}

//Time Complexity: O(n)
Find 2 integers which sum equals to a given number.md
content_copyfile_download
  • Rendered
  • Source

Input

An array of integers without duplicates array = [2,7,11,15] A number sum = 9

Ouput

Indices of 2 integers [0,1]

Explaination

array[0] + array[1] = 2 + 7 = 9 = sum

Pseudocode

  1. Write down the structure
function(array, sum) 
  ...
  return [i,j]
  1. Common approach
function(array, sum) 
  \!h loop array
  \!h find 2
  \!h store i which is index of 2
  \!h do math 9 - 2 = 7
  \!h find 7
  \!h store j which is index of 7
  
  ...
  return [i,j]
  1. What If?
  • What if I have an infinitive array of random stars' position [2,11,15,...]
  • And I have a telescope which allows to view within 9 diameter
  • Note that I even unsure that 7 exists
  1. Start over!
function(array, sum) 
  ...
  return [i,j]
  1. Narrow down
function(array, sum) 
  \!h find xmin = min number in array = 2
  \!h find xmax = 9 - xmin = 9 - 2 = 7
  \!h find xmed = 9/2 = 4.5 ~ 4
  
  ...
  
  \!h find xi = first number
  \!h find xj = second number
  return [i,j]
  1. So, somehow, ...
  • xi should be in range [xmin, xmed] = [2,4]
  • xj should be in range [xmed, xmax] = [4,7]
  • Note that I don't have to worry about 11 or 15 because they are out of range
  1. Organize
function(array, sum) 
  // find xmin = min number in array = 2
  // find xmax = sum - xmin = 9 - 2 = 7
  // find xmed = sum/2 = 9/2 = 4.5 ~ 4
  
  var xmin = Math.min(array)
  var xmax = sum - xmin
  var xmed = sum/2 
  
  // distribute numbers to 2 ranges [xmin, xmed] and [xmed, xmax]
  var xrange1 = []
  var xrange2 = []
  var i=0
  
  while (i<array.length) {
    if (array[i] > xmax || array[i] < xmin) {
      i++
    } else {
      if (array[i] < xmed) {
        xrange1.push(array[i])
      } else {
        xrange2.push(array[i])
      }  
    }
  }
  
  // find xi = list of first number
  // find xj = list of second number
  
  var x1 = 0
  var x2 = xrange2.length - 1
  var xi = []
  var xj = []
  
  while (x1 < xrange1.length && x2 > 0) {
    if (xrange1[x1] + xrange2[x2] === sum) {
      xi.push(xrange1[x1]) 
      xj.push(xrange2[x2])
      x1++
      x2--
    } else if (xrange1[x1] + xrange2[x2] > sum) {
      x2--
    } else {
      x1++
    }
  }
  
  // return result = list of pairs of numbers
  
  var result = [] 
  for (var t=0;t<xi.length;t++){
    result.push([xi[t],xj[t])
  }

Time Complexity: mlogm + nlogn + m + n