Skip to content

Instantly share code, notes, and snippets.

View vadimkorr's full-sized avatar
🦉

Vadim vadimkorr

🦉
View GitHub Profile
//Task: Find the greatest common divisor for an array of integers
//Tags: array, gcd
let arr = [6, 9, 21]
let gcd = function(a, b) {
a = Math.abs(a)
b = Math.abs(b)
while (a != b) {
if (a > b) a -= b
// Task: Given array of size 2*N-1, containing N-1 pairs of same integers and one unique integer.
// Find unique integer without sorting array - it's too big
// Complexity: O(n)
let findUnique = function(lst) {
let map = new Map();
lst.forEach((id) => {
if (map.has(id)) map.delete(id);
else map.set(id, 1);
})
// Task: Given an array of N numbers.
// Find longest subsequence of increasing numbers
let findLongestSubs = function(arr) {
if (arr.length === 0) {
return null;
} else if (arr.length === 1) {
return arr[0];
} else {
let longestLen = 1;
@vadimkorr
vadimkorr / modular_exponentiation.js
Last active January 28, 2018 12:15
Find x^y mod p
// Find x^y mod p
// Right-to-left method
let modPow = (x, y, p) => {
let res = 1;
x %= p;
while(y>0) {
if (y%2 == 1) res = res*x % p
y = Math.floor(y/2)
x = x*x % p
@vadimkorr
vadimkorr / Amount of even numbers in range.js
Created January 28, 2018 12:23
Amount of even numbers in range
// Find amount of even numbers X in range: A <= X <= B
let find = (a, b) => {
return Math.floor((b - a) / 2) + (a%2==0 || b%2==0 ? 1 : 0)
}
console.log(find(1, 5)) // 2
console.log(find(1, 4)) // 2
console.log(find(2, 5)) // 2
console.log(find(2, 4)) // 2
@vadimkorr
vadimkorr / divisible by M.js
Created January 28, 2018 12:31
FInd numbers divisible by M
// Find numbers divisible by M in range A <= X <= B
let find = (a, b, m) => {
a = a%m == 0 ? a : a + m - a%m
while(a<=b) {
console.log(a);
a += m
}
console.log("===")
}
@vadimkorr
vadimkorr / fibonacci.js
Last active January 28, 2018 14:16
Calculate fibonacci numbers
// Calculate fibonacci numbers
let fibRec = (n) => {
if (n<=1) return n;
return fibRec(n-1) + fibRec(n-2);
}
let mem = [0, 1];
let fibMem = (n) => {
if (n<=1) return n;
// Merge two sorted arrays
let a = [2, 5, 7, 9, 10]
let b = [1, 3, 8, 10, 11, 15]
let c = []
let i = j =0
while (i < a.length && j < b.length) {
if(a[i] < b[j]) {
function dll() {
this.head = null
}
dll.prototype.push = function(val) {
let head = this.head, curr = head, prev = head
if (!head) this.head = { val: val, prev: null, next: null }
else {
while (curr && curr.next) {
prev = curr
// Insert a number to a sorted linked list with respect to the sorted order
function dll() {
this.head = null
}
dll.prototype.push = function(val) {
let head = this.head, curr = head, prev = head
if (!head) this.head = { val: val, prev: null, next: null }
else {