Posted in

ARRAYS PROGRAMS AND ALGORITHMS IN JAVA

by admin••0•Posted inJAVA

1. Write a program to find the maximum and minimum element in an array of integers?

Algorithm :

  • Start
  • Initialize an integer array arr with some values
  • Set max = arr[0] and min = arr[0] (assume first element is both max and min)
  • Loop through the array from index 1 to arr.length – 1:
    • If arr[i] > max, update max = arr[i]
    • If arr[i] < min, update min = arr[i]
  •  After the loop ends, print:
    • “Maximum element: ” followed by max
    • “Minimum element: ” followed by min
  • End

Program :

   public class MaxMinArray {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 7, 3};
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i]; 
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        System.out.println(“Maximum element: ” + max);
        System.out.println(“Minimum element: ” + min);
    }
}

Output :

Maximum element: 9
Minimum element: 1

Explanation :

This program finds the maximum and minimum values in a given array. It initializes both max and min with the first element of the array. Then, it iterates through the rest of the array, comparing each element to update max or min accordingly. This single-pass solution is efficient and avoids sorting. In the end, it displays the highest and lowest values in the array.

2. Write a program to reverse an array in-place without using a secondary array?

Algorithm :

  • Start
  • Initialize an integer array arr = {5, 2, 9, 1, 7, 3}
  • Call the method reverseArray(arr)
  • Inside reverseArray method:
    • Set start = 0, end = arr.length – 1
    • While start < end, do the following:
      • Store arr[start] in temp
      • Set arr[start] = arr[end]
      • Set arr[end] = temp
      • Increment start by 1
      • Decrement end by 1
  • Return to main method
  • Print the reversed array using enhanced for loop
  • End

Program :

public class ReverseArray {
      public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 7, 3};
        reverseArray(arr);
        System.out.print(“Reversed Array: “);
        for (int i : arr) {
            System.out.print(i + ” “);
        }
    }
    public static void reverseArray(int[] arr) {
        int start = 0;
        int end = arr.length – 1;
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end–;
        }
    }
}

Output :

Reversed Array: 3 7 1 9 2 5

Explanation :

This program reverses the elements of an array in-place (i.e., without using extra space). It uses two pointers: one starting from the beginning (start) and the other from the end (end). These pointers swap the elements at their respective positions and move towards the center until they meet. This method is efficient (O(n) time complexity) and modifies the original array directly. Finally, the program prints the reversed array.

3. Write a program to how do you rotate an array in Java?

Algorithm :

  • Start
  • Initialize an integer array arr = {1, 2, 3, 4, 5, 6} and k = 2
  • Call rotateRight(arr, k)
  • Inside rotateRight(arr, k):
  • Get the length of the array: n = arr.length
  • Compute effective rotation: k = k % n → handles k > n
  • Reverse the entire array from index 0 to n-1:
    • arr becomes {6, 5, 4, 3, 2, 1}
  • Reverse the first k elements (index 0 to k-1):
    • arr becomes {5, 6, 4, 3, 2, 1}
  • Reverse the remaining n-k elements (index k to n-1):
    • arr becomes {5, 6, 1, 2, 3, 4}
  • Return to main method
  • Print the rotated array: 5 6 1 2 3 4
  • End

Program :

public class RotateArray {
      public static void main(String[] args) {
          int[] arr = {1, 2, 3, 4, 5, 6};
        int k = 2;  // Number of positions to rotate
        rotateRight(arr, k);
        System.out.print(“Rotated Array: “);
        for (int num : arr) {
            System.out.print(num + ” “);
        }
    }
    public static void rotateRight(int[] arr, int k) {
        int n = arr.length;
        k = k % n; 
        reverseArray(arr, 0, n – 1);
        reverseArray(arr, 0, k – 1);
        reverseArray(arr, k, n – 1);
    }
    public static void reverseArray(int[] arr, int start, int end) {
        while (start < end) {
            // Swap arr[start] and arr[end]
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end–;
        }
    }
}

Output (for input array {1, 2, 3, 4, 5, 6} and k = 2):

Rotated Array: 5 6 1 2 3 4

Explanation :

        This program rotates an array to the right by k positions using an efficient 3-step reverse method. First, it reverses the entire array, then reverses the first k elements, and finally the remaining n – k elements. This approach avoids the need for extra space and runs in O(n) time. The net effect is a right shift of all elements by k positions.

4. Write a program to check if a given array is sorted in non-decreasing order?

Algorithm :

  • Start
  • Initialize the array: arr = {1, 2, 2, 3, 4, 5}
  • Call the method isSorted(arr)
  • Inside isSorted method:
    • Loop from i = 1 to arr.length – 1:
      • If arr[i] < arr[i – 1], return false (array is not sorted)
    • If loop finishes without returning false, return true
  • Back in main:
    • If isSorted() returns true, print “The array is sorted in non-decreasing order.”
    • Else, print “The array is not sorted in non-decreasing order.”
  • End

Program :

  public class CheckSortedArray {
     public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 4, 5}; 
        if (isSorted(arr)) {
            System.out.println(“The array is sorted in non-decreasing order.”);
        } else {
            System.out.println(“The array is not sorted in non-decreasing order.”);
        }
    }
    public static boolean isSorted(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i – 1]) {
                return false; 
            }
        }
        return true; 
    }
}

Output :

The array is sorted in non-decreasing order.

Explanation :

