Tricky java programs
Reverse a String without Using Built-In Functions
• Reverse a string without using StringBuilder or StringBuffer reverse methods
public class ReverseString {
public static void main(String[] args) {
String input = "Java Programming";
char[] chars = [Link]();
for (int i = 0; i < [Link] / 2; i++) {
char temp = chars[i];
chars[i] = chars[[Link] - i - 1];
chars[[Link] - i - 1] = temp;
}
[Link]("Reversed String: " + new String(chars));
}
}
Explanation:
The idea is to convert the string to a character array
(toCharArray()), then use a simple loop to swap the
characters from the beginning and the end,
progressively moving toward the center.
This avoids using built-in reverse functions like
[Link]().
•
Find the Missing Number in an Array
Given an array containing n-1 distinct numbers from 1 to n, find the missing number.
public class MissingNumber {
public static void main(String[] args) {
int[] arr = {1, 2, 4, 5, 6};
int n = 6;
int totalSum = n * (n + 1) / 2;
int arraySum = 0;
for (int num : arr) {
arraySum += num;
}
int missingNumber = totalSum - arraySum;
[Link]("Missing number is: " + missingNumber);
}
}
Explanation:
We can use the formula for the sum of the first n
natural numbers: n*(n+1)/2.
We subtract the sum of the array from the
expected sum. The difference will be the missing
number.
This solution runs in O(n) time complexity.
Fibonacci Series Using Recursion
• Print the Fibonacci series up to n terms using recursion.
public class Fibonacci {
public static void main(String[] args) {
int n = 10;
for (int i = 0; i < n; i++) {
[Link](fib(i) + " ");
}
}
public static int fib(int n) {
if (n <= 1) {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}
}
Explanation:
The Fibonacci sequence is calculated recursively. Each number is the sum
of the previous two numbers.
The base cases are fib(0) = 0 and fib(1) = 1.
While this approach is simple, it is inefficient because of repeated
calculations for the same values, leading to an exponential time
complexity (O(2^n)).
Find the Largest Palindrome in a String
• Find the largest palindrome substring in a given string.
• Pblic class LargestPalindrome {
• public static void main(String[] args) {
• String str = "babad";
• [Link]("Largest Palindrome Substring: " + longestPalindrome(str));
• }
• pulic static String longestPalindrome(String s) {
• if (s == null || [Link]() < 1) return "";
• String longest = "";
• for (int i = 0; i < [Link](); i++) {
• String oddPalindrome = expandAroundCenter(s, i, i);
• String evenPalindrome = expandAroundCenter(s, i, i + 1);
• if ([Link]() > [Link]()) {
• longest = oddPalindrome;
• }
• if ([Link]() > [Link]()) {
• longest = evenPalindrome;
• }
• }
• return longest;
• }
• private static String expandAroundCenter(String s, int left, int right) {
• while (left >= 0 && right < [Link]() && [Link](left) == [Link](right)) {
• left--;
• right++;
• }
• return [Link](left + 1, right);
Explanation
• This solution checks every possible palindrome by expanding around each center (both odd and even
lengths).
• For each center (either one character or two characters), we expand outward as long as we find matching
characters.
• The time complexity is O(n^2).
Program: Find the Maximum Subarray Sum
public class MaxSubarraySum {
public static void main(String[] args) {
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSum = findMaxSubarraySum(nums);
[Link]("Maximum subarray sum: " + maxSum);
}
public static int findMaxSubarraySum(int[] nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < [Link]; i++) {
currentSum = [Link](nums[i], currentSum + nums[i]);
maxSum = [Link](maxSum, currentSum);
}
return maxSum;
}
}
maxSum: This variable stores the maximum sum of the subarray found so far.
currentSum: This keeps track of the sum of the current subarray we're considering.
• Initially, both maxSum and currentSum are set to the first element of the array, because that is the smallest possible subarray.
• Iterating through the array:
for (int i = 1; i < [Link]; i++) {
currentSum = [Link](nums[i], currentSum + nums[i]);
maxSum = [Link](maxSum, currentSum);
• The loop starts from the second element (i = 1) and goes to the end of the array.
• currentSum = [Link](nums[i], currentSum + nums[i]):
This line decides whether to start a new subarray at index i (i.e., just use nums[i]) or to extend the current subarray by adding
nums[i] to the currentSum.
If the value of currentSum + nums[i] is less than nums[i], it's better to start a new subarray, so currentSum is updated to nums[i].
• maxSum = [Link](maxSum, currentSum):
• After updating currentSum, we check if it's greater than maxSum. If it is, we update maxSum to store the new maximum
Return the result
return maxSum;
• Once the loop is complete, maxSum contains the largest sum of any
contiguous subarray found during the iteration, which is the final
result.
• Example (using the array {-2, 1, -3, 4, -1, 2, 1, -5, 4}):
Start with maxSum = -2 and currentSum = -2 (first element).
Iterate through the array:
o At index 1: currentSum = [Link](1, -2 + 1) = 1, maxSum = [Link](-2, 1) = 1.
o At index 2: currentSum = [Link](-3, 1 + -3) = -2, maxSum = [Link](1, -2) = 1.
o At index 3: currentSum = [Link](4, -2 + 4) = 4, maxSum = [Link](1, 4) = 4.
o At index 4: currentSum = [Link](-1, 4 + -1) = 3, maxSum = [Link](4, 3) = 4.
o At index 5: currentSum = [Link](2, 3 + 2) = 5, maxSum = [Link](4, 5) = 5.
o At index 6: currentSum = [Link](1, 5 + 1) = 6, maxSum = [Link](5, 6) = 6.
o At index 7: currentSum = [Link](-5, 6 + -5) = 1, maxSum = [Link](6, 1) = 6.
o At index 8: currentSum = [Link](4, 1 + 4) = 5, maxSum = [Link](6, 5) = 6.
Final result: maxSum = 6 (the maximum subarray sum).
