iamthuypham
1/25/2018 - 6:37 PM

## Algorithm - The Different Way to Learn

Learn Algorithm for a better world, not a better job

``````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)``````

### 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])
}
``````