This program checks whether a given integer array is sorted in non-decreasing order (each element is greater than or equal to the one before it). It iterates through the array and compares each element with the previous one. If it finds any element that is smaller than the one before, it immediately concludes that the array is not sorted. Otherwise, it confirms that the array is sorted. This method is efficient with O(n) time complexity.

5. Write a program to move all zero elements of an array to the end, without changing the relative order of non-zero elements?

Algorithm :

  • Start
  • Initialize the array: arr = {0, 1, 9, 2, 0, 3, 4, 0}
  • Call moveZeroes(arr)
  • Inside moveZeroes():
    • Set nonZeroIndex = 0
    • Loop from i = 0 to arr.length – 1:
      • If arr[i] is not 0:
        • Swap arr[nonZeroIndex] and arr[i]
        • Increment nonZeroIndex by 1
  • After the loop, all non-zero elements are moved to the front, and zeroes are pushed to the end
  • Return to main method
  • Print the updated array
  • End

Program :

        public class MoveZeroesToEnd {
       public static void main(String[] args) {
        int[] arr = {0, 1, 9, 2, 0, 3, 4, 0};
        moveZeroes(arr);
        System.out.print(“Array after moving zeroes: “);
        for (int num : arr) {
            System.out.print(num + ” “);
           }
     }
    public static void moveZeroes(int[] arr) {
        int nonZeroIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                int temp = arr[nonZeroIndex];
                arr[nonZeroIndex] = arr[i];
                arr[i] = temp;
                nonZeroIndex++; 
            }
        }
    }
}

Output :

Array after moving zeroes: 1 9 2 3 4 0 0 0

Explanation :

This program moves all the zeroes to the end of the array while maintaining the order of non-zero elements. It uses a pointer nonZeroIndex to track where the next non-zero element should be placed. As it iterates through the array, whenever it encounters a non-zero value, it swaps it with the element at nonZeroIndex. This approach works in-place (no extra space used) and has a time complexity of O(n), making it efficient and optimal.

6. Write a program to find the second largest element in an array?

Algorithm :

  • Start
  • Initialize the array: arr = {12, 35, 1, 10, 34, 1}
  • Call the method findSecondLargest(arr)
  • Inside findSecondLargest():
    • Initialize largest = Integer.MIN_VALUE
    • Initialize secondLargest = Integer.MIN_VALUE
    • Loop through the array:
      • If arr[i] > largest:
        • Set secondLargest = largest
        • Set largest = arr[i]
      • Else if arr[i] > secondLargest and arr[i] != largest:
        • Set secondLargest = arr[i]
  • Return secondLargest
  • In main, check if result is Integer.MIN_VALUE:
    • If yes, print “No second largest element”
    • Else, print the result
  • End

Program :

public class SecondLargestElement {
         public static void main(String[] args) {
        int[] arr = {12, 35, 1, 10, 34, 1};
        int secondLargest = findSecondLargest(arr);
        if (secondLargest == Integer.MIN_VALUE) {
            System.out.println(“There is no second largest element in the array.”);
        } else {
            System.out.println(“The second largest element is: ” + secondLargest);
        }
    }
    public static int findSecondLargest(int[] arr) {
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > largest) {
                secondLargest = largest; 
                largest = arr[i]; 
            }
            else if (arr[i] > secondLargest && arr[i] != largest) {
                secondLargest = arr[i];
            }
        }
        return secondLargest;
    }
}

Output :

The second largest element is: 34

Explanation :

                This program efficiently finds the second largest element in an array by scanning it once. It keeps track of two variables: largest and secondLargest. When a new larger element is found, it updates both values. If an element is smaller than the largest but greater than the second largest, it updates only the secondLargest. This method handles duplicates and negative values correctly. It runs in O(n) time and does not require sorting, making it efficient.

7. Write a program to given an array of size n-1 containing numbers from 1 to n, write a program to find the missing number?

Algorithm :

  • Start
  • Initialize the array: arr = {1, 2, 3, 5}
  • Call the method findMissingNumber(arr)
  • Inside findMissingNumber():
    • Let n = arr.length + 1 → n = 5 (since one number is missing from 1 to 5)
    • Calculate the expected sum using the formula: n * (n + 1) / 2
    • → expectedSum = 5 * 6 / 2 = 15
    • Initialize actualSum = 0Loop through the array:
      • Add each number to actualSum
      • After the loop: actualSum = 1 + 2 + 3 + 5 = 11
    • Compute the missing number: expectedSum – actualSum = 15 – 11 = 4
  • Return the missing number
  • In main, print the result: “The missing number is: 4”
  • End

Program :

       public class MissingNumber {
         public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5};   
        int missingNumber = findMissingNumber(arr);
        System.out.println(“The missing number is: ” + missingNumber);
    }
    public static int findMissingNumber(int[] arr) {
        int n = arr.length + 1; 
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : arr) {
            actualSum += num;
        }
        return expectedSum – actualSum;
    }
}

Output :

The missing number is: 4

Explanation :

           This program finds a missing number in an array containing distinct integers from 1 to n, with exactly one number missing. It uses the mathematical formula for the sum of the first n natural numbers and subtracts the actual sum of the array to determine the missing value. This approach is highly efficient with O(n) time complexity and O(1) space complexity. It avoids sorting or extra data structures and works reliably for single missing values in a sequential series.

8. Write a program to find the first duplicate element in an array?

