Skip to content

Instantly share code, notes, and snippets.

@RecuencoJones
Last active August 29, 2015 14:23
Show Gist options
  • Save RecuencoJones/d6eba9c70a9ffceeec39 to your computer and use it in GitHub Desktop.
Save RecuencoJones/d6eba9c70a9ffceeec39 to your computer and use it in GitHub Desktop.
Calcular el producto de todos los pares mayores que 5 sin incluir el número par más grande
/*
* Calcular el producto de todos los pares mayores que 5 sin
* incluir el número par más grande
*/
var l1 = [1,8,2,15,6,7,8,12]; //384
var l2 = [12,8,2,15,6,7,8,12]; //384
var l3 = [1,8,2,15,6,7,8,12,12]; //384
var l4 = [1,8,2,15,12,6,7,8,12]; //384
var l5 = [12,8,7,6,15,2,8,1]; //384
var l6 = [12,6,8,8]; //384
//var l7 = [12]; //0 --> Error!
var l8 = [12,6]; //6
//var l9 = [12,2,12]; //0 --> Error!
var l10 = [6,12,6,18,6]; //2592
/**
* Input: List of int values
* Output: List of tuple of size 2 each containing a number
* featured in the list and its number of repetitions
* Complexity: O(n^3) + O(n^2) + O(n^2) + O(n^3) = 2*O(n^3)
* Worst case: No repeated values (copy full array again)
*/
Array.prototype.group = function(){
var list = this;
var unique = [], times = [];
// Create array of distinct values
// O(length(list))*O(length(unique))*O(length(unique))
// = O(n)*O(n)*O(n) = O(n^3) <- iter * indexOf * push
// worst case: no repeated values
list.forEach(function(o){
if(unique.indexOf(o)==-1){ // indexOf has O(n) http://stackoverflow.com/questions/19287033/what-is-the-time-complexity-of-javascripts-array-indexof
unique.push(o); //push has O(n) http://stackoverflow.com/questions/22614237/javascript-runtime-complexity-of-array-functions
}
});
// initialize array of repetitions to 0 for each distinct value
// O(length(unique))*O(length(unique))
// = O(n)*O(n) = O(n^2) <- iter * push
unique.forEach(function(){times.push(0)});
// count repetitions of each value
// O(length(list))*O(i)*O(length(unique))
// = O(n)*O(1)*O(n) = O(n^2) <- iter * access * indexOf
list.forEach(function(i){
times[unique.indexOf(i)]++;
});
// map unique values and their repetitions into tuple
// O(length(unique))*O(length(unique))*O(i)*O(length(times))
// = O(n)*O(n)*O(1)*O(n) = O(n^3) <- iter * push * access * indexOf
return unique.map(function(x) {
return [x, times[unique.indexOf(x)]];
});
};
/**
* Input: List of tuple of size 2
* Tuple: [base, exponent]
* Output: List of int
*/
Array.prototype.powerTuple = function(){
return this.map(function (x) {
return Math.pow(x[0], x[1]);
});
};
function magic(a){
// example with l1
return a // [1,8,2,15,6,7,8,12]
.filter(function(x) { return x%2 == 0; }) // [8,2,6,8,12]
.filter(function(x) { return x>5; }) // [8,6,8,12]
.sort(function(a,b) { return b-a; }) // [12,8,8,6]
.group() // [[12,1],[8,2],[6,1]]
.splice(1) // [[8,2],[6,1]]
.powerTuple() // [64,6]
.reduce(function(x,y) { return x*y; }); // 384
}
console.log(l1,"-->",magic(l1));
console.log(l2,"-->",magic(l2));
console.log(l3,"-->",magic(l3));
console.log(l4,"-->",magic(l4));
console.log(l5,"-->",magic(l5));
console.log(l6,"-->",magic(l6));
//console.log(l7,"-->",magic(l7));
console.log(l8,"-->",magic(l8));
//console.log(l9,"-->",magic(l9));
console.log(l10,"-->",magic(l10));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment