8000 Merge branch 'master' into feat-bitwise-multiply · trekhleb/javascript-algorithms@820de5f · GitHub
[go: up one dir, main page]
Skip to content

Commit 820de5f

Browse files
adityahiranadityahiran
authored
Merge branch 'master' into feat-bitwise-multiply
2 parents 1bd3f1d + 7dc60c9 commit 820de5f

File tree

11 files changed

+173
-76
lines changed

11 files changed

+173
-76
lines changed

‎.travis.yml

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,8 +3,11 @@ dist: trusty
33
language: node_js
44
node_js:
55
- node
6+
install:
7+
- npm install -g codecov
8+
- npm install
69
script:
710
- npm run ci
8-
- npm run codecov
11+
- codecov
912
notifications:
1013
email: false

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,6 +67,7 @@ a set of rules that precisely define a sequence of operations.
6767
* `B` [Pascal's Triangle](src/algorithms/math/pascal-triangle)
6868
* `B` [Complex Number](src/algorithms/math/complex-number) - complex numbers and basic operations with them
6969
* `B` [Radian & Degree](src/algorithms/math/radian) - radians to degree and backwards conversion
70+
* `B` [Fast Powering](src/algorithms/math/fast-powering)
7071
* `A` [Integer Partition](src/algorithms/math/integer-partition)
7172
* `A` [Liu Hui π Algorithm](src/algorithms/math/liu-hui) - approximate π calculations based on N-gons
7273
* `A` [Discrete Fourier Transform](src/algorithms/math/fourier-transform) - decompose a function of time (a signal) into the frequencies that make it up
@@ -163,6 +164,7 @@ algorithm is an abstraction higher than a computer program.
163164
* `B` [Tree Depth-First Search](src/algorithms/tree/depth-first-search) (DFS)
164165
* `B` [Graph Depth-First Search](src/algorithms/graph/depth-first-search) (DFS)
165166
* `B` [Jump Game](src/algorithms/uncategorized/jump-game)
167+
* `B` [Fast Powering](src/algorithms/math/fast-powering)
166168
* `A` [Permutations](src/algorithms/sets/permutations) (with and without repetitions)
167169
* `A` [Combinations](src/algorithms/sets/combinations) (with and without repetitions)
168170
* **Dynamic Programming** - build up a solution using previously found sub-solutions

‎package-lock.json

Lines changed: 0 additions & 23 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎package.json

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -6,8 +6,7 @@
66
"scripts": {
77
"lint": "eslint ./src/*",
88
"test": "jest",
9-
"ci": "npm run lint && npm run test -- --coverage",
10-
"codecov": "codecov"
9+
"ci": "npm run lint && npm run test -- --coverage"
1110
},
1211
"pre-commit": [
1312
"lint",
@@ -27,7 +26,9 @@
2726
"javascript-algorithms",
2827
"sorting-algorithms",
2928
"graph",
30-
"tree"
29+
"tree",
30+
"interview",
31+
"interview-preparation"
3132
],
3233
"author": "Oleksii Trekhleb (https://www.linkedin.com/in/trekhleb/)",
3334
"license": "MIT",
@@ -39,7 +40,6 @@
3940
"@types/jest": "^23.1.4",
4041
"babel-cli": "^6.26.0",
4142
"babel-preset-env": "^1.7.0",
42-
"codecov": "^3.0.2",
4343
"eslint": "^4.19.1",
4444
"eslint-config-airbnb": "^17.0.0",
4545
"eslint-plugin-import": "^2.13.0",

‎src/algorithms/math/fast-powering/README.md

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
# Fast Powering Algorithm
2+
3+
**The power of a number** says how many times to use the number in a
4+
multiplication.
5+
6+
It is written as a small number to the right and above the base number.
7+
8+
![Power](https://www.mathsisfun.com/algebra/images/exponent-8-2.svg)
9+
10+
## Naive Algorithm Complexity
11+
12+
How to find `a` raised to the power `b`?
13+
14+
We multiply `a` to itself, `b` times. That
15+
is, `a^b = a * a * a * ... * a` (`b` occurrences of `a`).
16+
17+
This operation will take `O(n)` time since we need to do multiplication operation
18+
exactly `n` times.
19+
20+
## Fast Power Algorithm
21+
22+
Can we do better than naive algorithm does? Yes we may solve the task of
23+
powering in `O(log(n))` time.
24+
25+
The algorithm uses divide and conquer approach to compute power. Currently the
26+
algorithm work for two positive integers `X` and `Y`.
27+
28+
The idea behind the algorithm is based on the fact that:
29+
30+
For **even** `Y`:
31+
32+
```text
33+
X^Y = X^(Y/2) * X^(Y/2)
34+
```
35+
36+
For **odd** `Y`:
37+
38+
```text
39+
X^Y = X^(Y//2) * X^(Y//2) * X
40+
where Y//2 is result of division of Y by 2 without reminder.
41+
```
42+
43+
**For example**
44+
45+
```text
46+
2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2)
47+
```
48+
49+
```text
50+
2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2)
51+
```
52+
53+
Now, since on each step we need to compute the same `X^(Y/2)` power twice we may optimise
54+
it by saving it to some intermediate variable to avoid its duplicate calculation.
55+
56+
**Time Complexity**
57+
58+
Since each iteration we split the power by half then we will call function
59+
recursively `log(n)` times. This the time complexity of the algorithm is reduced to:
60+
61+
```text
62+
O(log(n))
63+
```
64+
65+
## References
66+
67+
- [YouTube](https://www.youtube.com/watch?v=LUWavfN9zEo&index=80&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&t=0s)
68+
- [Wikipedia](https://en.wikipedia.org/wiki/Exponentiation_by_squaring)

‎src/algorithms/math/fast-powering/__test__/fastPowering.test.js

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
import fastPowering from '../fastPowering';
2+
3+
describe('fastPowering', () => {
4+
it('should compute power in log(n) time', () => {
5+
expect(fastPowering(1, 1)).toBe(1);
6+
expect(fastPowering(2, 0)).toBe(1);
7+
expect(fastPowering(2, 2)).toBe(4);
8+
expect(fastPowering(2, 3)).toBe(8);
9+
expect(fastPowering(2, 4)).toBe(16);
10+
expect(fastPowering(2, 5)).toBe(32);
11+
expect(fastPowering(2, 6)).toBe(64);
12+
expect(fastPowering(2, 7)).toBe(128);
13+
expect(fastPowering(2, 8)).toBe(256);
14+
expect(fastPowering(3, 4)).toBe(81);
15+
expect(fastPowering(190, 2)).toBe(36100);
16+
expect(fastPowering(11, 5)).toBe(161051);
17+
expect(fastPowering(13, 11)).toBe(1792160394037);
18+
expect(fastPowering(9, 16)).toBe(1853020188851841);
19+
expect(fastPowering(16, 16)).toBe(18446744073709552000);
20+
expect(fastPowering(7, 21)).toBe(558545864083284000);
21+
expect(fastPowering(100, 9)).toBe(1000000000000000000);
22+
});
23+
});

‎src/algorithms/math/fast-powering/fastPowering.js

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/**
2+
* Fast Powering Algorithm.
3+
* Recursive implementation to compute power.
4+
*
5+
* Complexity: log(n)
6+
*
7+
* @param {number} base - Number that will be raised to the power.
8+
* @param {number} power - The power that number will be raised to.
9+
* @return {number}
10+
*/
11+
export default function fastPowering(base, power) {
12+
if (power === 0) {
13+
// Anything that is raised to the power of zero is 1.
14+
return 1;
15+
}
16+
17+
if (power % 2 === 0) {
18+
// If the power is even...
19+
// we may recursively redefine the result via twice smaller powers:
20+
// x^8 = x^4 * x^4.
21+
const multiplier = fastPowering(base, power / 2);
22+
return multiplier * multiplier;
23+
}
24+
25+
// If the power is odd...
26+
// we may recursively redefine the result via twice smaller powers:
27+
// x^9 = x^4 * x^4 * x.
28+
const multiplier = fastPowering(base, Math.floor(power / 2));
29+
return multiplier * multiplier * base;
30+
}

‎src/algorithms/sets/maximum-subarray/__test__/bfMaximumSubarray.test.js

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,10 @@ import bfMaximumSubarray from '../bfMaximumSubarray';
33
describe('bfMaximumSubarray', () => {
44
it('should find maximum subarray using brute force algorithm', () => {
55
expect(bfMaximumSubarray([])).toEqual([]);
6+
expect(bfMaximumSubarray([0, 0])).toEqual([0]);
7+
expect(bfMaximumSubarray([0, 0, 1])).toEqual([0, 0, 1]);
8+
expect(bfMaximumSubarray([0, 0, 1, 2])).toEqual([0, 0, 1, 2]);
9+
expect(bfMaximumSubarray([0, 0, -1, 2])).toEqual([2]);
610
expect(bfMaximumSubarray([-1, -2, -3, -4, -5])).toEqual([-1]);
711
expect(bfMaximumSubarray([1, 2, 3, 2, 3, 4, 5])).toEqual([1, 2, 3, 2, 3, 4, 5]);
812
expect(bfMaximumSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])).toEqual([4, -1, 2, 1]);

‎src/algorithms/sets/maximum-subarray/__test__/dpMaximumSubarray.test.js

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,10 @@ import dpMaximumSubarray from '../dpMaximumSubarray';
33
describe('dpMaximumSubarray', () => {
44
it('should find maximum subarray using dynamic programming algorithm', () => {
55
expect(dpMaximumSubarray([])).toEqual([]);
6+
expect(dpMaximumSubarray([0, 0])).toEqual([0]);
7+
expect(dpMaximumSubarray([0, 0, 1])).toEqual([0, 0, 1]);
8+
expect(dpMaximumSubarray([0, 0, 1, 2])).toEqual([0, 0, 1, 2]);
9+
expect(dpMaximumSubarray([0, 0, -1, 2])).toEqual([2]);
610
expect(dpMaximumSubarray([-1, -2, -3, -4, -5])).toEqual([-1]);
711
expect(dpMaximumSubarray([1, 2, 3, 2, 3, 4, 5])).toEqual([1, 2, 3, 2, 3, 4, 5]);
812
expect(dpMaximumSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])).toEqual([4, -1, 2, 1]);

‎src/algorithms/sets/maximum-subarray/dpMaximumSubarray.js

Lines changed: 29 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -6,57 +6,40 @@
66
* @return {Number[]}
77
*/
88
export default function dpMaximumSubarray(inputArray) {
9-
// Check if all elements of inputArray are negative ones and return the highest
10-
// one in this case.
11-
let allNegative = true;
12-
let highestElementValue = null;
13-
for (let i = 0; i < inputArray.length; i += 1) {
14-
if (inputArray[i] >= 0) {
15-
allNegative = false;
16-
}
17-
18-
if (highestElementValue === null || highestElementValue < inputArray[i]) {
19-
highestElementValue = inputArray[i];
20-
}
21-
}
22-
23-
if (allNegative && highestElementValue !== null) {
24-
return [highestElementValue];
25-
}
26-
27-
// Let's assume that there is at list one positive integer exists in array.
28-
// And thus the maximum sum will for sure be grater then 0. Thus we're able
29-
// to always reset max sum to zero.
30-
let maxSum = 0;
31-
32-
// This array will keep a combination that gave the highest sum.
33-
let maxSubArray = [];
34-
35-
// Current sum and subarray that will memoize all previous computations.
9+
// We iterate through the inputArray once, using a greedy approach to keep track of the maximum
10+
// sum we've seen so far and the current sum.
11+
//
12+
// The currentSum variable gets reset to 0 every time it drops below 0.
13+
//
14+
// The maxSum variable is set to -Infinity so that if all numbers are negative, the highest
15+
// negative number will constitute the maximum subarray.
16+
17+
let maxSum = -Infinity;
3618
let currentSum = 0;
37-
let currentSubArray = [];
3819

39-
for (let i = 0; i < inputArray.length; i += 1) {
40-
// Let's add current element value to the current sum.
41-
currentSum += inputArray[i];
20+
// We need to keep track of the starting and ending indices that contributed to our maxSum
21+
// so that we can return the actual subarray. From the beginning let's assume that whole array
22+
// is contributing to maxSum.
23+
let maxStartIndex = 0;
24+
let maxEndIndex = inputArray.length - 1;
25+
let currentStartIndex = 0;
26+
27+
inputArray.forEach((currentNumber, currentIndex) => {
28+
currentSum += currentNumber;
29+
30+
// Update maxSum and the corresponding indices if we have found a new max.
31+
if (maxSum < currentSum) {
32+
maxSum = currentSum;
33+
maxStartIndex = currentStartIndex;
34+
maxEndIndex = currentIndex;
35+
}
4236

37+
// Reset currentSum and currentStartIndex if currentSum drops below 0.
4338
if (currentSum < 0) {
44-
// If the sum went below zero then reset it and don't add current element to max subarray.
4539
currentSum = 0;
46-
// Reset current subarray.
47-
currentSubArray = [];
48-
} else {
49-
// If current sum stays positive then add current element to current sub array.
50-
currentSubArray.push(inputArray[i]);
51-
52-
if (currentSum > maxSum) {
53-
// If current sum became greater then max registered sum then update
54-
// max sum and max subarray.
55-
maxSum = currentSum;
56-
maxSubArray = currentSubArray.slice();
57-
}
40+
currentStartIndex = currentIndex + 1;
5841
}
59-
}
42+
});
6043

61-
return maxSubArray;
44+
return inputArray.slice(maxStartIndex, maxEndIndex + 1);
6245
}

0 commit comments

Comments
 (0)
0