Algorithm :

  • Start
  • Initialize the array: arr = {1, 2, 3, 4, 5, 6, 2, 7}
  • Call the method findFirstDuplicate(arr)
  • Inside findFirstDuplicate():
    • Create an empty HashSet<Integer> seen
    • Loop through each element num in the array:
      • If num is already in seen, return num (this is the first duplicate)
      • Otherwise, add num to seen
  • If loop completes with no duplicate found, return -1
  • In main, print:
    • “No duplicate elements found” if result is -1
    • Otherwise, print the duplicate number
  • End

Program :

    import java.util.HashSet;
      public class FirstDuplicate {
       public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 2, 7}; 
        int duplicate = findFirstDuplicate(arr);
        if (duplicate == -1) {
            System.out.println(“No duplicate elements found.”);
        } else {
            System.out.println(“The first duplicate element is: ” + duplicate);
        }
    }
    public static int findFirstDuplicate(int[] arr) {
        HashSet<Integer> seen = new HashSet<>();
        for (int num : arr) {
            if (seen.contains(num)) {
                return num;
            }
            seen.add(num);
        }
        return -1;
    }
}

Output :

 The first duplicate element is: 2

Explanation :

         The FirstDuplicate program identifies the first repeating element in an integer array. It uses a HashSet to keep track of numbers that have already been seen while iterating through the array.
As it checks each number:
If the number is not in the set, it gets added to the set.
If the number is already in the set, it means the number has appeared before and is the first duplicate, so the program immediately returns it.
In the given array {1, 2, 3, 4, 5, 6, 2, 7}, the number 2 appears again after its first occurrence, making it the first duplicate. The use of a HashSet ensures this is done efficiently in O(n) time, without needing to sort the array or use nested loops.

9. Write a program to count how many times each element appears in an array?

Algorithm :

  • Start
  • Initialize the array: arr = {4, 5, 6, 4, 7, 8, 5, 6, 4}
  • Call the method countElementOccurrences(arr)
  • Inside the method:
    • Create a HashMap<Integer, Integer> called frequencyMap
    • For each number num in the array:
      • Check if num is already a key in frequencyMap
      • If it is, increment its value (i.e., count) by 1
      • If it is not, add it with initial value 1 (default 0 + 1)
  • After the loop, iterate over frequencyMap.entrySet()
  • For each key-value pair:
    • Print: “Element X appears Y time(s)”
  • End

Program :

import java.util.HashMap;
        import java.util.Map;
        public class CountElements {
        public static void main(String[] args) {
        int[] arr = {4, 5, 6, 4, 7, 8, 5, 6, 4};
        countElementOccurrences(arr);
    }
    public static void countElementOccurrences(int[] arr) {
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        System.out.println(“Element occurrences:”);
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            System.out.println(“Element ” + entry.getKey() + ” appears ” + entry.getValue() + ” time(s).”);
        }
    }
}

 Output :

Element occurrences:
Element 4 appears 3 time(s).
Element 5 appears 2 time(s).
Element 6 appears 2 time(s).
Element 7 appears 1 time(s).
Element 8 appears 1 time(s).

Explanation :

       This program counts how many times each number appears in the array using a HashMap. As it loops through the array, it checks if the current number is already stored as a key in the map. If it is, its count is increased. If not, the number is added with a starting count of 1. The method getOrDefault() simplifies this by returning 0 if the key isn’t found. After processing the array, the map contains each unique number with its total count, which is then printed. This approach is efficient (O(n) time complexity) and useful when analyzing frequencies in arrays or lists.

10. Write a program to merge two sorted arrays into a single sorted array?

Algorithm :

  • Start
  • Input two sorted arrays:
    • arr1 = {1, 3, 5, 7}
    • arr2 = {2, 4, 6, 8}
  • Initialize pointers:
    • i = 0 for arr1
    • j = 0 for arr2
    • k = 0 for the merged array
  • Create a new array mergedArray of size arr1.length + arr2.length
  • While both arrays have elements left:
    • If arr1[i] <= arr2[j], set mergedArray[k] = arr1[i], increment i and k
    • Else, set mergedArray[k] = arr2[j], increment j and k
  • Copy remaining elements (if any):
    • While i < arr1.length, copy arr1[i] into mergedArray[k]
    • While j < arr2.length, copy arr2[j] into mergedArray[k]
  • Return the merged array
  • Print the merged array using Arrays.toString()
  • End

Program :

       import java.util.Arrays;
        public class MergeSortedArrays {
         public static void main(String[] args) {
           int[] arr1 = {1, 3, 5, 7}; 
           int[] arr2 = {2, 4, 6, 8};
          int[] mergedArray = mergeSortedArrays(arr1, arr2);
          System.out.println(“Merged sorted array: ” + Arrays.toString(mergedArray));
       }
        public static int[] mergeSortedArrays(int[] arr1, int[] arr2) {
        int n1 = arr1.length;
        int n2 = arr2.length;
        int[] mergedArray = new int[n1 + n2]; 
        int i = 0, j = 0, k = 0;
        while (i < n1 && j < n2) {
            if (arr1[i] <= arr2[j]) {
                mergedArray[k++] = arr1[i++];
            } else {
                mergedArray[k++] = arr2[j++];
            }
        }
        while (i < n1) {
            mergedArray[k++] = arr1[i++];
        }
        while (j < n2) {
            mergedArray[k++] = arr2[j++];
        }
        return mergedArray;
    }
}

Output :

Merged sorted array: [1, 2, 3, 4, 5, 6, 7, 8]

