Program 1: Find a missing number in given integer array of 1 to 100?
// Java program to find missing Number
class Nishant001
{
// Function to ind missing number
static int getMissingNo (int a[], int n)
{
int i, total;
total = (n+1)*(n+2)/2;
for ( i = 0; i< n; i++)
total -= a[i];
return total;
}
/* program to test above function */
public static void main(String args[])
{
int a[] = {1,2,4,5,6};
int miss = getMissingNo(a,5);
System.out.println(miss);
}
}
Output : 3
Time Complexity : O(n)
Program 2: Find the duplicate number on a given integer array?
class RepeatElement
{
void printRepeating(int arr[], int size)
{
int i, j;
System.out.println("Repeated Elements are :");
for (i = 0; i < size; i++)
{
for (j = i + 1; j < size; j++)
{
if (arr[i] == arr[j])
System.out.print(arr[i] + " ");
}
}
}
public static void main(String[] args)
{
RepeatElement repeat = new RepeatElement();
int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = arr.length;
repeat.printRepeating(arr, arr_size);
}
}
Output :
Repeating elements are 4 2
Time Complexity: O(n*n)
Auxiliary Space: O(1)
Program 3: Largest and smallest number in an unsorted integer array?
public class LargestSmallest
{
public static void main(String[] args)
{
int a[] = new int[] { 23, 34, 13, 64, 72, 90, 10, 15, 9, 27 };
int min = a[0]; // assume first elements as smallest number
int max = a[0]; // assume first elements as largest number
for (int i = 1; i < a.length; i++) // iterate for loop from arrays 1st index (second element)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
System.out.println("Largest Number in a given array is : " + max);
System.out.println("Smallest Number in a given array is : " + min);
}
}
Program 4: Find all pairs of integer array whose sum is equal to a given number
public class PairsOfElementsInArray
{
static void findThePairs(int inputArray[], int inputNumber)
{
System.out.println("Pairs of elements whose sum is "+inputNumber+" are : ");
for (int i = 0; i < inputArray.length; i++)
{
for (int j = i+1; j < inputArray.length; j++)
{
if(inputArray[i]+inputArray[j] == inputNumber)
{
System.out.println(inputArray[i]+" + "+inputArray[j]+" = "+inputNumber);
}
}
}
}
public static void main(String[] args)
{
findThePairs(new int[] {4, 6, 5, -10, 8, 5, 20}, 10);
findThePairs(new int[] {4, -5, 9, 11, 25, 13, 12, 8}, 20);
findThePairs(new int[] {12, 13, 40, 15, 8, 10, -15}, 25);
findThePairs(new int[] {12, 23, 125, 41, -75, 38, 27, 11}, 50);
}
}
Program 5: Sort an integer array in place using QuickSort algorithm?
public class QuickSortExample
{
public static void main(String[] args)
{
// This is unsorted array
Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };
// Let's sort using quick sort
quickSort( array, 0, array.length - 1 );
// Verify sorted array
System.out.println(Arrays.toString(array));
}
public static void quickSort(Integer[] arr, int low, int high)
{
//check for empty or null array
if (arr == null || arr.length == 0){
return;
}
if (low >= high){
return;
}
//Get the pivot element from the middle of the list
int middle = low + (high - low) / 2;
int pivot = arr[middle];
// make left < pivot and right > pivot
int i = low, j = high;
while (i <= j)
{
//Check until all values on left side array are lower than pivot
while (arr[i] < pivot)
{
i++;
}
//Check until all values on left side array are greater than pivot
while (arr[j] > pivot)
{
j--;
}
//Now compare values from both side of lists to see if they need swapping
//After swapping move the iterator on both lists
if (i <= j)
{
swap (arr, i, j);
i++;
j--;
}
}
//Do same operation as above recursively to sort two sub arrays
if (low < j){
quickSort(arr, low, j);
}
if (high > i){
quickSort(arr, i, high);
}
}
public static void swap (Integer array[], int x, int y)
{
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
}
Output: [3, 6, 10, 12, 13, 24, 70, 90]
Program 6: Perform a binary search in given array?
public class MyBinarySearch {
public int binarySearch(int[] inputArr, int key) {
int start = 0;
int end = inputArr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (key == inputArr[mid]) {
return mid;
}
if (key < inputArr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
MyBinarySearch mbs = new MyBinarySearch();
int[] arr = {2, 4, 6, 8, 10, 12, 14, 16};
System.out.println("Key 14's position: "+mbs.binarySearch(arr, 14));
int[] arr1 = {6,34,78,123,432,900};
System.out.println("Key 432's position: "+mbs.binarySearch(arr1, 432));
}
}
Output:
Key 14's position: 6
Key 432's position: 4
Program 7: Multiply two Matrices in Java
import java.util.Scanner;
class MatrixMultiplication
{
public static void main(String args[])
{
int m, n, p, q, sum = 0, c, d, k;
Scanner in = new Scanner(System.in);
System.out.println("Enter the number of rows and columns of first matrix");
m = in.nextInt();
n = in.nextInt();
int first[][] = new int[m][n];
System.out.println("Enter elements of first matrix");
for (c = 0; c < m; c++)
for (d = 0; d < n; d++)
first[c][d] = in.nextInt();
System.out.println("Enter the number of rows and columns of second matrix");
p = in.nextInt();
q = in.nextInt();
if (n != p)
System.out.println("The matrices can't be multiplied with each other.");
else
{
int second[][] = new int[p][q];
int multiply[][] = new int[m][q];
System.out.println("Enter elements of second matrix");
for (c = 0; c < p; c++)
for (d = 0; d < q; d++)
second[c][d] = in.nextInt();
for (c = 0; c < m; c++)
{
for (d = 0; d < q; d++)
{
for (k = 0; k < p; k++)
{
sum = sum + first[c][k]*second[k][d];
}
multiply[c][d] = sum;
sum = 0;
}
}
System.out.println("Product of the matrices:");
for (c = 0; c < m; c++)
{
for (d = 0; d < q; d++)
System.out.print(multiply[c][d]+"\t");
System.out.print("\n");
}
}
}
}
No comments:
Post a Comment