Binary Search
Nth root of an integer
❓: You are given two positive integers 'n' and 'm'. You have to return the 'nth' root of 'm', i.e. 'm(1/n)'. If the 'nth root is not an integer, return -1.
Example:
3 27
Output: 3
Explanation For Sample Input 1: 3rd Root of 27 is 3, as (3)^3 equals 27.
def NthRoot(n: int, m: int) -> int:
low, high = 0, m
while low <= high:
mid = (low + high) // 2
curr = mid**n
if curr == m:
return mid
elif curr < m:
low = mid + 1
else:
high = mid - 1
return -1
fn nth_root(n: i32, m: i32) -> i32 {
let (mut low, mut high) = (0, m);
while low <= high {
let mid = (low + high) / 2;
let curr = mid.pow(n as u32);
if curr == m {
return mid;
} else if curr < m {
low = mid + 1;
} else {
high = mid - 1;
}
}
-1
}
fn main() {
assert_eq!(nth_root(3, 27), 3);
assert_eq!(nth_root(4, 69), -1);
}
Matrix Median
Coming Soon
Single Element in a Sorted Array
❓: You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.
Return the single element that appears only once.
Example:
Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
🧠:
Elements which are repeated twice will be at
1. odd, even indices to left of target
2. even, odd indices to right of target
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
if nums[0] != nums[1]:
return nums[0]
if nums[-1] != nums[-2]:
return nums[-1]
low, high = 1, n - 2
while low <= high:
mid = (low + high) // 2
if nums[mid - 1] != nums[mid] != nums[mid + 1]:
return nums[mid]
elif nums[mid] == nums[mid - 1]:
if mid % 2:
low = mid + 1
else:
high = mid - 1
else:
if mid % 2:
high = mid - 1
else:
low = mid + 1
impl Solution {
pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
let n = nums.len();
if n == 1 || nums[0] != nums[1] {
return nums[0];
}
if nums[n - 1] != nums[n - 2] {
return nums[n - 1];
}
let (mut low, mut high) = (1, n - 2);
while low <= high {
let mid = (low + high) / 2;
if nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1] {
return nums[mid];
} else if nums[mid] != nums[mid - 1] {
if mid % 2 == 1 {
high = mid - 1;
} else {
low = mid + 1;
}
} else {
if mid % 2 == 1 {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
1
}
}
Search in Rotated Sorted Array
❓: There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
Example:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
🧠:
1. On doing binary search, atleast one of left or right half will be sorted.
2. Eliminate one of them using that property.
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
low, high = 0, n - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[low] <= nums[mid]:
if nums[low] <= target < nums[mid]:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] < target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return -1
impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
let n = nums.len();
let (mut low, mut high) = (0, n - 1);
while low <= high {
let mid = (low + high) / 2;
if nums[mid] == target {
return mid as i32;
} else if nums[low] <= nums[mid] {
if nums[low] <= target && target < nums[mid] {
high = mid - 1
} else {
low = mid + 1
}
} else {
if nums[mid] < target && target <= nums[high] {
low = mid + 1
} else {
high = mid - 1
}
}
}
-1
}
}
Median of 2 Sorted Arrays
Coming Soon
Kth Element of 2 Sorted Arrays
Coming Soon
Allocate Minimum Number of Pages
Coming Soon
Agressive Cows
❓: Given an array nums of size n, which denotes the positions of stalls, and an integer k, which denotes the number of aggressive cows, assign stalls to k cows such that the minimum distance between any two cows is the maximum possible. Find the maximum possible minimum distance.
Example:
Input: n = 6, k = 4, nums = [0, 3, 4, 7, 10, 9]
Output: 3
Explanation: The maximum possible minimum distance between any two cows will be 3 when 4 cows are placed at positions [0, 3, 7, 10]. Here the distances between cows are 3, 4, and 3 respectively. We cannot make the minimum distance greater than 3 in any ways.
🧠:
1. Minimum possible way is 1 and maximum is max(arr) - min(arr).
2. Linear search approach would be trying all the values in range till we find maximum result.
3. Binary search approach is going to mid element and check whether it is possible or not.
4. If it is possible, as we need max value, eliminate left half to find better answer in right half.
5. Else, eliminate right half to find answer in left half.
class Solution:
def aggressiveCows(self, nums, k):
self.nums = sorted(nums)
self.k = k
self.n = len(nums)
self.res = 0
self.helper()
return self.res
def helper(self):
low, high = 0, self.nums[-1] - self.nums[0]
while low <= high:
mid = (low + high) // 2
if self._is_possible(mid):
self.res = max(self.res, mid)
low = mid + 1
else:
high = mid - 1
def _is_possible(self, d):
prev = 0
count = self.k - 1
for i in range(1, self.n):
if self.nums[i] - self.nums[prev] >= d:
prev = i
count -= 1
if not count:
return True
return not count