Explanation :

             This program merges two already sorted arrays into one single sorted array using a two-pointer technique, which is efficient and runs in linear time, O(n). It maintains three indices: one for each input array and one for the result array. It compares the current elements of both arrays and inserts the smaller one into the result array, continuing this until all elements from both arrays are placed. This method avoids using extra sorting steps, making it ideal for merging data like in merge sort or sorted datasets.

11. Write a program to check if two arrays are equal (contain the same elements in the same order)?

Algorithm :

  • Start
  • Input two arrays:
    • arr1 = {1, 2, 3, 4}
    • arr2 = {1, 2, 3, 4}
  • Check if lengths of both arrays are equal:
    • If not equal, return false (arrays are not equal)
  • Iterate through each index i from 0 to arr1.length – 1:
    • Compare arr1[i] with arr2[i]
    • If any pair of elements are not equal, return false
  • If the loop completes without returning false, return true
  • Print the result:
    • If true, print “The arrays are equal.”
    • If false, print “The arrays are not equal.”
  • End

Program :

      import java.util.Arrays;
     public class CheckArraysEqual {
     public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4}; 
        int[] arr2 = {1, 2, 3, 4}; 
        if (areArraysEqual(arr1, arr2)) {
            System.out.println(“The arrays are equal.”);
        } else {
            System.out.println(“The arrays are not equal.”);
        }
    }
    public static boolean areArraysEqual(int[] arr1, int[] arr2) {
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false; 
            }
        }
      return true;
    }
}

Output :

 The arrays are equal.

Explanation :

This program checks whether two integer arrays are equal in both length and content. It first compares the sizes of the arrays; if they differ, it immediately returns false. If the sizes are the same, it loops through each element and compares them one by one. If any mismatch is found, it concludes the arrays are not equal. If no mismatch is found, it returns true, confirming that both arrays are equal in order and values. This approach has a time complexity of O(n), where n is the number of elements in the array.

12. Write a program to find the common elements between two arrays?

Algorithm :

  • Start
  • Initialize two arrays:
    • arr1 = {1, 2, 3, 4, 5}
    • arr2 = {3, 4, 5, 6, 7}
  • Create a HashSet named set
  • Insert all elements of arr1 into set
    • After this step, set = {1, 2, 3, 4, 5}
  • Initialize a boolean variable found = false to track if any common element is found
  • Iterate through each element in arr2:
    • For each num in arr2, check if set.contains(num)
    • If true, print the number and set found = true
  • After the loop, if found == false, print “No common elements found.”
  • End

Program :

   import java.util.HashSet;
       public class CommonElements {
        public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5}; 
        int[] arr2 = {3, 4, 5, 6, 7};
        findCommonElements(arr1, arr2);
    }
    public static void findCommonElements(int[] arr1, int[] arr2) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : arr1) {
            set.add(num);
        }
        System.out.print(“Common elements: “);
        boolean found = false;
        for (int num : arr2) {
            if (set.contains(num)) {
                System.out.print(num + ” “);
                found = true;
            }
        }
        if (!found) {
            System.out.println(“No common elements found.”);
        } else {
            System.out.println();
        }
    }
}

Output :

Common elements: 3 4 5

Explanation : 

                    This program finds and prints the common elements between two arrays using a HashSet for efficient look-up. It first stores all elements of the first array (arr1) in a set. Then, it iterates through the second array (arr2) and checks for each element if it exists in the set. If a match is found, it prints the number. The use of a HashSet ensures that look-up operations are done in constant time O(1), making the entire approach efficient with a time complexity of O(n + m) where n and m are the lengths of the two arrays. This is ideal for detecting duplicates or intersections between two sets of values.

13. Write a program to find the Sum of All Elements in an Array?

Algorithm :

  • Start
  • Define a method sumOfElements(int[] arr) that:
    • Initializes a variable sum = 0
    • Iterates through the array using a loop
    • Adds each element to sum
    • Returns the sum
  • In the main method:
    • Declare and initialize an array: array = {1, 2, 3, 4, 5}
    • Call the method sumOfElements(array) and store the result
    • Print the result
  • End

Program :

   public class SumOfArray {
    public static int sumOfElements(int[] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        return sum;
    }
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        int result = sumOfElements(array);
        System.out.println(“The sum of all elements in the array is: ” + result);
    }
}

Output :

The sum of all elements in the array is: 15

Explanation :

This program calculates the sum of all elements in a given integer array. The sumOfElements method loops through each element in the array and accumulates their total in a sum variable. This result is then returned and printed. The time complexity is O(n), where n is the number of elements in the array, since each element is visited exactly once. This method provides a straightforward way to find the total of numerical data stored in arrays.

14. Write a program to find the Product of All Elements in an Array?

Algorithm :

  • Start
  • Define a method productOfElements(int[] arr):
    • Initialize product = 1
    • Loop through each element of the array using a for loop
    • Multiply each element with product
    • Return the final product
  • In the main method:
    • Create an array array = {1, 2, 3, 4, 5}
    • Call productOfElements(array) and store the result
    • Print the result
  • End

Program :

 public class ProductOfArray {
    public static int productOfElements(int[] arr) {
        int product = 1;
        for (int i = 0; i < arr.length; i++) {
            product *= arr[i];
        }
        return product;
    }
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        int result = productOfElements(array);
        System.out.println(“The product of all elements in the array is: ” + result);
    }
}

Output :

