Plus One Problem:
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit
of the integer. The digits are ordered from most significant to least significant in left-to-right order.
The large integer does not contain any leading 0's.
Increment the large integer by one and return the resulting array of digits.
Example 1:
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].
Example 2:
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].
Example 3:
Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].
Constraints:
1 <= [Link] <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0's.
Solution:
class Solution {
public int[] plusOne(int[] digits) {
for (int i = [Link] - 1; i >= 0; i--) {
if (digits[i] < 9) {
++digits[i];
return digits;
digits[i] = 0;
int[] ans = new int[[Link] + 1];
ans[0] = 1;
return ans;
}
Question 2:
You may recall that an array arr is a mountain array if and only if:
[Link] >= 3
There exists some index i (0-indexed) with 0 < i < [Link] - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[[Link] - 1]
Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if
there is no mountain subarray.
Example 1:
Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.
Example 2:
Input: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.
Constraints:
1 <= [Link] <= 104
0 <= arr[i] <= 104
Solution:
class Solution {
public int longestMountain(int[] arr) {
int ans = 0;
for (int i = 0; i + 1 < [Link];) {
while (i + 1 < [Link] && arr[i] == arr[i + 1])
++i;
int increasing = 0;
int decreasing = 0;
while (i + 1 < [Link] && arr[i] < arr[i + 1]) {
++increasing;
++i;
while (i + 1 < [Link] && arr[i] > arr[i + 1]) {
++decreasing;
++i;
if (increasing > 0 && decreasing > 0)
ans = [Link](ans, increasing + decreasing + 1);
return ans;
}
Question 3: Perfect Square or not
Given a positive integer num, return true if num is a perfect square or false otherwise.
A perfect square is an integer that is the square of an integer. In other words, it is the product of
some integer with itself.
You must not use any built-in library function, such as sqrt.
Example 1:
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
Example 2:
Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.
Constraints:
1 <= num <= 231 – 1
Solution:
class Solution {
// Method to check if a given number is a perfect square
public boolean isPerfectSquare(int num) {
long left = 1; // Set the lower bound of the search range
long right = num; // Set the upper bound of the search range
// Binary search to find the square root of num
while (left < right) {
// Calculate the midpoint to avoid overflow
long mid = (left + right) >>> 1;
// If mid squared is greater than or equal to num, it could be the root
if (mid * mid >= num) {
right = mid; // Adjust the upper bound for the next iteration
} else {
left = mid + 1; // Adjust the lower bound if mid squared is less than num
// Check if the final left value squared equals the original number to confirm if it's a perfect
square
return left * left == num;
Question 4:
Given two integers dividend and divisor, divide two integers without using multiplication, division,
and mod operator.
The integer division should truncate toward zero, which means losing its fractional part. For
example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.
Return the quotient after dividing dividend by divisor.
Note: Assume we are dealing with an environment that could only store integers within the 32-
bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 -
1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.
Constraints:
-231 <= dividend, divisor <= 231 - 1
divisor != 0
Solution:
class Solution {
public int divide(int dividend, int divisor) {
// Determine the sign of the result
int sign = 1;
if ((dividend < 0) != (divisor < 0)) {
sign = -1;
}
// Use long to avoid integer overflow issues
long longDividend = [Link]((long) dividend);
long longDivisor = [Link]((long) divisor);
// This will accumulate the result of the division
long total = 0;
// Loop to find how many times the divisor can be subtracted from
the dividend
while (longDividend >= longDivisor) {
// This counter will keep track of the number of left shifts
int count = 0;
// Double the divisor until it is less than or equal to the
dividend
while (longDividend >= (longDivisor << (count + 1))) {
count++;
}
// Add the number of times we could double the divisor to the
total
total += 1L << count;
// Subtract the final doubled divisor value from the dividend
longDividend -= longDivisor << count;
}
// Multiply the sign back into the total
long result = sign * total;
// Handle overflow cases by clamping to the Integer range
if (result >= Integer.MIN_VALUE && result <= Integer.MAX_VALUE) {
return (int) result;
}
// If the result is still outside the range, return the max
integer value
return Integer.MAX_VALUE;
}
}
Question 5:
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing
a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit,
return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you
sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= [Link] <= 105
0 <= prices[i] <= 104
Solution:
class Solution {
public int maxProfit(int[] prices) {
// Initialize 'maxProfit' to 0, which is the minimum profit that can be made.
int maxProfit = 0;
// Assume the first price is the minimum buying price.
int minPrice = prices[0];
// Loop through all the prices to find the maximum profit.
for (int price : prices) {
// Calculate the maximum profit by comparing the current 'maxProfit'
// with the difference of the current price and the 'minPrice'.
maxProfit = [Link](maxProfit, price - minPrice);
// Update the 'minPrice' if a lower price is found.
minPrice = [Link](minPrice, price);
// Return the maximum profit that can be achieved.
return maxProfit;
Question 6:
Given a string n representing an integer, return the closest integer (not including itself), which is a
palindrome. If there is a tie, return the smaller one.
The closest is defined as the absolute difference minimized between two integers.
Example 1:
Input: n = "123"
Output: "121"
Example 2:
Input: n = "1"
Output: "0"
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.
Constraints:
1 <= [Link] <= 18
n consists of only digits.
n does not have leading zeros.
n is representing an integer in the range [1, 1018 - 1].
Solution:
class Solution {
// Function to find the nearest palindromic number in string form
public String nearestPalindromic(String n) {
// Convert the input string to a long integer for comparison
long number = [Link](n);
// Variable to store the closest palindrome number
long closestPalindrome = -1;
// Get all potential palindrome candidates
for (long candidate : getPalindromeCandidates(n)) {
// If this is the first candidate or it's closer to the input number than the current closest
// or equally close but smaller, then update the closest palindrome
if (closestPalindrome == -1 ||
[Link](candidate - number) < [Link](closestPalindrome - number) ||
([Link](candidate - number) == [Link](closestPalindrome - number) && candidate <
closestPalindrome)) {
closestPalindrome = candidate;
// Convert the closest palindrome back to a string and return it
return [Link](closestPalindrome);
// Helper function to generate palindrome candidates based on the input string
private Set<Long> getPalindromeCandidates(String n) {
int length = [Link](); // Length of the input number
Set<Long> candidates = new HashSet<>(); // Set to store palindrome candidates
// Add 9's (One less digit than n and all 9's) e.g. 999 for n=1000
[Link]((long)[Link](10, length - 1) - 1);
// Add 1 followed by all zeros and then a 1 (One more digit than n) e.g. 10001 for n=999
[Link]((long)[Link](10, length) + 1);
// Get the first half of n (if odd, include the middle digit)
long firstHalf = [Link]([Link](0, (length + 1) / 2));
// Generate candidates by varying the first half from -1 to 1 and mirroring to get palindromes
for (long i = firstHalf - 1; i <= firstHalf + 1; ++i) {
StringBuilder candidateBuilder = new StringBuilder();
[Link](i); // Append the first half
// Mirror and append the reverse of the first half (excluding the middle digit if odd length)
[Link](new StringBuilder([Link](i)).reverse().substring(length %
2));
// Add the generated number to candidates
[Link]([Link]([Link]()));
// Remove the number itself if it's a palindrome, as we want the nearest different palindrome
[Link]([Link](n));
return candidates; // Return the set of candidates
}
}