Problem Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. You must write an algorithm with O(log n) runtime complexity. Examples Example 1: Input: nums = [1,3,5,6], target = 5 Output: 2 ...
Problem Implement pow(x, n) % d. In other words, given x, n and d, find (x^n % d) Note that remainders on division cannot be negative. In other words, make sure the answer you return is non negative. Examples Example 1: Input: x = 2, n = 3, d = 3 Output: 2 Explanation: 2^3 % 3 = 8 % 3 = 2. ...
This is a follow up on H-Index Problem. What if the citations array is sorted in ascending order? Could you optimize your algorithm? Problem Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in an ascending order, return compute the researcher’s h-index. According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each. ...
Problem Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return compute the researcher’s h-index. According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each. If there are several possible values for h, the maximum one is taken as the h-index. ...
Problem There are two sorted arrays nums1 and nums2 of size n. Find the median of the two sorted arrays. You may assume nums1 and nums2 cannot be both empty. OR There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)) Median Definition Median Definition ...
Problem Given a sorted array and an element, find last occurrence of element in array. Examples Example 1: Input: a = [1, 4, 4, 10, 10, 15, 20], target = 10 Output: 4 This problem is similar to Find first position of target element in sorted array. Solution A brute force solution involves scanning the entire array and comparing each A[index] with the key. If A[index] is equal to the key and the next element is different, return the index. The worst-case time complexity of this method is ( O(N) ). Can we improve this? And the answer is yes, using Binary Search on Sorted Array. ...
Problem Given a sorted array of integers and a target element. Find the number of occurrences of the target in the array. You must write an algorithm with O(log n) runtime complexity. Examples Example 1: Input: nums = [1, 1, 2, 2, 2, 2, 3], target = 2 Output: 4 Explanation: 2 appears four times in the array ...