The product of all elements in the array is: 120

Explanation :

         This program computes the product of all elements in a given integer array. The method initializes a variable product to 1 (since 1 is the identity element for multiplication), then multiplies each array element with it. After iterating through the entire array, the final product is returned and displayed. The algorithm is efficient, with a time complexity of O(n) where n is the size of the array, as it makes a single pass through the elements.

15. Write a program to find the Even and Odd Count in an Array?

Algorithm :

  • Start
  • Define a method countEvenOdd(int[] arr):
    • Initialize two counters: evenCount = 0, oddCount = 0
    • Loop through each element num in the array:
      • If num % 2 == 0, increment evenCount
      • Else, increment oddCount
  • Print both evenCount and oddCount
  • In main() method:
    • Declare an integer array array = {1, 2, 3, 4, 5, 6, 7, 8, 9}
    • Call countEvenOdd(array)
  • End

Program :

public class EvenOddCount {
    public static void countEvenOdd(int[] arr) {
        int evenCount = 0; 
        int oddCount = 0;  
        for (int num : arr) {
            if (num % 2 == 0) {
                evenCount++; 
            } else {
                oddCount++;
            }
        }
        System.out.println(“Even numbers count: ” + evenCount);
        System.out.println(“Odd numbers count: ” + oddCount);
    }
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        countEvenOdd(array);
    }
}

Output :

 Even numbers count: 4
Odd numbers count: 5

Explanation :

The EvenOddCount program is designed to count how many even and odd numbers exist in a given integer array. It works by looping through each element of the array and checking whether the number is even or odd using the modulus operator %. If a number divided by 2 gives a remainder of 0 (num % 2 == 0), it is considered even; otherwise, it is odd. Two separate counters (evenCount and oddCount) keep track of how many numbers fall into each category. At the end of the loop, the program prints the total counts of even and odd numbers.

16. Write a program to find the Largest Product of Two Elements in an Array?

Algorithm :

  • Start
  • Input Validation:
    • Check if the array has fewer than 2 elements.
    • If yes, print a message and return -1 (cannot find product with fewer than 2 numbers).
  • Initialization:
    • Initialize max1 and max2 to the smallest integer (Integer.MIN_VALUE) to track the two largest numbers.
    • Initialize min1 and min2 to the largest integer (Integer.MAX_VALUE) to track the two smallest numbers.
  • Traverse the Array:
    • For each number in the array:
    • Update max1 and max2 to always contain the two largest numbers.
    • Update min1 and min2 to always contain the two smallest numbers.
  • Calculate Products:
  • Compute two possible maximum products:
    • max1 * max2 (product of two largest positive numbers)
    • min1 * min2 (product of two smallest negative numbers)
  • Return the Larger Product:
    • Return the greater of the two computed products.
  • End

Program :

    public class LargestProductOfTwo {
    public static int largestProduct(int[] arr) {
        if (arr.length < 2) {
            System.out.println(“Array must contain at least two elements.”);
            return -1; 
        }
        int max1 = Integer.MIN_VALUE; 
        int max2 = Integer.MIN_VALUE; 
        int min1 = Integer.MAX_VALUE; 
        int min2 = Integer.MAX_VALUE;
        for (int num : arr) {
            if (num > max1) {
                max2 = max1; 
                max1 = num;  
            } else if (num > max2) {
                max2 = num;  
            }
            if (num < min1) {
                min2 = min1; 
                min1 = num;
            } else if (num < min2) {
                min2 = num; 
            }
        }
        return Math.max(max1 * max2, min1 * min2);
    }
    public static void main(String[] args) {
        int[] array = {1, -10, -3, 4, 6};
        int result = largestProduct(array);
        System.out.println(“The largest product of two elements in the array is: ” + result);
    }
}

Output :

The largest product of two elements in the array is: 30

Explanation :

            This program calculates the largest product of any two elements in an integer array. It smartly considers both the largest positive numbers and the smallest (i.e., most negative) numbers because two negative numbers can produce a large positive product. For example, in the array {1, -10, -3, 4, 6}, the product -10 * -3 = 30 is greater than 6 * 4 = 24, so the result is 30. This makes the logic suitable for arrays containing both negative and positive integers.

17. Write a program to find the Element that Appears Once in an Array?

Algorithm :

  • Start
  • Initialize result = 0.
  • Iterate through each element in the array:
    • XOR result with the current element.
  • Repeat for all elements:
  • 0 ^ 4 = 4
  • 4 ^ 5 = 1
  • 1 ^ 6 = 7
  • 7 ^ 4 = 3
  • 3 ^ 5 = 6
  • 6 ^ 7 = 1
  • 1 ^ 6 = 7
  • Return the final value of result which is 7.
  • End

 Program :

    public class ElementAppearsOnce {
    public static int findElementAppearsOnce(int[] arr) {
        int result = 0; 
        for (int num : arr) {
            result ^= num; 
        }
        return result; 
    }
    public static void main(String[] args) {
        int[] array = {4, 5, 6, 4, 5, 7, 6};
        int result = findElementAppearsOnce(array);
        System.out.println(“The element that appears once in the array is: ” + result);
    }
}

Output : 

 The element that appears once in the array is: 7

Explanation :

              This program finds the number that appears only once in an array where all other numbers appear twice. It uses the XOR (^) operation, which cancels out duplicate numbers due to the property that a ^ a = 0 and a ^ 0 = a. By XORing all elements, duplicates are removed, and only the unique number remains. In the given array {4, 5, 6, 4, 5, 7, 6}, the final output is 7, as it appears only once.

18. Write a program to find the Union of Two Arrays?

Algorithm :

  • Start
  •  Create an empty HashSet<Integer> called unionSet.
  •  Traverse the first array arr1 = {1, 2, 3, 4}:
    • Add each element to unionSet: → {1, 2, 3, 4}
  •  Traverse the second array arr2 = {3, 4, 5, 6}:
    • Add each element to unionSet:
      • 3 and 4 are already present (no duplicates in a HashSet)
      • 5 and 6 are added → final set: {1, 2, 3, 4, 5, 6}
  •  Create a result array of size unionSet.size() → int[6].
  •  Copy elements from the unionSet into the result array.
  •  Return the result array and print it.
  •  End

Program :

import java.util.HashSet;
       public class UnionOfArrays {
       public static int[] findUnion(int[] arr1, int[] arr2) {
        HashSet<Integer> unionSet = new HashSet<>();
        for (int num : arr1) {
            unionSet.add(num);
        }
        for (int num : arr2) {
            unionSet.add(num);
        }
        int[] result = new int[unionSet.size()];
        int i = 0;
        for (int num : unionSet) {
            result[i++] = num;
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4};
        int[] arr2 = {3, 4, 5, 6};
        int[] union = findUnion(arr1, arr2);
        System.out.print(“Union of the two arrays: “);
        for (int num : union) {
            System.out.print(num + ” “);
        }
    }
}

Output :

  Union of the two arrays: 1 2 3 4 5 6

 Explanation :

This Java program calculates the union of two arrays, meaning it combines all unique elements from both arrays without duplicates. It uses a HashSet to automatically handle duplicates, as sets only store unique values. The program first adds all elements from the first and second arrays into the set, ensuring each number appears only once. It then converts the set into an array and prints it. For input arrays {1, 2, 3, 4} and {3, 4, 5, 6}, the output is the union {1, 2, 3, 4, 5, 6}.

19. Write a program to find the Missing Positive Integer in an Unsorted Array?

Algorithm :

  • Start
  • Given array: {3, 4, -1, 1}
  • Find the smallest missing positive integer.
  • Array Length: n = 4
  • First Loop (Rearrange Elements):
  • Place each positive number x (1 ≤ x ≤ n) at index x – 1.
  • i = 0: arr[0] = 3 → valid & not in right place → swap with arr[2] → array becomes {-1, 4, 3, 1}
    • i = 0 again: arr[0] = -1 → skip
    • i = 1: arr[1] = 4 → swap with arr[3] → array becomes {-1, 1, 3, 4}
    • i = 1 again: arr[1] = 1 → swap with arr[0] → array becomes {1, -1, 3, 4}
    • i = 1 again: arr[1] = -1 → skip
    • i = 2: arr[2] = 3 → already at correct position → skip
    • i = 3: arr[3] = 4 → already at correct position → skip
  • Final rearranged array: {1, -1, 3, 4}
  • Second Loop (Find Missing):
    1. i = 0: arr[0] = 1 → correct
    1. i = 1: arr[1] ≠ 2 → return 2 (missing number)
  • End

 Program :

   import java.util.Arrays;
   public class MissingPositiveInteger {
    public static int findMissingPositive(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            while (arr[i] > 0 && arr[i] <= n && arr[arr[i] – 1] != arr[i]) {
                // Swap arr[i] with arr[arr[i] – 1]
                int temp = arr[i];
                arr[i] = arr[arr[i] – 1];
                arr[temp – 1] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (arr[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
    public static void main(String[] args) {
        int[] array = {3, 4, -1, 1};
        int result = findMissingPositive(array);
        System.out.println(“The smallest missing positive integer is: ” + result);
    }
}

Output :  

The smallest missing positive integer is: 2

Explanation :

          This Java program efficiently finds the smallest missing positive integer in an unsorted array using in-place cyclic sorting. It rearranges the array so that each positive number x (where 1 ≤ x ≤ array length) is placed at index x – 1. During this process, negative numbers and numbers out of range are ignored. Once the array is rearranged, it scans the array to find the first index i where the value is not i + 1, indicating that i + 1 is missing. If all values are in place, the missing number is n + 1. For input {3, 4, -1, 1}, the smallest missing positive number is 2.

20. Write a program to find the Intersection of Three Sorted Arrays?

Algorithm :

  • Start
  • Given arrays :
  • arr1 = {1, 5, 10, 20, 40}
  • arr2 = {6, 7, 20, 80}
  • arr3 = {3, 4, 5, 20, 80}
  • Find common elements in all three sorted arrays.
  • Initialize pointers: i = 0, j = 0, k = 0
  • Compare elements at current pointers:
  • arr1[i], arr2[j], and arr3[k]
  • If all three are equal, it’s a common element → add to result and increment all pointers.
  • If not equal, increment the pointer pointing to the smallest value (to try to match the others).
  • Repeat until one of the arrays is fully traversed.
  • End

Program :

import java.util.ArrayList;
      import java.util.List;
     public class IntersectionOfThreeSortedArrays {
      public static List<Integer> intersection(int[] arr1, int[] arr2, int[] arr3) {
        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0, k = 0;
        // Traverse all three arrays
        while (i < arr1.length && j < arr2.length && k < arr3.length) {
            // If elements are the same in all three arrays, add to result
            if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
                result.add(arr1[i]);
                i++;
                j++;
                k++;
            }
            // If arr1[i] is smaller, increment i
            else if (arr1[i] < arr2[j]) {
                i++;
            }
            // If arr2[j] is smaller, increment j
            else if (arr2[j] < arr3[k]) {
                j++;
            }
            // If arr3[k] is smaller, increment k
            else {
                k++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 5, 10, 20, 40};
        int[] arr2 = {6, 7, 20, 80};
        int[] arr3 = {3, 4, 5, 20, 80};
        List<Integer> intersectionResult = intersection(arr1, arr2, arr3);
        System.out.println(“The intersection of the three arrays is: ” + intersectionResult);
    }
}

Output : 

The intersection of the three arrays is: [20]

Explanation :

This Java program finds the intersection of three sorted arrays using three pointers. Starting from the beginning of each array, it compares the current elements. If all three elements match, it’s a common value and is added to the result list. If they don’t match, the pointer with the smallest value is incremented to catch up. This continues until one of the arrays is fully traversed. For input arrays {1, 5, 10, 20, 40}, {6, 7, 20, 80}, and {3, 4, 5, 20, 80}, the only common element is 20.

21. Write a program to find the Missing Number in an Array of 1 to N?

Algorithm :

  • Start
  • Array: {1, 2, 4, 5, 6}
  • N = 6 → the array should contain numbers from 1 to 6
  • Calculate Expected Sum of numbers from 1 to N using the formula:
  • expectedSum = N * (N + 1) / 2 = 6 * 7 / 2 = 21
  • Calculate Actual Sum of elements in the array:
  • actualSum = 1 + 2 + 4 + 5 + 6 = 18
  • Find Missing Number by subtracting actualSum from expectedSum:
  • missingNumber = 21 – 18 = 3
  • Output: Print the missing number → 3
  • End

Program :

   public class MissingNumber {
    public static int findMissingNumber(int[] arr, int N) {
        int expectedSum = N * (N + 1) / 2;
        int actualSum = 0;
        for (int num : arr) {
            actualSum += num;
        }
        return expectedSum – actualSum;
    }
    public static void main(String[] args) {
        int[] array = {1, 2, 4, 5, 6};
        int N = 6; 
        int missingNumber = findMissingNumber(array, N);
        System.out.println(“The missing number is: ” + missingNumber);
    }
}

Output : 

The missing number is: 3

Explanation :

                 This Java program finds the missing number in a sequence of integers from 1 to N, where one number is missing. It uses the formula for the sum of the first N natural numbers (N*(N+1)/2) to calculate the expected total. It then sums up the elements in the given array. The difference between the expected sum and the actual sum gives the missing number. This method is simple and efficient, requiring only one pass through the array, with a time complexity of O(n) and space complexity of O(1). For the input {1, 2, 4, 5, 6}, the missing number is correctly identified as 3.

22. Write a program to find the Common Elements in All Rows of a Matrix?

Algorithm :

  • Start
  • Given Matrix:
  • {  
  • {1, 2, 3, 4},  
  • {2, 3, 4, 5},  
  • {3, 4, 6, 7}
  • }
  • Initialize commonElements with the first row → {1, 2, 3, 4}
  • Process second row {2, 3, 4, 5}:
  • Create a Set of second row → {2, 3, 4, 5}
  • Intersect with commonElements using retainAll
  • Resulting commonElements: {2, 3, 4}
  • Process third row {3, 4, 6, 7}:
  • Create a Set of third row → {3, 4, 6, 7}
  • Intersect with commonElements: {2, 3, 4} ∩ {3, 4, 6, 7}
  • Final commonElements: {3, 4}
  • Return and print:
    1. Output → The common elements in all rows are: [3, 4]
  • End

Program :

    import java.util.HashSet;
    import java.util.Set;
   public class CommonElementsInMatrix {
    public static Set<Integer> findCommonElements(int[][] matrix) {
        Set<Integer> commonElements = new HashSet<>();
        for (int i = 0; i < matrix[0].length; i++) {
            commonElements.add(matrix[0][i]);
        }
        for (int row = 1; row < matrix.length; row++) {
            Set<Integer> currentRowSet = new HashSet<>();   
            for (int col = 0; col < matrix[row].length; col++) {
                currentRowSet.add(matrix[row][col]);
            }
            commonElements.retainAll(currentRowSet);
        }
        return commonElements;
    }
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3, 4},
            {2, 3, 4, 5},
            {3, 4, 6, 7}
        };
        // Find and print common elements in all rows
        Set<Integer> common = findCommonElements(matrix);
        System.out.println(“The common elements in all rows are: ” + common);
    }
}

Output :

The common elements in all rows are: [3, 4]

Explanation :

             This Java program finds elements that are common to all rows of a given matrix. It starts by adding all elements from the first row into a HashSet. Then, for each of the remaining rows, it converts the row into a set and uses the retainAll method to keep only the elements that are present in both the current set and the common set so far. This way, only values that appear in every row are retained. For the provided matrix, the elements 3 and 4 are the only ones present in all rows, and thus are returned. The algorithm is efficient and readable, with time complexity roughly O(m × n) where m is the number of rows and n is the number of columns.

23. Write a program to find the Element that Occurs More Than n/3 Times?

Algorithm :

  • Start
  • Given:
  • Array: {3, 3, 4, 2, 4, 4, 2, 4, 4}
  • Length n = 9 → threshold = n / 3 = 3
  • Execution Steps:
  • Initialize frequency map (empty).
  • Traverse array and count occurrences:
  • 3 → 2 times
  • 4 → 5 times
  • 2 → 2 times
  • Iterate through the map:
  • 3 → count = 2 → not more than 3
  • 4 → count = 5 → greater than 3 → print: “Element 4 occurs more than n/3 times.”
  • 2 → count = 2 → not more than 3
  • Since at least one qualifying element is found, skip the “no element found” message.
  • End

Program :

import java.util.HashMap;
   import java.util.Map;
   public class ElementOccursMoreThanNby3 {
    public static void findElement(int[] arr) {
        int n = arr.length;
        int threshold = n / 3;
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        } 
        boolean found = false;
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (entry.getValue() > threshold) {
                System.out.println(“Element ” + entry.getKey() + ” occurs more than n/3 times.”);
                found = true;
            }
        }
        if (!found) {
            System.out.println(“No element occurs more than n/3 times.”);
        }
    }
    public static void main(String[] args) {
        int[] array = {3, 3, 4, 2, 4, 4, 2, 4, 4};
        findElement(array);
    }
}

