###Time Complexity
O(1) is constant time, no matter how much data there is, it will take the same amount of time to find the answer
O(log n) is cutting the search area in half each time
O(n) is looping through each item once
O(n2) is looping through twice
0(nn) is looping through each value and having to do something with each value based on how many values came before it
####TapeEquilibrium
rewrite
A is an Array = [3,1,2,4,3]
N is the length of A
P is any integer between 0 and N
The total sum of A is 13
If P is 1, then P is the first index in the array and is equal to 3
Example solution
function solution(A) {
var sumAfter = 0;
var sumBefore = 0;
//sets the number to positive
var minDiff = Number.POSITIVE_INFINITY;
//add up the numbers in the array
A.forEach(function(value) {
sumAfter += value;
});
for(var i = 1; i < A.length; i++) {
sumBefore += A[i - 1];
sumAfter = sumAfter - A[i - 1];
minDiffTemp = Math.abs(sumBefore - sumAfter);
if(minDiffTemp < minDiff) {
minDiff = minDiffTemp;
}
}
return minDiff;
}
####FrogJmp
function solution(X, Y, D) {
return Math.ceil((Y - X)/ D);
}
####PermMissingElem
function solution(A) {
aSum = (A.length + 2) * ((A.length +1) / 2);
missing = 0;
for(i=0;i<A.length; i++) {
missing += A[i];
}
return aSum - missing;
}
###Counting Elements ####FrogRiverOne
function solution(X, A) {
var count = {};
var countI = 0;
var index = 0;
for(var i = 0; i < A.length; i++) {
index = A[i] -1;
if(A[i] <= X && !count[index]) {
count[index] = true;
countI++;
if(countI === X) return i;
}
}
return -1;
}
####PermCheck
function solution(A) {
var sum = 0;
var numbers = {};
for(var i = 0; i < A.length; i++) {
var a = A[i];
sum += a;
if(numbers[a] === 1) {
return 0;
} else {
numbers[a] = 1;
}
}
var n = A.length;
var sum_n = (n * (n + 1)) / 2;
var difference = sum_n - sum;
if(difference !== 0) return 0;
return 1;
}
####MissingInteger
function solution(A) {
var count = [];
for(var i = 0; i<A.length; i++) {
if(A[i] > 0) {count[A[i]] = true;}
}
for(i = 1; i <= count.length; i++) {
if(!count[i]) {return i;}
}
return 1;
}
####MaxCounters time complexity: O(N + M)
// N number of counters
// function increase(X) increases a counter by 1
// function max_counter all counters are set to maximum value of one counter
// A is a 0 indexted array
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(N, A) {
//set len to array length
var len = A.length;
//set lastBase to 0
var lastBase = 0;
//set max to 0
var max = 0;
//make an empty array for counters
var counters = [];
//n1 is the number or counters plus 1
var n1 = N+1;
//set i to 0 and increment i by 1 untill it's 1 less than the number of counters
for(var i = 0; i < N; i++){
//counters array looks like counters[0] = 0 at the beginning
counters[i] = 0;
}
//set i back to 0, increment i by 1 untill it's 1 less than the array length
for(i = 0; i < len; i++){
//if Array at index i is less than the number of counters +1
if(A[i] < n1){
//if counters array index at Array index i -1 is less than lastBase(which starts at 0)
if(counters[A[i]-1] < lastBase) {
//counters array index is set to the value of lastBase
counters[A[i]-1] = lastBase;
}
//if counters array index is greater than lastBase value, counters array index is incremented by 1
counters[A[i]-1] += 1;
//if max is less than the counters array index
if(max < counters[A[i]-1]) {
//max is set to the value of the counters array index
max = counters[A[i]-1];
}
} else {
//if Array at index i is greater than the number of counters +1 lastBase is set to the value of max
lastBase = max;
}
}
//i is set to 0 and incremented by one untill i is equal to the number of counters
for(i = 0; i < N; i++){
//if counters index is less than lastBase
if(counters[i] < lastBase) {
//counters indext is set to the value of lastBase
counters[i] = lastBase;
}
}
return counters;
}
####Find Digits
input:
2
12
1012
expected output:
2
3
solution
function processData(input) {
var a = input.split('\n'); // returns ['2', '12', '1012']
var b = a.map(Number); // returns [2, 12, 1012]
}