You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once. Example 1: Input: [1,1,2,3,3,4,4,8,8] Output: 2 Example 2: Input: [3,3,7,7,10,11,11] Output: 10 Note: Your solution should run in O(log n) time and O(1) space. Solution Java class Solution { public int singleNonDuplicate(int[] nums) { int left = 0, right = nums.
Given an int array wood representing the length of n pieces of wood and an int k. It is required to cut these pieces of wood such that more or equal to k pieces of the same length len are cut. What is the longest len you can get? Example 1 Input: wood = [5, 9, 7], k = 3 Output: 5 Explanation: 5 -> 5 9 -> 5 + 4 7 -> 5 + 2 Example 2 Input: wood = [5, 9, 7], k = 4 Output: 4 Explanation: 5 -> 4 + 1 9 -> 4 * 2 + 1 7 -> 4 + 3 Example 3 Input: wood = [1, 2, 3], k = 7 Output: 0 Explanation: We cannot make it.
Given 2 lists a and b. Each element is a pair of integers where the first integer represents the unique id and the second integer represents a value. Your task is to find an element from a and an element form b such that the sum of their values is less or equal to target and as close to target as possible. Return a list of ids of selected elements. If no pair is possible, return an empty list.
(This problem is an interactive problem.) You may recall that an array A is a mountain array if and only if: A.length >= 3 There exists some i with 0 < i < A.length - 1 such that: A[0] < A[1] < ... A[i-1] < A[i] A[i] > A[i+1] > ... > A[A.length - 1] Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target.
Let’s call an array A a mountain if the following properties hold: A.length >= 3 There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.
Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c. Example 1 Input: 5 Output: True Explanation: 1 * 1 + 2 * 2 = 5 Example 2 Input: 3 Output: False Solution import math class Solution: def judgeSquareSum(self, c: int) -> bool: if c <= 1: return True sqrt = math.ceil(math.sqrt(c)) left, right = 0, sqrt-1 while left*left + right*right < c: if (left+1)*(left+1) + right*right > c: right -= 1 else: left += 1 if left*left + right*right == c: return True return False Without sqrt function
Given a positive integer num, write a function which returns True if num is a perfect square else False. Note Do not use any built-in library function such as sqrt. Example 1 Input: 16 Output: true Example 2 Input: 14 Output: false Solution (naive) Java class Solution { public boolean isPerfectSquare(int num) { if (num == 1) return true; for (int i = 2; i < num; i++) { if (i * i == num) { return true; } if (i * i > num) { break; } } return false; } } Solution (Binary Search version 1) Let x be the square root, 1 < x < num/2 always holds true.
We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked. Every time you guess wrong, I’ll tell you whether the number is higher or lower. You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0): -1 : My number is lower 1 : My number is higher 0 : Congrats!
You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximum number of envelopes can you Russian doll? (put one inside other) Note Rotation is not allowed. Example: Input: [[5,4],[6,4],[6,7],[2,3]] Output: 3 Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. Example: Consider the following matrix: [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] Given target = 5, return true.