Skip to content

Instantly share code, notes, and snippets.

@Nditah

Nditah/index.html

Created March 4, 2018 16:20
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Nditah/064998597353253b776308a0b9905eac to your computer and use it in GitHub Desktop.
Save Nditah/064998597353253b776308a0b9905eac to your computer and use it in GitHub Desktop.
Download ZIP
JS Permutation using Array and Set // source https://jsbin.com/yahuxas
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width">
<title>JS Permutation using Array and Set </title>
</head>
<body>
/**
// Problem
A permutation is a sequence containing each element from 1 to N once, and only once.
Write a function:
function solution(A);
that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.
// Optimal Solution
1. The easiet way to achieve that is to loop through 1 to N and check if every member is available
However, loop is 100% correctness and <20% performance at O(N**2)
2. The Second way is to test if the sum == to expected summation and product == factorial of the array
However, this method also has poor performance since facctorial is recursive.
3. The Best solution with 100% correctness and 100% performance is to check the sum and
also that the size of the set (number of distinct element of the set) ===length of array
*/
<script id="jsbin-javascript">
/**
// Problem
A permutation is a sequence containing each element from 1 to N once, and only once.
Write a function:
function solution(A);
that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.
// Optimal Solution
1. The easiet way to achieve that is to loop through 1 to N and check if every member is available
However, loop is 100% correctness and <20% performance at O(N**2)
2. The Second way is to test if the sum == to expected summation and product == factorial of the array
However, this method also has poor performance since facctorial is recursive.
3. The Best solution with 100% correctness and 100% performance is to check the sum and
also that the size of the set (number of distinct element of the set) ===length of array
*/
function solution(A = []) {
/*
function factorial(x) {
if (x === 0) {
return 1;
}
return x * factorial(x - 1);
}
*/
let N = A.length;
let result = 0;
if (N > 1) {
let maxi = Math.max(...A);
let sum = A.reduce(function (a, b) { return a + b; }, 0);
//let prod = A.reduce(function(a,b){return a*b;});
let sumEx = (1 + maxi) * N / 2;
// let prodEx = factorial(N);
let set = new Set(A);
if (maxi === N && sum === sumEx && set.size === N) result = 1;
else result = 0;
console.log("Sum " + sum + ", sumEx " + sumEx + ", set size " + set.size );
/*
// 100% correctness but 20% Perfomance
for (let i = 1; i < N + 2; i++) {
//if(!A.includes(i)) return i;
if (A.indexOf(i) === -1) return i;
}
*/
return result;
} else if (N == 1 && A[0] == 1) {
return 1;
} else {
return 0;
}
}
let B = [4, 1, 3, 2]; // 1
let A = [1, 2, 3, 5]; // 0
console.log(solution(B));
</script>
<script id="jsbin-source-javascript" type="text/javascript">
/**
// Problem
A permutation is a sequence containing each element from 1 to N once, and only once.
Write a function:
function solution(A);
that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.
// Optimal Solution
1. The easiet way to achieve that is to loop through 1 to N and check if every member is available
However, loop is 100% correctness and <20% performance at O(N**2)
2. The Second way is to test if the sum == to expected summation and product == factorial of the array
However, this method also has poor performance since facctorial is recursive.
3. The Best solution with 100% correctness and 100% performance is to check the sum and
also that the size of the set (number of distinct element of the set) ===length of array
*/
function solution(A = []) {
/*
function factorial(x) {
if (x === 0) {
return 1;
}
return x * factorial(x - 1);
}
*/
let N = A.length;
let result = 0;
if (N > 1) {
let maxi = Math.max(...A);
let sum = A.reduce(function (a, b) { return a + b; }, 0);
//let prod = A.reduce(function(a,b){return a*b;});
let sumEx = (1 + maxi) * N / 2;
// let prodEx = factorial(N);
let set = new Set(A);
if (maxi === N && sum === sumEx && set.size === N) result = 1;
else result = 0;
console.log("Sum " + sum + ", sumEx " + sumEx + ", set size " + set.size );
/*
// 100% correctness but 20% Perfomance
for (let i = 1; i < N + 2; i++) {
//if(!A.includes(i)) return i;
if (A.indexOf(i) === -1) return i;
}
*/
return result;
} else if (N == 1 && A[0] == 1) {
return 1;
} else {
return 0;
}
}
let B = [4, 1, 3, 2]; // 1
let A = [1, 2, 3, 5]; // 0
console.log(solution(B)); </script></body>
</html>
Raw
jsbin.yahuxas.js
/**
// Problem
A permutation is a sequence containing each element from 1 to N once, and only once.
Write a function:
function solution(A);
that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.
// Optimal Solution
1. The easiet way to achieve that is to loop through 1 to N and check if every member is available
However, loop is 100% correctness and <20% performance at O(N**2)
2. The Second way is to test if the sum == to expected summation and product == factorial of the array
However, this method also has poor performance since facctorial is recursive.
3. The Best solution with 100% correctness and 100% performance is to check the sum and
also that the size of the set (number of distinct element of the set) ===length of array
*/
function solution(A = []) {
/*
function factorial(x) {
if (x === 0) {
return 1;
}
return x * factorial(x - 1);
}
*/
let N = A.length;
let result = 0;
if (N > 1) {
let maxi = Math.max(...A);
let sum = A.reduce(function (a, b) { return a + b; }, 0);
//let prod = A.reduce(function(a,b){return a*b;});
let sumEx = (1 + maxi) * N / 2;
// let prodEx = factorial(N);
let set = new Set(A);
if (maxi === N && sum === sumEx && set.size === N) result = 1;
else result = 0;
console.log("Sum " + sum + ", sumEx " + sumEx + ", set size " + set.size );
/*
// 100% correctness but 20% Perfomance
for (let i = 1; i < N + 2; i++) {
//if(!A.includes(i)) return i;
if (A.indexOf(i) === -1) return i;
}
*/
return result;
} else if (N == 1 && A[0] == 1) {
return 1;
} else {
return 0;
}
}
let B = [4, 1, 3, 2]; // 1
let A = [1, 2, 3, 5]; // 0
console.log(solution(B));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment