In this article, we'll dive deeper into arrays, covering:
Resizing Arrays: Learn how to dynamically resize arrays to accommodate changing data.
Problem 1: Finding the Missing Number: Given an array of distinct numbers from 1 to n-1, find the missing number.
Problem 2: Palindrome Check: Check if a given string is a palindrome or not.
Stay tuned for detailed explanations, code solutions, and screenshots to help you grasp these concepts better! 📚💻
Learn how to resize() method workings internally
public class ResizeArray {
public void printArray(int[] arr) {
int n = arr.length;
for(int i =0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void resize(int[] arr, int capacity) {
int[] temp = new int[capacity];
for(int i = 0; i < arr.length ; i++) {
temp[i] = arr[i];
}
arr = temp;
}
public static void main(String[] args) {
int[] myArr = {5,1,7,6,9,};
System.out.println("The size of original array - " +myArr.length);
resize(myArr, 10);
System.out.println("The size of original array after rezise -" +myArr.length);
}
}
Below is the Screenshot of resizing the array, with void as return type.
Even after printing the size of array, the size of array remains the same. So to get ride of this small mistake. We have to change the return type of this method to array.
public class ResizeArray {
public void printArray(int[] arr) {
int n = arr.length;
for(int i =0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static int[] resize(int[] arr, int capacity) {
int[] temp = new int[capacity];
for(int i = 0; i < arr.length ; i++) {
temp[i] = arr[i];
}
/*
* arr = temp; return arr;
*/
return temp;
}
public static void main(String[] args) {
int[] myArr = {5,1,7,6,9,};
System.out.println("The size of original array - " +myArr.length);
myArr = resize(myArr, 10);
System.out.println("The size of original array after rezise -" +myArr.length);
}
}
After changing the return type below is the output. The capacity of the array changes.
Let's delve into the issues because practice is crucial. You must have hands-on experience along with theoretical knowledge. I've recently come to realize this, so I encourage you guys to engage in logic-building activities and problem-solving. I want you to understand where and how we will apply this in real-time scenarios.
Problem: Given an array of length n-1 containing unique numbers in the range of 1 to n, find the missing number within it.
Note: arr.length provides the actual number of elements in the array, not n-1 elements if the array comprises n elements. In Java, the array index ranges from '0' to 'length-1'.
Input: (i)array length is 4; but n=5 {1,3,4,5}
(ii)array length is 7 ; but n = 8 {1,3,4,5,8,2,7}
Output: (i)Missing number = 2
(ii)Missing number = 6
Hint: The mathematical approach to this problem is as follows: The sum of the first 'n' natural numbers is calculated by the formula 1+2+3+....+n = n x(n+1)/2.
Pseudo Code: Using the mathematical formula. Let's consider n=5, then
(5 x (5+1))/2
\=>(5 x 6)/2
\=>30/2 = 15
Now, sum up the elements from the range 1 to 5 = 1+ 2+ 3+ 4+ 5 = 15
Create a variable for the above mathematical approach and calculate the sum of the first
nnatural numbers in thetotalvariable with(arr.length + 1).Use a temporary variable
tempto store the sum of all the elements in the array.Initialize the temp variable with zero
0(i.e.temp = 0).Iterate through the entire loop, add each element of the array, and assign it to temp.
Finally, return the subtraction value of
total - temp.
public class FindmissingElement {
public static int missingElement(int[] arr) {
int n = arr.length+1;
int total = (n*(n+1))/2;
int temp =0;
for(int i =0; i< arr.length; i++) {
temp = temp + arr[i];
}
return total-temp;
}
public static void main(String[] args) {
int[] myArr = {1,3,4,5,8,2,7};
int result = missingElement(myArr);
System.out.println("Missing number = "+ result);
}
}
Below is the output of the FindmissingElement problem.
Let's see the other data types of array like String and do some problem solving.
Problem: Given a string , the task is to check whether given string is Palindrome or not.
Input: (i) Str = ' madam' || 'mom' || 'dad
(ii) Str = 'that' || 'java'
Output:(i) True
(ii) False
Hint: It's easy if you go with Two pointer approach, as we did in the last article. While doing this as input is string convert it into the Character array using this .toCharArray() method
Pseudo Code:
First change the given string into the Character Array with
.toCharArray()method and store it into an Array.Initialize two variables as
startandendwith zeroth index of array and last index of the array respectively.Iterate through the entire loop until this two variables overlap each other.(i.e.
start < endif odd elements are there then middle element will be left and if it's even then each and every element will be check there is no need to check<=)Check the
startof the array is not equal toendindex of the array and return False as they are not palindrome.If those index of the array are same then Increment the start and decrement the end to check the next elements in the array.
Finally, if
endandstartoverlap till then statement number 4 is False. Return True stating that the given string is Palindrome.
public class PalindromeorNot {
public static boolean isPalindromeorNot(String word) {
//word.toLowerCase()
char[] charArr = word.toCharArray();
int start = 0;
int end = word.length()-1;
while(start < end) {
if(charArr[start] != charArr[end]) {
return false;
}
start++;
end--;
} return true;
}
public static void main(String[] args) {
String Word = "madam";
//String Word = "Madam"; even this will return false as 'M' != 'm' . Either you have to change it into lowercase/uppercase all the characters in the string or accept that
if(isPalindromeorNot(Word)) {
System.out.println("Given String is Palindrome :" +Word);
}else {
System.out.println("Given String is not a Palindrome :" +Word);
}
}
}
So, buckle up, dear reader, as we embark on this adventure together. Let's unravel the mysteries of data structures and algorithms, one concept at a time.
Until next time, happy coding! 🚀