Sqrt(x)
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
If x >= 2, 0< sqrt(x) <x/2
So use binary search by considering all possible values from 0 to x/2 as the starting search space
use long to store square as x can take full range of integer values so the square may not fit in int
if (x < 2) return x;
int left=2, right = x/2;
while(left <= right) {
int mid = left + (right-left)/2;
long square = (long)mid*mid;
if (square > x) {
right = mid-1;
} else if (square < x) {
left = mid + 1;
} else {
return mid;
}
}
return right;
}Koko eating bananas
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Use binary search. 1 to maximum of piles[i], do a search in this range.
If koko eats at a rate, then time needed to eat all bananas:
sum(piles)/rate rounded up to nearest integer.
int right=0, left=1;
for(int pile: piles) {
right = Math.max(pile, right);
}
while(left < right) {
int middle = left + (right-left)/2;
int timeSpent = 0;
for(int pile: piles) {
timeSpent += Math.ceil((double)pile/middle);
}
//is timeSpent a workable speed?
if (timeSpent <= h) {
right = middle;
} else {
left = middle+1;
}
}
return right;Find floor of a target in a given array:
floor = largest value <= target
int left=0, right = array.length-1
Integer result = null;
while(left <= right) {
int middle = left + (right-left)/2;
if (array[middle] <= target) {
left = middle+1;
result = array[middle];
} else {
right = middle-1;
}
}
return result;
Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e., x^n) without using library functions
Input: x = 2.00000, n = 10
Output: 1024.00000
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Use binary exponentiation. Not even Krishna knows why.
Call this by converting the number n into a long:
private double binaryExp(double x, long n) {
if (n == 0) {
return 1;
}
// Handle case where, n < 0.
if (n < 0) {
n = -1 * n;
x = 1.0 / x;
}
// Perform Binary Exponentiation.
double result = 1;
while (n != 0) {
// If 'n' is odd we multiply result with 'x' and reduce 'n' by '1'.
if (n % 2 == 1) {
result = result * x;
n -= 1;
}
// We square 'x' and reduce 'n' by half, x^n => (x^2)^(n/2).
x = x * x;
n = n / 2;
}
return result;
}Median of sorted arrays
Avoid merging, will be slow O(M + N). Instead use binary search
Partition both arrays so that the left half contains exactly half elements (duh) and then every element in left <= every element in the right
Just ensure first array (A) is the smaller array
Let’s partition in this way:
A = [ (left of A) | partitionA | (right of A ]
B = [ (left of B) | partitionB | (right of B ]
if (nums1.length > nums2.length)
return findMedianSortedArrays(nums2, nums1);
int length1 = nums1.length;
int length2 = nums2.length;
//binary search on A to find the partition
int low = 0, high = length1;
while(low <= high) {
int partitionA = low + (high-low)/2;
//corresponding partition in B
int partitionB = (length1 + length2 + 1)/2 - partitionA;
int maxLeftA = (partitionA == 0) ? Integer.MIN_VALUE : nums1[partitionA-1];
int minRightA = (partitionA == length1) ? Integer.MAX_VALUE : nums1[partitionA];
int maxLeftB = (partitionB == 0) ? Integer.MIN_VALUE : nums2[partitionB-1];
int minRightB = (partitionB == length2) ? Integer.MAX_VALUE : nums2[partitionB];
//is partition is valid?
if(maxLeftA <= minRightB && maxLeftB <= minRightA) {
//if total length is even
if ((length1 + length2)%2 == 0) {
//average of two middle values
return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightB, minRightA))/2.0;
} else {
return Math.max(maxLeftA, maxLeftB);
}
}
if (maxLeftA > minRightB) {
//move search left since we need to move some elements in left partition to the right
high = partitionA - 1;
} else {
//move search right as we need to put some elements in right partition to the left
low = partitionA + 1;
}
}
return -1;