Output :

Element 4 occurs more than n/3 times.

 Explanation :

          This Java program finds any element in an array that appears more than n/3 times, where n is the array length. It uses a HashMap to count the frequency of each number. After building the frequency map, it checks each entry to see if its count exceeds n/3. If it finds such elements, it prints them; otherwise, it notifies that no such element exists. In the given array {3, 3, 4, 2, 4, 4, 2, 4, 4}, the number 4 appears 5 times, which is more than 3, so it is printed as the result.

24. Write a program to find the Longest Palindromic Subsequence in an Array?

Algorithm :

  • Start
  • Given array: {1, 2, 3, 2, 1}
    Length n = 5
  • Initialize a DP table dp[n][n] with dp[i][i] = 1 for all i (every element is a palindrome of length 1).
  • Check all subsequence lengths from 2 to n:
  • For subsequence of length 2 to 5:
  • If arr[i] == arr[j], set dp[i][j] = dp[i+1][j-1] + 2
  • Else, set dp[i][j] = max(dp[i+1][j], dp[i][j-1])
  • Build the table from shorter to longer subsequences.
  • Final result is stored in dp[0][n-1], i.e., dp[0][4].
  • For input {1, 2, 3, 2, 1}, the longest palindromic subsequence is the entire array itself (1, 2, 3, 2, 1), so the result is 5.
  • End

Program :

public class LongestPalindromicSubsequence {
    public static int longestPalindromicSubsequence(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int len = 2; len <= n; len++) { 
            for (int i = 0; i < n – len + 1; i++) {
                int j = i + len – 1; 
                if (arr[i] == arr[j]) {
                    dp[i][j] = dp[i + 1][j – 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j – 1]);
                }
            }
        }
        return dp[0][n – 1];
    }
     public static void main(String[] args) {
        int[] array = {1, 2, 3, 2, 1};
        // Find and print the length of the longest palindromic subsequence
        int result = longestPalindromicSubsequence(array);
        System.out.println(“The length of the longest palindromic subsequence is: ” + result);
    }
}

Output : 

The length of the longest palindromic subsequence is: 5

Explanation :

                 This program computes the length of the longest palindromic subsequence in an integer array using dynamic programming. It initializes a 2D DP table where each dp[i][j] stores the length of the longest palindromic subsequence within arr[i..j]. If the values at the two ends of the subsequence are equal, it adds 2 to the value found in the smaller subproblem dp[i+1][j-1]. Otherwise, it takes the maximum of excluding either end. For the input {1, 2, 3, 2, 1}, the entire array is a palindrome, so the output is 5.

25. Write a program to find the Sum of Diagonal Elements in a Matrix?

Algorithm :

  • Start
  • Given matrix:
  • [
  • {1, 2, 3},
  • {4, 5, 6},
  • {7, 8, 9}
  • ]Initialize sum = 0.
  • Loop over each row index i from 0 to n-1 (here, n = 3):
    • Add matrix[i][i] (primary diagonal).
    • Add matrix[i][n – i – 1] (secondary diagonal), only if it’s not the same as the primary diagonal element.
  • For this matrix:
    • i = 0: add 1 (primary) + 3 (secondary) → sum = 4
    • i = 1: add 5 (primary), skip secondary (same element) → sum = 9
    • i = 2: add 9 (primary) + 7 (secondary) → sum = 25
  • Final result: 25
  • End

Program :

    public class DiagonalSum {
    public static int sumOfDiagonals(int[][] matrix) {
        int n = matrix.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += matrix[i][i];
            if (i != n – i – 1) {
                sum += matrix[i][n – i – 1];
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        int result = sumOfDiagonals(matrix);
        System.out.println(“The sum of diagonal elements is: ” + result);
  }
}

Output :

The sum of diagonal elements is: 25

Explanation :

            This Java program calculates the sum of the diagonal elements of a square matrix. It traverses each row and adds both the primary diagonal (matrix[i][i]) and the secondary diagonal (matrix[i][n – i – 1]) elements. To avoid double-counting the center element in odd-sized matrices, it checks if both diagonals refer to the same element before adding. For the example 3×3 matrix, the diagonal elements are {1, 5, 9} and {3, 5, 7}, and their sum without double-counting 5 is 25.

Leave a Reply

Your email address will not be published. Required fields are marked *