Java Program to Check if an Array is Strictly Increasing

This is the Java Program to Check if an Array is Strictly Increasing.

Problem Description
Given an array of integers check whether it is strictly increasing or not.
A strictly increasing array is an array whose each element is greater than it’s
preceding element.

Example:
Array = [1, 2, 3, 4, 5]

Output: Array is strictly increasing.

Problem Solution
Iterate through the array and check whether the current array element is greater than its
preceding element. If all the elements are greater than its preceding element return true,
else return false.

Program/Source Code
Here is the source code of the Java Program to Check if an Array is Strictly Increasing. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Check if an Array is Strictly Increasing
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class StrictlyIncreasing {
8. // Function to check array is strictly increasing or not.
9. static boolean checkStrictlyIncreasing(int[] array){
10. boolean result=true;
11. int i;
12. for(i=0;i<array.length-1;i++){
13. if(array[i]>=array[i+1])
14. {
15. result=false;
16. break;
 17. }
18. }
19. return result;
20. }
21.  
22. // Function to read the user input
23. public static void main(String[] args) {
24. BufferedReader br= new BufferedReader(new
InputStreamReader(System.in));
25. int size;
26. System.out.println("Enter the size of the array");
27. try{
28. size=Integer.parseInt(br.readLine());
29. }
30. catch(Exception e)
31. {
32. System.out.println("Invalid Input");
33. return;
34. }
35. int[] array=new int[size];
36. System.out.println("Enter array elements");
37. int i;
38. for(i=0;i<array.length;i++){
39. try{
40. array[i]=Integer.parseInt(br.readLine());
41. }
42. catch(Exception e)
43. {
44. System.out.println("An error occurred");
45. return;
46. }
47. }
48. boolean result=checkStrictlyIncreasing(array);
49. if(result){
50. System.out.println("Array is strictly increasing");
51. }
52. else{
53. System.out.println("Array is not strictly increasing");
54. }
55. }
56. }

Program Explanation
1. In function checkStrictlyIncreasing(), the loop for(i=0; i<array.length-1; i++) checks
whether each array element is greater than the element following it, through the condition
if(array[i] >= array[i+1]).
2. Any element that fulfils this condition, implies that the array is not strictly increasing, and
it sets the result to false and breaks from the loop.
3. Finally, the boolean variable result is returned as the answer.
advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Positive Test Case):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
Array is strictly increasing
 
Case 2 (Negative Test Case):
 
Enter the size of the array
8
Enter array elements
1
2
2
3
4
5
6
6
Array is not strictly increasing
 
Case 3 (Positive Test Case - another example):
 
Enter the size of the array
7
Enter array elements
12
24
45
56
678
890
980
Array is strictly increasing

Java Program to Print Odd Elements at Odd Index Number

This is the Java Program to Print Odd Elements at Odd Index Number.

Problem Description
Given an array of integers, print the odd numbers present at odd index numbers.
Example:

Array = [2,1,4,4,5,7]

Output = 1,7

Problem Solution
Iterate through the array, and check whether the current index is even or odd. If it is odd
then check the element at that index to be even or odd, print the element if it is odd.

Program/Source Code
Here is the source code of the Java Program to Print Odd Elements at Odd Index Number.
The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Print Odd Elements at Odd Index Number
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class OddIndexedOddElements {
8. // Function to print Odd Elements present at Odd Index Number
9. static void printOddIndexedElements(int[] array){
10. int i=0;
11. for(i=0; i<array.length; i++){
12. if(i%2 != 0 && array[i]%2 !=0){
13. System.out.print(array[i] + " ");
14. }
15. }
16. }
17.  
18. // Function to read user input
 19. public static void main(String[] args) {
20. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
21. int size;
22. System.out.println("Enter the size of the array");
23. try {
24. size = Integer.parseInt(br.readLine());
25. } catch (Exception e) {
26. System.out.println("Invalid Input");
27. return;
28. }
29. int[] array = new int[size];
30. System.out.println("Enter array elements");
31. int i;
32. for (i = 0; i < array.length; i++) {
33. try {
34. array[i] = Integer.parseInt(br.readLine());
35. } catch (Exception e) {
36. System.out.println("An error occurred");
37. return;
38. }
39. }
40. System.out.println("Output");
41. printOddIndexedElements(array);
42. }
43. }

Program Explanation
1. In function printOddIndexedElements(), the loop for(i=0; i<array.length; i++) iterates
through the array.
2. Then using the condition if(i%2 != 0 && array[i]%2 != 0), we first check whether the
current index is odd.
3. If the index is odd, then we check the element at that index (the condition after the &&
operator), if the element is odd, then display the element.
advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Positive test Case - having odd elements at odd index):
 
Enter the size of the array
6
Enter array elements
2
1
4
4
5
7
Output
1 7
 
Case 2 (Negative test Case - no odd element present at odd index):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
Output

Java Program to Find Local Maximas in an Array

This is the Java Program to Find Local Maximas in an Array.

Problem Description
Given an array of integers, find out the local maxima present in the array.
An element in an array is a local maxima if it greater than the element after it, and the
element before it.
For the elements at the extreme end only one check is required, that is, the element
following the first element or the element before the last element.
In case of two or more maxima, only one of them is returned.

Example:
Array = [1, 2, 3, 4, 5, -1]

Output:
5

Problem Solution
The idea here is to use an algorithm, similar to the binary search. Check the middle
element of the array, if it is greater than the elements following it and the element preceding
it, then it is the local maxima, else if it is greater than the preceding element, then the local
maxima is in the left half, else the local maxima is in the right half.

Program/Source Code
Here is the source code of the Java Program to Find Local Maximas in an Array. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Find Local Maximas in an Array
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class LocalMaxima {
8. // Function to return the index of the local Maxima
9. static int localMaxima(int[] array){
10. int low,mid,high;
11. low = 0;
12. high = array.length-1;
13. int ans;
14. while(low<=high){
15. mid = (low + high)/2;
16. if((mid == 0 || array[mid-1] < array[mid])
17. && (mid == array.length-1 || array[mid+1] < array[mid])){
18. return mid;
19. }
20. else if(mid > 0 && array[mid-1] > array[mid]){
21. high = mid-1;
22. }
23. else{
24. low = mid+1;
25. }
26. }
27. return -1;
28. }
29.  
30. // Function to read input
31. public static void main(String[] args) {
32. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
33. int size;
 34. System.out.println("Enter the size of the array");
35. try {
36. size = Integer.parseInt(br.readLine());
37. } catch (Exception e) {
38. System.out.println("Invalid Input");
39. return;
40. }
41. int[] array = new int[size];
42. System.out.println("Enter array elements");
43. int i;
44. for (i = 0; i < array.length; i++) {
45. try {
46. array[i] = Integer.parseInt(br.readLine());
47. } catch (Exception e) {
48. System.out.println("An error occurred");
49. return;
50. }
51. }
52. int index = localMaxima(array);
53. System.out.println("The local maxima is " + array[index]);
54. }
55. }

Program Explanation
1. In the function localMaxima(), we initialize two variables high and low as array.length-1
and 0 respectively.
2. Using a loop while(low <=high), we first calculate the middle index.
3. Now, in the condition if((mid == 0 || array[mid-1] < array[mid]) && (mid == array.length-1 ||
array[mid+1] < array[mid])), we check whether the element at current middle index is a
maxima.
4. If the element is a maxima, then we return the current middle index, otherwise using the
condition else if(mid > 0 && array[mid-1] > array[mid]), we first check that we are not at the
beginning of the array and finally, check if the preceding element is greater than the current
middle element.
5. If it is, we then set high to mid-1, to look in the first half of the array. Otherwise, we set
low to mid+1 to look for the maxima in the second half of the array.
advertisement

Time Complexity: O(log(n)) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Positive test case - local maxima is not at the extreme ends):
 
Enter the size of the array
6
Enter array elements
1
2
3
4
5
-1
The local maxima is 5
 
Case 2 (Positive test case - local maxima is at the beginning of the array):
 
Enter the size of the array
8
Enter array elements
8
7
6
5
4
3
2
1
The local maxima is 8
 
Case 3 (Positive test case - local maxima is at the end of the array):
 
Enter the size of the array
6
Enter array elements
1
2
3
4
5
6
The local maxima is 6

Java Program to Print the Next Greater Element in the Array in

Order, Elements with no Greater Elements will have -1 Printed
Next to them
This is the Java Program to Print the Next Greatest Element in the Array in Order, Elements
with no Greater Elements will have -1 Printed Next to them.
Problem Description
Given an array, print the Next Greater Element (NGE) for every element. The Next greater
Element for an element x is the first greater element on the right side of x in the array.
Elements for which no greater element exist, consider next greater element as -1.

Example:

For the input array [6, 4, 5, 7], the next greater elements for each element are as follows.

6—->7
4—->5
5—->7
7—->-1

Problem Solution
Create a stack and push the first element of the array onto it. Now for each of the
remaining elements, check whether the stack is empty or not. If the stack is not empty, pop
an element from the stack, if the element is smaller than the current array element, then
print the current element as the next greater element for popped element. Continue the
process, either until the stack is empty or the popped element is greater than the current
array element. Finally, push the current array element onto the stack. At last, after iterating
over the array, pop all the elements of the stack and print -1 as the next greater element for
them.

Program/Source Code
Here is the source code of the Java Program to Print the Next Greatest Element in the
Array in Order, Elements with no Greater Elements will have -1 Printed Next to them. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. // Java program to print the next greatest element in the array
3. import java.io.BufferedReader;
4. import java.io.InputStreamReader;
5. import java.util.Stack;
6.  
7. public class NextGreater {
8. // Method to print the next greatest element
9. static void printNextGreatest(int[] array){
10. Stack<Integer> stack=new Stack<>();
11. stack.push(array[0]);
12. int i,x;
13. for(i=1;i<array.length;i++){
14. if(stack.empty()){
15. stack.push(array[i]);
16. continue;
17. }
18. while (!stack.empty() && stack.peek()<array[i]){
19. x=stack.peek();
20. System.out.println(x+"---->"+array[i]);
21. stack.pop();
22. }
23. stack.push(array[i]);
24. }
25. while(!stack.empty()){
26. System.out.println(stack.pop()+"---->"+-1);
27. }
28. }
29. // Main method to read the array
30. public static void main(String[] args) {
31. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
32. int size;
33. System.out.println("Enter the size of the array");
34. try {
35. size = Integer.parseInt(br.readLine());
36. } catch (Exception e) {
37. System.out.println("Invalid Input");
38. return;
39. }
40. int[] array = new int[size];
41. System.out.println("Enter array elements");
42. int i;
43. for (i = 0; i < array.length; i++) {
44. try {
45. array[i] = Integer.parseInt(br.readLine());
46. } catch (Exception e) {
47. System.out.println("Invalid element. Enter it again");
48. i--;
49. }
50. }
51. printNextGreatest(array);
 52. }
53. }

Program Explanation
1. In function printNextGreatest(), a new stack is created through the statement
Stackstack=new Stack<>()
and the first element of the array is pushed onto the stack.
2. The loop for(i=1;i<array.length;i++) is used to iterate through the array.
3. Firstly, it is checked if the stack is empty if it is then the current array element is added to
the stack.
4. The nested loop while (!stack.empty() && stack.peek()<array[i]), checks if the element at
the top of the stack is less than the current array element.
5. If it is, then array[i] is the next greater element, for the element at the top of the stack.
6. At the end of each iteration of while loop, the element is popped from the stack.
7. At the end of each iteration of for loop, the current element is pushed onto the stack.
8. Finally, the last while loop is used, to print all the elements having no next greater
element.
advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
4
Enter array elements
6
4
5
7
4---->5
5---->7
6---->7
7---->-1
 
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
1---->2
2---->3
3---->4
4---->5
5---->-1

Sanfoundry Global Education & Learning Series – Java Programs.

Java Program to Find the Minimum Distance between Array

Elements
This is the Java Program to Find the Minimum Distance between Array Elements.

Problem Description
Given an array of n elements, and two integers say x and y, present in the array, find out
the minimum distance between x and y in the array, that is the number of elements between
x and y, including y. If the elements are not present print infinite value.

Example:
ArrayOne = [1, 2, 3, 4, 5, 6] 
x = 2
y = 5
Output
3

Problem Solution
Check for the first occurrence of x or y in the array and store that index in a variable say
z. Now continue traversing the array, if you find x or y, and it is not equal to the element at
z, then update the minimum distance. Finally, update the index in variable z.

Program/Source Code
Here is the source code of the Java Program to Find the Minimum Distance between Array
Elements. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. // Java Program to Find the Minimum Distance between Array Elements
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class MinimumDistance {
8. // Function to calculate the minimum distance
9. static int minimumDistance(int[] array,int x,int y){
10. int prev,i=0;
11. prev = 0;
12. int dist = Integer.MAX_VALUE;
13. for(i=0; i<array.length; i++){
14. if(array[i] == x || array[i] == y){
15. prev = i;
16. break;
17. }
18. }
19. for(i=prev+1; i<array.length; i++){
20. if(array[i] == x || array[i] == y){
21. if(array[i] != array[prev] && (i-prev) < dist)
22. {
23. dist = i-prev;
24. prev = i;
25. }
26. else{
27. prev = i;
28. }
29. }
30. }
31. return dist;
32. }
33. // Function to read input and display the output
34. public static void main(String[] args) {
35. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
36. int size;
37. System.out.println("Enter the size of the array");
38. try {
39. size = Integer.parseInt(br.readLine());
40. } catch (Exception e) {
41. System.out.println("Invalid Input");
42. return;
43. }
44. int[] array = new int[size];
45. System.out.println("Enter array elements");
 46. int i;
47. for (i = 0; i < array.length; i++) {
48. try {
49. array[i] = Integer.parseInt(br.readLine());
50. } catch (Exception e) {
51. System.out.println("An error Occurred");
52. }
53. }
54. int x,y;
55. System.out.println("Enter the numbers between which" +
56. " the distance is to be calculated");
57. try {
58. x = Integer.parseInt(br.readLine());
59. y = Integer.parseInt(br.readLine());
60. } catch (Exception e) {
61. System.out.println("Invalid Input");
62. return;
63. }
64. int output = minimumDistance(array,x,y);
65. System.out.println("The minimum distance is " + output);
66. }
67. }

Program Explanation
1. In function minimumDistance(), the variable dist is initialized to Integer.MAX_VALUE.
2. The first loop for(i=0; i<array.length; i++) is used to find the first occurrence of either
element x or y and store that index in variable prev.
3. The second loop for(i=prev+1; i<array.length; i++) traverses through the remaining part.
4. The conditions if(array[i] == x || array[i] == y) { if(array[i] != array[prev] && (i-prev) < dist),
first checks for x or y.
5. When found it compares the element with the element at index prev. If they are not the
same, then the dist is updated accordingly.

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Positive Test Case):
 
Enter the size of the array
6
Enter array elements
1
2
3
4
5
6
Enter the numbers between which the distance is to be calculated
2
5
The minimum distance is 3
 
Case 2 (Negative Test Case):
 
Enter the size of the array
5
Enter array elements
9
8
7
6
5
Enter the numbers between which the distance is to be calculated
1
2
The minimum distance is 2147483647
 
Case 3 (Positive Test Case - another example):
 
Enter the size of the array
8
Enter array elements
12
2
45
57
7
54
3
2
Enter the numbers between which the distance is to be calculated
2
3
The minimum distance is 1

Java Program to Merge Two Arrays Without Extra Space in

Order
This is the Java Program to Merge Two Arrays Without Extra Space in Order.

Problem Description
Given two sorted arrays, merge both the arrays in order without using extra space.
Example:
ArrayOne = [ 2, 3, 7, 8, 9] 
ArrayTwo = [-2, -1, 1, 4, 5]

Output
ArrayOne = [-2, -1,, 1, 2, 3] ArrayTwo = [4, 5, 7, 8, 9]

Problem Solution
Let the two sorted arrays are arrayOne and arrayTwo. Pick the last element of the
arrayTwo and search for any element in an arrayOne which is greater than the element
selected. If the search is successful we place the element picked in its correct position.
Finally, the last element of arrayOne is placed in its correct position in arrayTwo, to maintain
the sorted order.

Program/Source Code
Here is the source code of the Java Program to Merge Two Arrays Without Extra Space in
Order. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows
7. The program output is also shown below.
1.  
2. // Java Program to Merge Two Arrays Without Extra Space in Order
3. import java.io.BufferedReader;
4. import java.io.InputStreamReader;
5. import java.util.Arrays;
6.  
7. public class InplaceMerge {
8. // Function to merge the arrays in place
9. static void inPlaceMerge(int[] arrayOne,int[] arrayTwo){
10. int i,j,temp;
11. for(i=arrayTwo.length - 1;i>=0;i--){
12. temp = arrayOne[arrayOne.length-1];
13. for(j=arrayOne.length-2; j>=0 && arrayTwo[i] < arrayOne[j];j--)
{
14. arrayOne[j+1] = arrayOne[j];
15. }
16.  
17. if(j!=arrayOne.length-2 || temp > arrayTwo[i]){
18. arrayOne[j+1] = arrayTwo[i];
19. arrayTwo[i] = temp;
20. }
21. }
22. }
23. // Function to read input and display the output
24. public static void main(String[] args) {
25. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
26. int size,size1;
27. System.out.println("Enter the size of the two arrays");
28. try {
29. size = Integer.parseInt(br.readLine());
30. size1 = Integer.parseInt(br.readLine());
31. } catch (Exception e) {
32. System.out.println("Invalid Input");
33. return;
34. }
35. int[] arrayOne = new int[size];
36. int[] arrayTwo = new int[size1];
37. System.out.println("Enter the first array elements");
38. int i;
39. for (i = 0; i < arrayOne.length; i++) {
40. try {
41. arrayOne[i] = Integer.parseInt(br.readLine());
42. } catch (Exception e) {
43. System.out.println("An error occurred");
44. }
45. }
46. System.out.println("Enter the second array elements");
47. for (i = 0; i < arrayTwo.length; i++) {
48. try {
49. arrayTwo[i] = Integer.parseInt(br.readLine());
50. } catch (Exception e) {
51. System.out.println("An error occurred");
52. }
53. }
54. Arrays.sort(arrayOne);
55. Arrays.sort(arrayTwo);
56. System.out.println("Initially arrays are");
57. System.out.println("Array One");
58. System.out.println(Arrays.toString(arrayOne));
59. System.out.println("\nArray Two");
60. System.out.println(Arrays.toString(arrayTwo));
61. inPlaceMerge(arrayOne,arrayTwo);
62. System.out.println("\nArrays after merging are");
63. System.out.println("\nArray One");
 64. System.out.println(Arrays.toString(arrayOne));
65. System.out.println("\nArray Two");
66. System.out.println(Arrays.toString(arrayTwo));
67. }
68. }

Program Explanation
1. In function inPlaceMerge(), the loop for(i=arrayTwo.length – 1;i>=0;i–) traverses the
second array from right to left.
2. The variable temp stores the last element of the arrayOne.
3. The loop for(j=arrayOne.length-2; j>=0 && arrayTwo[i] < arrayOne[j];j–) moves each
arrayOne element one position ahead until correct position for arrayOne[i] is not found.
4. Finally, the condition if(j!=arrayOne.length-2 || temp > arrayTwo[i]), checks if any
elements were shifted.
5. If it is true, then the elements are placed into their correct position.
advertisement

Time Complexity: O(n ) where n is the number of elements in the array.

2

Runtime Test Cases

 
Case 1 (Simple Test Case - equal sized arrays):
 
Enter the size of the two arrays
5
5
Enter the first array elements
2
3
7
8
9
Enter the second array elements
-2
-1
1
4
5
Initially arrays are
Array One
[2, 3, 7, 8, 9]
 
Array Two
[-2, -1, 1, 4, 5]
 
Arrays after merging are
 
Array One
[-2, -1, 1, 2, 3]
 
Array Two
[4, 5, 7, 8, 9]
 
Case 2 (Simple Test Case - Unequal Sized arrays):
 
Enter the size of the two arrays
3
4
Enter the first array elements
6
7
8
Enter the second array elements
1
2
3
4
Initially arrays are
Array One
[6, 7, 8]
 
Array Two
[1, 2, 3, 4]
 
Arrays after merging are
 
Array One
[1, 2, 3]
 
Array Two
[4, 6, 7, 8]
 
Case 3 (Simple Test Case - Unequal sized reverse sorted arrays):
 
Enter the size of the two arrays
3
2
Enter the first array elements
5
4
3
Enter the second array elements
2
1
Initially arrays are
Array One
[3, 4, 5]
 
Array Two
[1, 2]
 
Arrays after merging are
 
Array One
[1, 2, 3]
 
Array Two
[4, 5]

Java Program to Determine if 2 Strings are Cyclic Permutations

of Each Other
This is the Java Program to Determine if 2 Strings are Cyclic Permutations of Each Other.

Problem Description
Given two different strings of the same length, find out if they are cyclic permutations of
each other, that is one string can be transformed into another, by cyclically rotating its
elements.

Example:
String str =”ABCD”;
String str2 = “CDAB”;

Output = “Yes”

Problem Solution
Concatenate any one of the string to itself, let the concatenated string be str3. Now, check
whether the other string is a substring of str3, if it is then str and str2 are cyclic permutations
of one another, otherwise they aren’t.

Program/Source Code
Here is the source code of the Java Program to Determine if 2 Strings are Cyclic
Permutations of Each Other. The program is successfully compiled and tested using IDE
IntelliJ Idea in Windows 7. The program output is also shown below.
1.  
2. // Java Program to Determine if 2 Strings are Cyclic Permutations of Each
Other
3.  
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7.  
 8. public class StringRotation {
9. // Function to read input and display the output
10. public static void main(String[] args) {
11. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
12. String str;
13. System.out.println("Enter the string");
14. try {
15. str = br.readLine();
16. } catch (Exception e) {
17. System.out.println("An I/O error occurred");
18. return;
19. }
20. String str2;
21. System.out.println("Enter the second string");
22. try {
23. str2 = br.readLine();
24. } catch (Exception e) {
25. System.out.println("An I/O error occurred");
26. return;
27. }
28. if(str.length() != str2.length())
29. {
30. System.out.println("\nNo");
31. return;
32. }
33. String str1=str;
34. str1 += str;
35. if(str1.indexOf(str2)!=-1)
36. {
37. System.out.println("\nYes");
38. }
39. else{
40. System.out.println("\nNo");
41. }
42. }
43. }

Program Explanation
1. In main() function, firstly both the strings are entered.
2. Then the lengths of the two string are compared if they are unequal then No is displayed.
3. Otherwise, the first string is concatenated with itself and stored in the variable in str1.
4. Now, it is checked whether the second string is a subset of str1 using the command
str1.indexOf(str2).
5. If the condition is true, then Yes is displayed, otherwise, No is displayed.

Time Complexity: O(1).

advertisement

Runtime Test Cases

 
Case 1 (Positive Test Case):
 
Enter the string
ABCD
Enter the second string
CDAB
 
Yes
 
Case 2 (Negative Test Case):
 
Enter the string
ABCD
Enter the second string
DCAB
 
No
 
Case 3 (Positive Test Case - another example):
 
Enter the string
XYZ
Enter the second string
ZXY
 
Yes

Java Program to Find the Largest Square Matrix with all 1’s
This is the Java Program to Find the Largest Square Matrix with all 1’s.

Problem Description
Given a boolean matrix of 0’s and 1’s, find and print the largest square sub-matrix whose all
the entries are 1.
Example:
Matrix:
0 0 1 1
0 1 1 1
0001

Output:
1 1
11

Problem Solution
Create a new matrix, say L of the same size. Initialize the first row and column of this new
matrix with the first row and column of the original matrix. The values in this matrix
represent the largest square sub-matrix whose all the entries are 1 that is present up to the
indexes lets say, i and j. Traverse through the original matrix, if its entry is 1,that is  M[i][j] =
1, then L[i][j] = min(L[i][j-1],L[i-1][j],L[i-1][j-1]) + 1, otherwise L[i][j] = 0. Find out the
maximum value in matrix L and using it print the largest square sub-matrix.

Program/Source Code
Here is the source code of the Java Program to Find the Largest Square Matrix with all 1’s.
The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Find the Largest Square Matrix with all 1's
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class Max1SquareMatrix {
8. // Function to find the largest square submatrix and display it.
9. static void printSquareSubMatrix(int[][] matrix){
10. int m,n;
11. n=matrix.length;
12. m=matrix[0].length;
13. int[][] L = new int[n][m];
14. int i,j;
15. for(i=0; i<m; i++){
16. L[0][i] = matrix[0][i];
17. }
18. for(i=0; i<n; i++){
19. L[i][0] = matrix[i][0];
20. }
21. i=1;
22. while(i<n){
23. j=1;
24. while(j<m){
25. if(matrix[i][j] == 1){
26. L[i][j] = Math.min(L[i][j-1],
27. Math.min(L[i-1][j-1],L[i-1][j]))+1;
28. }
29. else{
30. L[i][j] = 0;
31. }
32. j++;
33. }
34. i++;
35. }
36. int max = L[0][0];
37. int max_i,max_j;
38. max_i=max_j=0;
39. i=0;
40. while(i<n){
41. j=0;
42. while(j<m){
43. if(L[i][j] > max){
44. max = L[i][j];
45. max_i = i;
46. max_j = j;
47. }
48. j++;
49. }
50. i++;
51. }
52. System.out.println("Maximum Sub-matrix");
53. i = max_i;
54. while(i>(max_i-max)){
55. j = max_j;
56. while(j>(max_j-max)){
57. System.out.print(matrix[i][j]);
58. j--;
59. }
60. System.out.println();
61. i--;
62. }
63. }
 64. // Function to read user input
65. public static void main(String[] args) {
66. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
67. int rows,columns;
68. try{
69. System.out.println("Enter the number of rows");
70. rows = Integer.parseInt(br.readLine());
71. System.out.println("Enter the number of columns");
72. columns = Integer.parseInt(br.readLine());
73. }
74. catch(Exception e){
75. System.out.println("An error occurred");
76. return;
77. }
78. int[][] matrix = new int[rows][columns];
79. int i,j;
80. System.out.println("Enter the Boolean Matrix");
81. try{
82. for(i=0; i<rows; i++){
83. for(j=0; j<columns; j++){
84. matrix[i][j] = Integer.parseInt(br.readLine());
85. }
86. }
87. }catch (Exception e){
88. System.out.println("An error occurred");
89. return;
90. }
91. System.out.println("The matrix is");
92. for(i=0; i<rows; i++){
93. for(j=0; j<columns; j++){
94. System.out.print(matrix[i][j]);
95. }
96. System.out.println();
97. }
98. if(rows > 0 && columns > 0)
99. printSquareSubMatrix(matrix);
100. }
101. }

Program Explanation
1. In function printSquareSubMatrix(), a new matrix L is created and its first row and column
are initialized with first row and column of the original matrix, using the first two loops.
2. The set of nested loops while(i<n){ while(j<m) are used to compute order of the largest
sub-square matrix.
3. The loops while(i<n){ while(j<m), find out the order of the largest square sub-matrix and
the maximum row and column index are stored in max_i and max_j.
4. The loops while(i>(max_i-max)){while(j>(max_j-max)) then print the sub matrix.

Time Complexity: O(nm) where n is the number of rows and m is the number of columns
in the matrix respectively.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the number of rows
3
Enter the number of columns
4
Enter the Boolean Matrix
0
0
1
1
0
1
1
1
0
0
0
1
The matrix is
0011
0111
0001
Maximum Sub-matrix
11
11
 
Case 2 (Simple Test Case - another example):
 
Enter the number of rows
4
Enter the number of columns
4
Enter the Boolean Matrix
0
1
1
1
0
1
1
1
0
1
1
1
0
1
0
1
The matrix is
0111
0111
0111
0101
Maximum Sub-matrix
111
111
111

Java Program to Shift the 0’s in an Array to the Beginning

This is the Java Program to Shift the 0’s in an Array to the Beginning.

Problem Description
Given an array of integers, shift all the zeroes present in it to the beginning.
Example:

Array = [1 0 2 3 0 4]

Output
Array = [0 0 1 2 3 4]

Problem Solution
Traverse the array from beginning to end, and whenever a zero is encountered, move it to
the position of the first nonzero element, in the array.

Program/Source Code
Here is the source code of the Java Program to Shift the 0’s in an Array to the Beginning.
The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Shift the 0's in an Array to the Beginning
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class ShiftZeroesBeginning {
8. // Function to shift 0's in the beginning
9. static void inTheBeginning(int[] array){
10. int startIndex=0;
11. int i,temp,j;
12. for(i=1; i<array.length; i++){
13. if(array[i] == 0){
14. for(j=i; j>startIndex;j--){
15. temp = array[j];
16. array[j] = array[j-1];
17. array[j-1] = temp;
18. }
19. startIndex++;
20. }
21. }
22. }
23. // Function to read input and display the final array
24. public static void main(String[] args){
25. BufferedReader br = new BufferedReader
26. (new InputStreamReader(System.in));
27. int size;
28. System.out.println("Enter the size of the array");
29. try {
30. size = Integer.parseInt(br.readLine());
31. } catch (Exception e) {
32. System.out.println("Invalid Input");
33. return;
34. }
35. int[] array = new int[size];
36. System.out.println("Enter array elements");
37. int i;
38. for (i = 0; i < array.length; i++) {
39. try {
40. array[i] = Integer.parseInt(br.readLine());
41. } catch (Exception e) {
42. System.out.println("An error occurred");
43. return;
 44. }
45. }
46. inTheBeginning(array);
47. System.out.println("The array after shifting the" +
48. " zeroes in the beginning is");
49. for(i=0; i<array.length; i++){
50. System.out.print(array[i] + " ");
51. }
52. }
53. }

Program Explanation
1. In function inTheBeginning(), the loop for(i=0;i<array.length;i++) is used to iterate through
the array.
2. The statement if(array[i]==0) looks for elements whose value is zero.
3. Any zero element is shifted to the position of the first non-zero element using the nested
loop for(j=i;j>startIndex;j–).
4. The variable startIndex serves as the position of first non-zero element.
5. Consequently, all the zeroes get shifted to the beginning of the array.
advertisement

Time Complexity: O(n ) where n is the number of elements in the array.

2

Runtime Test Cases

 
Case 1 (Simple test Case):
 
Enter the size of the array
6
Enter array elements
1
0
2
3
0
4
The array after shifting the zeroes in the beginning is
0 0 1 2 3 4
 
Case 2 (Simple test Case - another example):
 
Enter the size of the array
6
Enter array elements
6
7
8
9
0
0
The array after shifting the zeroes in the beginning is
0 0 6 7 8 9

Java Program to Check if an Array is Strictly Decreasing

This is the Java Program to Check if an Array is Strictly Decreasing.

Problem Description
Given an array of integers check whether it is strictly decreasing or not.
A strictly decreasing array is an array whose each element is smaller than it’s
preceding element.

Example:
Array = [5, 4, 3, 2, 1]

Output: Array is strictly decreasing.

Problem Solution
Iterate through the array and check whether the current array element, is smaller than its
preceding element if all the elements are smaller than its preceding element return true,
else return false.

Program/Source Code
Here is the source code of the Java Program to Check if an Array is Strictly Decreasing.
The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Check if an Array is Strictly Decreasing
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class StrictlyDecreasing {
8. // Function to check array is strictly decreasing
9. static boolean checkStrictlyDecreasing(int[] array){
10. boolean result=true;
11. int i;
12. for(i=0;i<array.length-1;i++){
13. if(array[i]<=array[i+1])
14. {
15. result=false;
16. break;
17. }
18. }
19. return result;
20. }
21. // Function to read input and decreasing output
22. public static void main(String[] args) {
23. BufferedReader br= new BufferedReader(new
InputStreamReader(System.in));
24. int size;
25. System.out.println("Enter the size of the array");
26. try{
27. size=Integer.parseInt(br.readLine());
28. }
29. catch(Exception e)
30. {
31. System.out.println("Invalid Input");
32. return;
33. }
34. int[] array=new int[size];
35. System.out.println("Enter array elements");
36. int i;
37. for(i=0;i<array.length;i++){
38. try{
39. array[i]=Integer.parseInt(br.readLine());
40. }
41. catch(Exception e)
42. {
43. System.out.println("An error occurred");
44. }
45. }
46. boolean result=checkStrictlyDecreasing(array);
47. if(result){
48. System.out.println("Array is strictly decreasing");
49. }
50. else{
51. System.out.println("Array is not strictly decreasing");
52. }
53. }
 54. }

Program Explanation
1. In function checkStrictlyDecreasing(), the loop for(i=0; i<array.length; i++) is used to
iterate through the array.
2. The condition if(array[i] <= array[i+1]) checks if the current element is smaller than its
following element.
3. If the condition is true, flag is set to false, indicating that the array is not strictly
decreasing.
4. Finally, the flag variable is returned.
advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Positive Test Case):
 
Enter the size of the array
5
Enter array elements
5
4
3
2
1
Array is strictly decreasing
 
Case 2 (Negative Test Case):
 
Enter the size of the array
8
Enter array elements
6
5
5
4
3
2
1
1
Array is not strictly decreasing

Java Program to Find the Largest sub-Array consisting of Equal

Number of 0s and 1s
This is the Java Program to Find the Largest sub-Array consisting of Equal Number of 0’s
and 1’s.

Problem Description
Given an array, find out the longest subarray consisting of the equal number of zeroes and
ones.

Example:
ArrayOne = [1, 2, 0, 5, 6, 0, 1, 0]

Output
1205601

Problem Solution
Maintain two variables start and end to store the starting and ending index of the
subarray and initialize them to -1. Also, create a boolean variable flag mark it to be true.
Iterate through the array, and check if the element is 0 or 1 if it is one and the flag is true set
the flag to false, otherwise set the flag to true and update the variables starting and ending
indexes.

Program/Source Code
Here is the source code of the Java Program to Find the Largest sub-Array consisting of
Equal Number of 0’s and 1’s. The program is successfully compiled and tested using IDE
IntelliJ Idea in Windows 7. The program output is also shown below.
1.  
2. // Java Program to Find the Largest sub-Array
3. // Consisting of Equal Number of 0's and 1's
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class EqualZeroesAndOnes {
8. // Function to find out the largest subarray having equal zeroes and
ones.
9. static int[] largestSubarray(int[] array){
10. int[] index = new int[2];
11. int start,end,i;
12. start = end = -1;
13. boolean flag = true;
14. for(i=0; i<array.length; i++){
15. if (array[i] == 0 || array[i] == 1){
16. if(start == -1){
17. start = i;
18. flag = false;
19. }
20. else if (flag){
21. flag = false;
22. }
23. else{
24. flag = true;
25. end = i;
26. }
27. }
28. }
29. if(start != -1 && end != -1){
30. index[0] = start;
31. index[1] = end;
32. }
33. return index;
34. }
35. // Function to read the input and to display the subarray
36. public static void main(String[] args) {
37. BufferedReader br = new BufferedReader
38. (new InputStreamReader(System.in));
39. int size;
40. System.out.println("Enter the size of the array");
41. try {
42. size = Integer.parseInt(br.readLine());
43. } catch (Exception e) {
44. System.out.println("Invalid Input");
45. return;
46. }
47. int[] array = new int[size];
48. System.out.println("Enter array elements");
49. int i;
50. for (i = 0; i < array.length; i++) {
51. try {
52. array[i] = Integer.parseInt(br.readLine());
53. } catch (Exception e) {
54. System.out.println("An error occurred");
55. }
56. }
57. int[] index = largestSubarray(array);
 58. if(index[0] == 0 && index[1] == 0)
59. System.out.println("No such subarray exists");
60. else{
61. for(i=index[0]; i<=index[1]; i++){
62. System.out.print(array[i] + " ");
63. }
64. }
65. }
66. }

Program Explanation
1. In function largestSubarray(), the variables start and end are initialized to -1 and flag is
set to true.
2. The loop for(i=0; i<array.length; i++) is used to iterate through the array.
3. The condition if(array[i] == 0 || array[i] == 1) checks for zero and one.
4. The nested condition if(start == -1) checks if the current element is the first element of the
subarray.
5. The nested condition else if(flag) checks if the number of zeroes and ones were
previously equal.
6. The else part sets the end variable to point to the last entry of the subarray.

Time Complexity: O(n) where n is the number of elements in the array.

advertisement

Runtime Test Cases

 
Case 1 (Positive Test Case):
 
Enter the size of the array
8
Enter array elements
1
2
0
5
6
0
1
0
1 2 0 5 6 0 1
 
Case 2 (Negative Test Case):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
No such subarray exists

Java Program to Find the Number of Unique Words

This is the Java Program to Find the Number of Unique Words.

Problem Description
Given a string, in which various words are separated by whitespace. Print the count of the
unique words present in it, that is the words whose frequency is 1.

Example:
String str =”Java is great C++ is also great”;

Output = 3

Problem Solution
Split the string into various substrings based on the delimiter whitespace. Now find the
frequency of each substring and maintain a count of substrings whose frequency is 1.

Program/Source Code
Here is the source code of the Java Program to Find the Number of Unique Words. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Find the Number of Unique Words
3.  
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7.  
8. public class NumberOfUniqueWords {
9. // Function to calculate the number of unique words
10. static int calculateNoOfUniqueWords(String str) {
11. String[] words = str.split(" ");
12. boolean[] array = new boolean[words.length];
 13. int j, i = 0;
14. int count = 0;
15. for (i = 0; i < words.length; i++) {
16. if (!array[i]) {
17. count++;
18. for (j = i + 1; j < words.length; j++) {
19. if (words[j].compareTo(words[i]) == 0) {
20. array[j] = true;
21. count--;
22. }
23. }
24. }
25. }
26. return count;
27. }
28. // Function to read input and display the output
29. public static void main(String[] args) {
30. BufferedReader br = new BufferedReader
31. (new InputStreamReader(System.in));
32. String str;
33. System.out.println("Enter the string");
34. try {
35. str = br.readLine();
36. } catch (IOException e) {
37. System.out.println("An I/O error occurred");
38. return;
39. }
40. int count = calculateNoOfUniqueWords(str);
41. System.out.println("Total number of unique words in \"" +
42. str + "\" are " + count);
43. }
44. }

Program Explanation
1. In function calculateNoOfUniqueWords, the split method is used to split the string into
various substrings, which are separated by whitespaces.
2. An array of boolean values is maintained to avoid checking the repeated substring more
than once.
3. The loop for (i = 0; i < words.length; i++) is used to iterate through the array of substrings.
4. The condition if(!array[i]), checks whether the substring is already checked or not.
5. The nested loop checks if the substring array[i] is repeated or not.
6. If the substring is not repeated, the variable count is incremented.
7. Finally, the variable count is returned.

Time Complexity: O(n ) where n is the length of the string.

2

advertisement

Runtime Test Cases

 
Case 1 (Average Case):
 
Enter the string
Java is great C++ is also great
Total number of unique words in "Java is great C++ is also great" are 3
 
Case 2 (Best Case):
 
Enter the string
I am am I
Total number of unique words in "I am am I" are 0
 
Case 3 (Worst Case):
 
Enter the string
We are here
Total number of unique words in "We are here" are 3

Java Program to Shift the 0’s in an Array to the End

This is the Java Program to Shift the 0’s in an Array to the End.

Problem Description
Given an array of integers, shift all the zeroes present in it to the end.
Example:

Array = [1 0 2 3 0 4]

Output
Array = [1 2 3 4 0 0]

Problem Solution
Traverse the array from beginning to end, and whenever a nonzero is encountered, move it
to the position of the first element having a zero value, in the array.

Program/Source Code
Here is the source code of the Java Program to Shift the 0’s in an Array to the End. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Shift the 0's in an Array to the End
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class ShiftZeroesEnd {
8. // Function to shift the zeroes in the end
9. static void inTheEnd(int[] array){
10. int startIndex = 0;
11. int i,j,temp;
12. for(i=0;i<array.length;i++){
13. if(array[i] != 0){
14. for(j=i; j>startIndex;j--){
15. temp = array[j];
16. array[j] = array[j-1];
17. array[j-1] = temp;
18. }
19. startIndex++;
20. }
21. }
22. }
23. // Function to read user input and display the output
24. public static void main(String[] args){
25. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
26. int size;
27. System.out.println("Enter the size of the array");
28. try {
29. size = Integer.parseInt(br.readLine());
30. } catch (Exception e) {
31. System.out.println("Invalid Input");
32. return;
33. }
34. int[] array = new int[size];
35. System.out.println("Enter array elements");
36. int i;
37. for (i = 0; i < array.length; i++) {
38. try {
 39. array[i] = Integer.parseInt(br.readLine());
40. } catch (Exception e) {
41. System.out.println("An error occurred");
42. return;
43. }
44. }
45. inTheEnd(array);
46. System.out.println("The array after shifting the zeroes in the end
is");
47. for(i=0; i<array.length; i++){
48. System.out.print(array[i] + " ");
49. }
50. }
51. }

Program Explanation
1. In function inTheEnd(), the loop for(i=0;i<array.length;i++) is used to iterate through the
array.
2. The statement if(array[i]!=0) looks for non-zero elements.
3. Any non-zero element is shifted to the position of the first zero element using the nested
loop for(j=i;j>startIndex;j–).
4. Consequently, all the zeroes get shifted to the end of the array.
advertisement

Time Complexity: O(n ) where n is the number of elements in the array.

2

Runtime Test Cases

 
Case 1 (Simple test Case):
 
Enter the size of the array
6
Enter array elements
1
0
2
3
0
4
The array after shifting the zeroes in the end is
1 2 3 4 0 0
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
6
Enter array elements
6
7
8
9
0
0
The array after shifting the zeroes in the end is
6 7 8 9 0 0

Java Program to Print Even Elements at Odd Index Number

This is the Java Program to Print Even Elements at Odd Index Number.

Problem Description
Given an array of integers, print the even numbers present at odd index numbers.
Example:

Array = [2,1,4,4,5,7]

Output = 4

Problem Solution
Iterate through the array, and check whether the current index is even or odd if it is odd,
then check the element at that index to be even or odd, print the element if it is even.

Program/Source Code
Here is the source code of the Java Program to Print Even Elements at Odd Index Number.
The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Print Even Elements at Odd Index Number
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class EvenIndexedOddElements {
8. // Function to even numbers present at odd index
9. static void printEvenIndexedElements(int[] array){
10. int i=0;
11. for(i=0; i<array.length; i++){
 12. if(i%2 != 0 && array[i]%2 ==0){
13. System.out.print(array[i] + " ");
14. }
15. }
16. }
17. // Function to read input
18. public static void main(String[] args) {
19. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
20. int size;
21. System.out.println("Enter the size of the array");
22. try {
23. size = Integer.parseInt(br.readLine());
24. } catch (Exception e) {
25. System.out.println("Invalid Input");
26. return;
27. }
28. int[] array = new int[size];
29. System.out.println("Enter array elements");
30. int i;
31. for (i = 0; i < array.length; i++) {
32. try {
33. array[i] = Integer.parseInt(br.readLine());
34. } catch (Exception e) {
35. System.out.println("An error occurred");
36. return;
37. }
38. }
39. System.out.println("Output");
40. printEvenIndexedElements(array);
41. }
42. }

Program Explanation
1. In function printEvenIndexedElements, the loop for(i=0; i<array.length; i++) is used to
iterate through the array.
2. The condition if(i%2!=0 && array[i]%2==0), checks whether the current index is odd and
the element at that index is even.
3. The element is printed if the above mentioned condition is true.
advertisement
Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
6
Enter array elements
2
1
4
4
5
7
Output
4
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
8
Enter array elements
12
34
45
32
76
55
567
346
Output
34 32 346

Java Program to Print Odd Elements at Even Index Number

This is the Java Program to Print Odd Elements at Even Index Number.

Problem Description
Given an array of integers, print the odd numbers present at even index numbers.
Example:

Array = [2,1,4,4,5,7]

Output = 5

Problem Solution
Iterate through the array, and check whether the current index is even or odd if it is
even, then check the element at that index to be even or odd, print the element if it is odd.

Program/Source Code
Here is the source code of the Java Program to Print Odd Elements at Even Index Number.
The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Print Odd Elements at Even Index Number
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class EvenIndexedOddElements {
8. // Function to odd numbers present at even index
9. static void printEvenIndexedElements(int[] array){
10. int i=0;
11. for(i=0; i<array.length; i++){
12. if(i%2 == 0 && array[i]%2 !=0){
13. System.out.print(array[i] + " ");
14. }
15. }
16. }
17. // Function to read input
18. public static void main(String[] args) {
19. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
20. int size;
21. System.out.println("Enter the size of the array");
22. try {
23. size = Integer.parseInt(br.readLine());
24. } catch (Exception e) {
25. System.out.println("Invalid Input");
26. return;
27. }
28. int[] array = new int[size];
29. System.out.println("Enter array elements");
30. int i;
31. for (i = 0; i < array.length; i++) {
32. try {
33. array[i] = Integer.parseInt(br.readLine());
 34. } catch (Exception e) {
35. System.out.println("An error occurred");
36. return;
37. }
38. }
39. System.out.println("Output");
40. printEvenIndexedElements(array);
41. }
42. }

Program Explanation
1. In function printEvenIndexedElements, the loop for(i=0; i<array.length; i++) is used to
iterate through the array.
2. The condition if(i%2==0 && array[i]%2!=0), checks whether the current index is even and
the element at that index is odd.
3. The element is printed if the above mentioned condition is true.
advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
6
Enter array elements
2
1
4
4
5
7
Output
5
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
8
Enter array elements
12
34
45
32
76
55
567
346
Output
45 567

Java Program to Find the Column with the Maximum Number of

1’s in a Sorted Matrix
This is the Java Program to Find the Column with the Maximum Number of 1’s in a Sorted
Matrix.

Problem Description
Given a boolean matrix of 0’s and 1’s, where each column is sorted, print the first column
with the maximum number of 1’s.
Example:
Matrix:
0 0 0 1
0 0 1 1
0 1 1 1
1111

Output:
1111

Problem Solution
Iterate through the first column to find the index of the topmost one in it. For each of the
next column, if the element at the index before the topmost one is zero, then skip that
column, otherwise update the index for topmost one.

Program/Source Code
Here is the source code of the Java Program to Find the Column with the Maximum
Number of 1s in a Sorted Matrix. The program is successfully compiled and tested using
IDE IntelliJ Idea in Windows 7. The program output is also shown below.
1.  
2. //Java Program to Find the Column with the Maximum Number of 1s in a Sorted
Matrix
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class ColumnWithMaxOne {
8. // Function to print the column with maximum number of 1's.
9. static void printColumn(int[][] matrix){
10. int i,j,columnnumber = -1;
11. int topmost = -1;
12. for(i=0;i<matrix.length;i++){
13. if(matrix[i][0] == 1)
14. {
15. columnnumber = 0;
16. topmost = i;
17. break;
18. }
19. }
20. if(topmost == -1){
21. topmost = matrix.length;
22. }
23. for(i=1; i<matrix.length; i++){
24. int x = topmost-1;
25. while(x >= 0 && matrix[i][x] == 1){
26. columnnumber = i;
27. topmost = x;
28. x--;
29. }
30. }
31. if(columnnumber != -1) {
32. System.out.println("Column with maximum number of One's in " +
33. "Sorted Matrix is");
34. for (i = 0; i < matrix[columnnumber].length; i++) {
35. System.out.print(matrix[columnnumber][i] + " ");
36. }
37. }
38. else{
39. System.out.println("There is no column containing 1's");
40. }
41. }
42. // Function to read user input
43. public static void main(String[] args) {
44. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
45. int rows,columns;
46. try{
47. System.out.println("Enter the number of rows");
 48. rows = Integer.parseInt(br.readLine());
49. System.out.println("Enter the number of columns");
50. columns = Integer.parseInt(br.readLine());
51. }
52. catch(Exception e){
53. System.out.println("An error occurred");
54. return;
55. }
56. int[][] matrix = new int[rows][columns];
57. int i,j,prev;
58. prev=Integer.MIN_VALUE;
59. System.out.println("Enter the Sorted Matrix");
60. try{
61. for(i=0; i<rows; i++){
62. for(j=0; j<columns; j++){
63. matrix[i][j] = Integer.parseInt(br.readLine());
64. }
65. }
66. }catch (Exception e){
67. System.out.println("An error occurred");
68. return;
69. }
70. System.out.println("The matrix is");
71. for(i=0; i<rows; i++){
72. for(j=0; j<columns; j++){
73. System.out.print(matrix[i][j]);
74. }
75. System.out.println();
76. }
77. if(rows > 0 && columns >0)
78. printColumn(matrix);
79. }
80. }

Program Explanation
1. In function printColumn(), the variables columnnumber and topmost are initialized to -1.
2. The first loop for(i=0; i<matrix.length; i++), checks for 1 in first column,we set
columnnumber to 0 and topmost to i if 1 exists.
3. Using the condition if(topmost == -1) we check if the first column is full of zeroes, in this
case we set topmost to matrix.length;
4. The loop for(i=1; i<matrix.length; i++) is used to iterate through the remaining columns.
5. The nested loop while(x >= 0 && matrix[i][x] == 1), is used to check if the value in the
current column, at a higher position is 1. If it is the variables topmost and columnnumber are
updated. Here, variable x denotes the position and is initialised to topmost-1.
6. The condition if(columnnumber != -1) is used to display the column with maximum
number of 1’s, if there is any, otherwise, a suitable message is displayed.

Time Complexity: O(n+m) where n is the number of rows and m is the number of columns
in the matrix respectively.

Runtime Test Cases

 
Case 1 (Positive Test Case - each column with different number of 1's):
 
Enter the number of rows
4
Enter the number of columns
4
Enter the Sorted Matrix
0
0
0
1
0
0
1
1
0
1
1
1
1
1
1
1
The matrix is
0001
0011
0111
1111
Column with the maximum number of One's in Sorted Matrix is
1 1 1 1
 
Case 2 (Positive Test Case - two columns having same number of 1's):
 
Enter the number of rows
4
Enter the number of columns
4
Enter the Boolean Matrix
0
0
0
1
0
0
1
1
0
1
1
1
0
0
1
1
The matrix is
0000
0011
0111
0111
Column with the maximum number of One's in Sorted Matrix is
0 1 1 1
 
Case 3 (Negative Test Case - no column containing 1):
 
Enter the number of rows
3
Enter the number of columns
3
Enter the Boolean Matrix
0
0
0
0
0
0
0
0
0
The matrix is
000
000
000
There is no column containing 1's

Java Program to Find the Minimum Sum in a Contiguous Sub-

Array
This is the Java Program to Find the Minimum Sum in a Contiguous Sub-Array.

Problem Description
Given an array of integers, find the contiguous subarray, whose sum of the elements, is
minimum.
Example:

Array = [2 1 3 5 -2 1 -3 8]

Output
Subarray = [-2 1 -3]

Sum = -4

Problem Solution
The idea is to divide the array recursively into two equal parts. Find the middle index of
the array, recursively find the minimum sum subarray, in the left part and the right part, find
the minimum sum crossing subarray as well,finally return the subarray having the minimum
sum.

Program/Source Code
Here is the source code of the Java Program to Find the Minimum Sum in a Contiguous
Sub-Array. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Find the Minimum Sum in a Contiguous Sub-Array
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class MinSumSubarray {
8. // Function to find the crossing subarray with minimum sum
9. static int[] minCrossingSubarray(int[] array, int low, int mid, int
high){
10. int lsum,rsum;
11. lsum = rsum = Integer.MAX_VALUE;
12. int sum = 0;
13. int[] output = new int[3];
14. int i, maxleft, maxright;
15. maxleft = maxright = -1;
16. for(i=mid;i>=0;i--){
17. sum+=array[i];
18. if(sum < lsum){
19. lsum = sum;
20. maxleft = i;
21. }
22. }
23. sum = 0;
24. for(i=mid+1;i<=high;i++){
25. sum+=array[i];
26. if(sum < rsum){
27. rsum = sum;
28. maxright = i;
29. }
30. }
31. output[0] = maxleft;
32. output[1] = maxright;
33. output[2] = lsum+rsum;
34. return output;
35. }
36. // Function to recursively find minimum subarray in left and right
parts
37. static int[] minimumSumSubarray(int[] array, int low, int high){
38. int[] output = new int[3];
39. if(low == high){
40. output[0] = low;
41. output[1] = high;
42. output[2] = array[low];
43. return output;
44. }
45. int mid = (low+high)/2;
46. int[] output1 = minimumSumSubarray(array,low,mid);
47. int[] output2 = minimumSumSubarray(array,mid+1,high);
48. int[] output3 = minCrossingSubarray(array,low,mid,high);
49. if(output1[2] <= output2[2] && output1[2] <= output3[2])
50. return output1;
51. else if (output2[2] <= output1[2] && output2[2] <= output3[2])
52. return output2;
53. return output3;
54. }
55. // Fumction to read user input
56. public static void main(String[] args) {
57. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
58. int size;
59. System.out.println("Enter the size of the array");
 60. try {
61. size = Integer.parseInt(br.readLine());
62. } catch (Exception e) {
63. System.out.println("Invalid Input");
64. return;
65. }
66. int[] array = new int[size];
67. System.out.println("Enter array elements");
68. int i;
69. for (i = 0; i < array.length; i++) {
70. try {
71. array[i] = Integer.parseInt(br.readLine());
72. } catch (Exception e) {
73. System.out.println("An error Occurred");
74. }
75. }
76. int[] output = minimumSumSubarray(array, 0, array.length-1);
77. System.out.println("The minimum sum subarray is");
78. int x = 0;
79. for(i=output[0]; i<=output[1];i++){
80. System.out.print(array[i] + " ");
81. x+=array[i];
82. }
83. System.out.println("\nThe minimum sum is " + x);
84. }
85. }

Program Explanation
1. In function minCrossingSubarray(), the variables lsum and rsum are initialized to
Integer.MAX_VALUE.
2. The loop for(i=mid;i>=0; i–) is used to find the minimum sum subarray when moving from
the middle element towards the leftmost element.
3. The loop for(i=mid+1;i<=high; i++) is used to find the minimum sum subarray when
moving from the middle element towards the rightmost element.
4. Finally, the output array is updated to contain the index of the leftmost and rightmost
element, upto where the sum is maximum and the maximum sum is also stored in it as
(lsum + rsum).
5. In function minimumSumSubarray(), the condition if(low == high) checks if there is only
element, in the array.
6. If there is only one element, then the output array is updated as required.
7. Otherwise, the index of the middle element is calculated and the function
minimumSumSubarray() is recursively called on left and right halves.
8. Finally, the function minCrossingSubarray() is called and the output arrays returned from
the three calls are compared. The array containing the minimum sum is returned.
advertisement

Time Complexity: O(n*log(n)) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
8
Enter array elements
2
1
3
5
-2
1
-3
8
The minimum sum subarray is
-2 1 -3
The minimum sum is -4
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
7
Enter array elements
7
6
5
1
2
3
4
The minimum sum subarray is

Java Program to Remove Duplicates in a Sorted Array

This is the Java Program to Remove Duplicates in a Sorted Array.

Problem Description
Given a sorted array of integers, remove the duplicates of the elements from the array.
Example:

Array = [1 2 2 3 3 4]

Output
Array = [1 2 3 4]

Problem Solution
Traverse the array from beginning to end and in a variable, an index, where the element
having a duplicate will be copied. The idea is to copy each unique element to the
beginning of the array and print that part of the array.

Program/Source Code
Here is the source code of the Java Program to Remove Duplicates in a Sorted Array. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Remove Duplicates in a Sorted Array
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class RemoveDuplicates {
8. // Function to remove the duplicates
9. static int removeDuplicates(int[] array){
10. int replaceIndex = 0;
11. int i,j;
12. for(i=0; i<array.length; i++){
13. for(j=i+1; j<array.length; j++){
14. if(array[j]!=array[i]){
15. break;
16. }
17. }
18. array[replaceIndex++] = array[i];
19. i = j-1;
20. }
21. return replaceIndex;
22. }
23. // Function to read user input
 24. public static void main(String[] args) {
25. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
26. int size;
27. System.out.println("Enter the size of the array");
28. try {
29. size = Integer.parseInt(br.readLine());
30. } catch (Exception e) {
31. System.out.println("Invalid Input");
32. return;
33. }
34. int[] array = new int[size];
35. System.out.println("Enter array elements in sorted order");
36. int i;
37. for (i = 0; i < array.length; i++) {
38. try {
39. array[i] = Integer.parseInt(br.readLine());
40. } catch (Exception e) {
41. System.out.println("An error occurred");
42. return;
43. }
44. }
45. int index = removeDuplicates(array);
46. System.out.println("Array after removing duplicates is");
47. for(i=0; i<index; i++){
48. System.out.print(array[i] + " ");
49. }
50. }
51. }

Program Explanation
1. In function removeDuplicates(), we declare and initialize variable replaceIndex to 0.
2. The loop for(i=0; i<array.length; i++) is used to iterate through the array.
3. The nested loop for(j=i+1; j<array.length; j++) is used to check for duplicate elements, it
breaks out of the loop if the condition if(array[j]!=array[i]) is true.
4. Finally, array[i] is copied to position replaceindex and i is set to j-1, to avoid scanning
again through duplicate elements.
advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Positive Test Case - Involving Duplicates):
 
Enter the size of the array
6
Enter array elements in sorted order
1
2
2
3
3
4
Array after removing duplicates is
1 2 3 4
 
Case 2 (Negative test Case - Without Duplicates):
 
Enter the size of the array
4
Enter array elements in sorted order
4
3
2
1
Array after removing duplicates is
4 3 2 1
 
Case 3 (Positive Test Case - Another Example):
 
Enter the size of the array
7
Enter array elements in sorted order
1
3
3
3
4
5
6
Array after removing duplicates is
1 3 4 5 6

Java Program to Print the Longest Sub-Array that is Increasing

This is the Java Program to Print the Longest Sub-Array that is increasing.

Problem Description
Given an array of integers, find the longest contiguous subarray whose elements are
increasing, that is, the elements following the preceding elements in the subarray must be
greater than them.
Example:

Array = [5, 6, 3, 0, 7, 8, 9, 1, 2]

Output: 0 7 8 9

Problem Solution
Traverse the array from beginning to end and check for the first element which is
smaller than the element following it, from that index find out the subarray which is
increasing, if the current subarray length is greater than the previous subarray length, then
update the longest increasing subarray. Initially, the subarray would be of length one,
referring to the first element of the array.

Program/Source Code
Here is the source code of the Java Program to Print the Longest Sub-Array that is
Increasing. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Print the Longest Sub-Array that is Increasing
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class LongestIncreasingSubarray {
8. // Function to calculate the longest increasing subarray
9. static int[] longestIncreasingSubarray(int[] array){
10. int[] index = new int[2];
11. int i,j,start = 0;
12. int max = 0;
13. for(i=0; i<array.length-1; i++){
14. if(array[i] < array[i+1]){
15. start = i;
16. max++;
17. for(j = i+1; j<array.length-1; j++){
18. if(array[j] > array[j+1])
19. break;
20. else
21. max++;
22. }
 23. if(max > index[1] - index[0] + 1){
24. index[0] = start;
25. index[1] = j--;
26. }
27. i = j;
28. }
29. }
30. return index;
31. }
32. // Function to read input and display the output
33. public static void main(String[] args) {
34. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
35. int size;
36. System.out.println("Enter the size of the array");
37. try {
38. size = Integer.parseInt(br.readLine());
39. } catch (Exception e) {
40. System.out.println("Invalid Input");
41. return;
42. }
43. int[] array = new int[size];
44. System.out.println("Enter array elements");
45. int i;
46. for (i = 0; i < array.length; i++) {
47. try {
48. array[i] = Integer.parseInt(br.readLine());
49. } catch (Exception e) {
50. System.out.println("An error occurred");
51. }
52. }
53. int[] index = longestIncreasingSubarray(array);
54. System.out.println("The longest increasing subarray is");
55. for(i=index[0];i<=index[1];i++){
56. System.out.print(array[i] + " ");
57. }
58. }
59. }

Program Explanation
1. In function longestIncreasingSubarray(), we declare array index [] to store the starting
and ending index of the longest subarray.
2. The loop for(i=0; i<array.length-1; i++) is used to iterate through the array.
3. The condition if(array[i] < array[i+1]) is used to check if the current pair of elements is
increasing.
4. If it is true, then a nested loop for(j = i+1; j<array.length-1; j++) is set-up to look for the
end of the increasing subarray.
5. The condition if(max > index[1] – index[0] + 1) checks if the current subarray length, is
greater than the previous one. It updates the index array, if it is true.
6. The variable max stores the length of the increasing subarray and variable start stores
the starting index.
advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case - Mixed Elements):
 
Enter the size of the array
9
Enter array elements
5
6
3
0
7
8
9
1
2
The longest decreasing subarray is
0 7 8 9
 
Case 2 (Simple Test Case - Elements in Ascending Order):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
The longest increasing subarray is
1 2 3 4 5
 
Case 3 (Simple Test Case - Elements in Descending Order):
 
Enter the size of the array
6
Enter array elements
6
5
4
3
2
1
The longest increasing subarray is
6

Java Program to Print Even Elements at Even Index Number

This is the Java Program to Print Even Elements at Even Index Number.

Problem Description
Given an array of integers, print the even numbers present at even index numbers.
Example:

Array = [2,1,4,4,5,7]

Output = 2 4

Problem Solution
Iterate through the array, and check whether the current index is even or odd if it is
even, then check the element at that index to be even or odd, print the element if it is even.

Program/Source Code
Here is the source code of the Java Program to Print Even Elements at Even Index
Number. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Print Even Elements at Even Index Number
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class EvenIndexedOddElements {
8. // Function to even numbers present at even index
9. static void printEvenIndexedElements(int[] array){
10. int i=0;
11. for(i=0; i<array.length; i++){
 12. if(i%2 == 0 && array[i]%2 ==0){
13. System.out.print(array[i] + " ");
14. }
15. }
16. }
17. // Function to read input
18. public static void main(String[] args) {
19. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
20. int size;
21. System.out.println("Enter the size of the array");
22. try {
23. size = Integer.parseInt(br.readLine());
24. } catch (Exception e) {
25. System.out.println("Invalid Input");
26. return;
27. }
28. int[] array = new int[size];
29. System.out.println("Enter array elements");
30. int i;
31. for (i = 0; i < array.length; i++) {
32. try {
33. array[i] = Integer.parseInt(br.readLine());
34. } catch (Exception e) {
35. System.out.println("An error occurred");
36. return;
37. }
38. }
39. System.out.println("Output");
40. printEvenIndexedElements(array);
41. }
42. }

Program Explanation
1. In function printEvenIndexedElements(), the loop for(i=0; i<array.length; i++) is used to
iterate through the array.
2. The condition if(i%2==0 && array[i]%2==0) checks if the index and the element at the
index are both even.
3. The element is displayed if the condition is true.
advertisement
Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case - Even elements at even index):
 
Enter the size of the array
6
Enter array elements
2
1
4
4
5
7
Output
2 4
 
Case 2 (Simple Test Case - Odd elements at even index):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
Output

Java Program to Find Local Minimas in an Array

This is the Java Program to Find Local Minimas in an Array.

Problem Description
Given an array of integers, find out the local maxima present in the array.
An element in an array is a local minima if it less than the element after it, and the
element before it.
For the elements at the extreme end only one check is required, that is, the element
following the first element or the element before the last element.
In case of two or more minima, only one of them is returned.

Example:
Array = [1, 2, 3, 7, 5, 6]
Output:
1 or 5

Problem Solution
The idea here is to use an algorithm, similar to the binary search. Check the middle
element of the array, if it is less than the elements following it and the element preceding it,
then it is the local minima, else if it is less than the preceding element, then the local minima
is in the left half, else the local minima is in the right half.

Program/Source Code
Here is the source code of the Java Program to Find Local Minima in an Array. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Find Local Minimas in an Array
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class LocalMinima {
8. // Function to return the index of the local minima
9. static int localMinima(int[] array){
10. int low,mid,high;
11. low = 0;
12. high = array.length-1;
13. mid = (low + high)/2;
14. int ans;
15. while(low<=high){
16. mid = (low + high)/2;
17. if((mid == 0 || array[mid-1] > array[mid])
18. && (mid == array.length-1 || array[mid+1] > array[mid])){
19. return mid;
20. }
21. else if(mid > 0 && array[mid-1] < array[mid]){
22. high = mid-1;
23. }
24. else{
25. low = mid+1;
26. }
27. }
 28. return -1;
29. }
30. // Function to read user input
31. public static void main(String[] args) {
32. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
33. int size;
34. System.out.println("Enter the size of the array");
35. try {
36. size = Integer.parseInt(br.readLine());
37. } catch (Exception e) {
38. System.out.println("Invalid Input");
39. return;
40. }
41. int[] array = new int[size];
42. System.out.println("Enter array elements");
43. int i;
44. for (i = 0; i < array.length; i++) {
45. try {
46. array[i] = Integer.parseInt(br.readLine());
47. } catch (Exception e) {
48. System.out.println("An error occurred");
49. return;
50. }
51. }
52. int index = localMinima(array);
53. System.out.println("The local minima is " + array[index]);
54. }
55. }

Program Explanation
1. In the function localMinima(), we initialize two variables high and low as array.length-1
and 0 respectively.
2. Using a loop while(low<=high), we first calculate the middle index.
3. Now, in the condition if((mid == 0 || array[mid-1] > array[mid]) && (mid == array.length-1 ||
array[mid+1] > array[mid])), we check whether the element at current middle index is a
minima.
4. If the element is a minima, then we return the current middle index, otherwise using the
condition else if(mid > 0 && array[mid-1] < array[mid]), we first check that we are not at the
beginning of the array and finally, check if the preceding element is smaller than the current
middle element.
5. If it is, we then set high to mid-1, to look in the first half of the array, otherwise, we set low
to mid+1 to look for the minima in the second half of the array.
advertisement

Time Complexity: O(log(n)) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Positive test Case - local minima is not at the extreme ends):
 
Enter the size of the array
8
Enter array elements
23
12
11
10
13
5
57
58
The local minima is 10
 
Case 2 (Positive test Case - local minima is at the beginning of the array):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
The local minima is 1
 
 
Case 3 (Positive test Case - local minima is at the end of the array):
 
Enter the size of the array
5
Enter array elements
9
8
7
6
5
The local minima is 5
Java Program to Find the Sub-Arrays whose Sum is Equal to a
Given Number
This is the Java Program to Find the Sub-Arrays whose Sum is Equal to a Given Number.

Problem Description
Given an array of integers and a value say m, find out the contiguous subarray the sum
of whose elements, is equal to m.

Example:
Array = [1, 2, 3, 4, 5, -1] m = 8

Output:
[4, 5, -1]

Problem Solution
Iterate through the array, maintain a running sum of the array elements, if the running
sum is equal to the value m, then we have got the subarray, else search for the value
(currentsum – m) in a hashmap, if it is present in the hashmap, then the subarray from the
element, next to the (currentsum – m) to the present element, is your required subarray,
else add the value (currentsum – m) to the hashmap.

Program/Source Code
Here is the source code of the Java Program to Find the Sub-Arrays whose Sum is Equal to
a Given Number. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Find the Sub-Arrays whose Sum is Equal to a Given Number
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6. import java.util.HashMap;
7. import java.util.Map;
8.  
9. public class SubarrayWithGivenSum {
10. // Function to find the subarray with the given sum
11. static void findSubarray(int[] array, int sum){
12. Map< Integer, Integer > obj = new HashMap<>();
13. int currentSum = 0;
14. int i,startIndex = 0;
15. boolean flag = false;
16. for(i=0; i<array.length; i++){
17. currentSum += array[i];
18. if(currentSum == sum){
19. flag = true;
20. break;
21. }
22. if(obj.containsKey(currentSum - sum)){
23. startIndex = obj.get(currentSum - sum) + 1;
24. flag = true;
25. break;
26. }
27. else{
28. obj.put(currentSum, i);
29. }
30. }
31. if(flag){
32. System.out.println("The subarray is");
33. for( ; startIndex<=i; startIndex++){
34. System.out.print(array[startIndex] + " ");
35. }
36. }
37. else{
38. System.out.println("No such subarray exists");
39. }
40. }
41. // Function to read user input
42. public static void main(String[] args) {
43. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
44. int size;
45. System.out.println("Enter the size of the array");
46. try {
47. size = Integer.parseInt(br.readLine());
48. } catch (Exception e) {
49. System.out.println("Invalid Input");
50. return;
51. }
52. int[] array = new int[size];
53. System.out.println("Enter array elements");
54. int i;
55. for (i = 0; i < array.length; i++) {
 56. try {
57. array[i] = Integer.parseInt(br.readLine());
58. } catch (Exception e) {
59. System.out.println("An error occurred");
60. return;
61. }
62. }
63. int sum;
64. System.out.println("Enter the sum you are looking for");
65. try{
66. sum = Integer.parseInt(br.readLine());
67. }
68. catch (Exception e){
69. System.out.println("An error occurred");
70. return;
71. }
72. System.out.println("Output ");
73. findSubarray(array, sum);
74. }
75. }

Program Explanation
1. In the function findSubarray(), we create a hashmap using the statement
Map<Integer,Integer> obj=new HashMap<>().
2. The first value in the map stores the current sum of the array elements and the second
value stores the index upto which the current sum is calculated.
3. In the loop for(i=0; i<array.length; i++), we iterate through the array and add the current
array element to the variable currentsum.
4. Using the condition, if(currentSum == sum) we check if the current sum of the array
elements is equal to the sum we are looking for.
5. If it is we break out of the loop, otherwise we check whether the element currentsum –
sum is present in the hashmap, if it is present we set the starting index of the subarray to
index of the element following the element (currentsum-sum) through the statement
startIndex = obj.get(currentSum – sum) + 1 and break out of the loop.
6. If both the previous two condition fails, we add the current sum to the hashmap using
(obj.put(currentSum, i)). Finally, we display the subarray if it exists, otherwise, a suitable
message is displayed.

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases
advertisement
 
Case 1 (Positive test Case):
 
Enter the size of the array
6
Enter array elements
1
2
3
4
5
-1
Enter the sum you are looking for
8
Output
The subarray is
4 5 -1
 
Case 2 (Positive test Case - another example):
 
Enter the size of the array
8
Enter array elements
1
2
3
4
4
3
2
1
Enter the sum you are looking for
20
Output
The subarray is
1 2 3 4 4 3 2 1
 
Case 3 (Negative test Case):
 
Enter the size of the array
8
Enter array elements
1
2
3
4
5
6
7
8
Enter the sum you are looking for
100
Output
No such subarray exists

Java Program to Rotate an Array by n Elements

This is the Java Program to Rotate an Array by n Elements.

Problem Description
Given an array of integers, circularly rotate the elements of the array, by a given value,
say n.
Example:

int array[] = {1,2,3,4,5}

n = 3
output = {3,4,5,1,2}

Problem Solution

The idea is to use two loops. The outer loop is used to manage the value by which the
array elements are to be rotated. In the second loop, just move each array element one
position ahead, that is, 1  into 2 , 2  into 3 , and so on, until the last element is moved into
st nd nd rd

the 1 position.
st

Program/Source Code
Here is the source code of the Java Program to Rotate an Array by n Elements. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Rotate an Array by n Elements.
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class RotateArray {
8. // Function to rotate the array elements
9. static void rotateArray(int[] array, int n){
10. int i,j,temp,temp1;
11. for(i=1;i<=n;i++){
12. temp = array[0];
13. for(j=0;j<array.length;j++){
14. temp1 = array[(j+1) % array.length];
15. array[(j+1) % array.length] = temp;
16. temp = temp1;
17. }
18. }
19. }
20. // main function to read the array and display the output
21. public static void main(String[] args) {
22. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
23. int size;
24. System.out.println("Enter the size of the array");
25. try {
26. size = Integer.parseInt(br.readLine());
27. } catch (Exception e) {
28. System.out.println("Invalid Input");
29. return;
30. }
31. int[] array = new int[size];
32. System.out.println("Enter array elements");
33. int i;
34. for (i = 0; i < array.length; i++) {
35. try {
36. array[i] = Integer.parseInt(br.readLine());
37. } catch (Exception e) {
38. System.out.println("An error occurred");
39. return;
40. }
41. }
42. System.out.println("The contents of the array before rotation
are");
43. for(i=0;i<array.length;i++){
44. System.out.print(array[i] + " ");
45. }
46. System.out.println();
47. int n;
48. System.out.println("Enter the number by which the array elements
are to "
49. + "be rotated");
50. try{
51. n=Integer.parseInt(br.readLine());
 52. }catch (Exception e){
53. System.out.println("An error occurred");
54. return;
55. }
56. rotateArray(array,n);
57. System.out.println("The contents of the array after rotation are");
58. for(i=0;i<array.length;i++){
59. System.out.print(array[i] + " ");
60. }
61. }
62. }

Program Explanation
1. In the function rotateArray(), the loop for(i=1; i<=n; i++) runs the number of times, the
array is to be rotated.
2. Using a nested loop for(i=0; i<array.length; i++), we shift each array element one position
ahead.
3. Therefore, in one rotation of the outer loop, the array is rotated one time. Hence, in n
iterations, it is rotated n times.

Time Complexity: O(n*m) where n is the value by which array elements are to be rotated,
m is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Positive test Case):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
The contents of the array before rotation are
1 2 3 4 5
Enter the number by which the array elements are to be rotated
3
The contents of the array after rotation are
3 4 5 1 2
 
Case 2 (Positive test Case - another example):
 
Enter the size of the array
7
Enter array elements
234
35
31
46
2434
133
457
The contents of the array before rotation are
234 35 31 46 2434 133 457
Enter the number by which the array elements are to be rotated
8
The contents of the array after rotation are
457 234 35 31 46 2434 133

Java Program to Find the Missing Element in an Integer Array

This is the Java Program to Find the Missing Element in an Integer Array.

Problem Description
Given an array of n-1 integers having no duplicates, and containing the integers in the
range 1 to n.
Find out the missing integer.
Example:
Array = [ 1, 2, 4, 5]

Output :
Missing integer = 3

Problem Solution
Take two variables to say x and y, in x store the XOR of all array elements and in y store
the XOR of integers from 1 to n. Finally, take the result of XOR of x and y, this result is our
missing integer.

Program/Source Code
Here is the source code of the Java Program to Find the Missing Element in an Integer
Array. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows
7. The program output is also shown below.
1.  
2. //Java Program to Find the Missing Element in an Integer Array.
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class MissingInteger {
8. // Function to calculate XOR values and return the missing integer.
9. static int findMissingInteger(int[] array){
10. int i;
11. int XOR1, XOR2;
12. XOR1 = array[0];
13. XOR2 = 1;
14. for(i=1;i<array.length;i++){
15. XOR1 ^= array[i];
16. XOR2 ^= (i+1);
17. }
18. XOR2 ^=(i+1);
19. return (XOR2 ^ XOR1);
20. }
21. // Function to read the input and display the output
22. public static void main(String[] args) {
23. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
24. int size;
25. System.out.println("Enter the range of the values (starts from
1)");
26. try {
27. size = Integer.parseInt(br.readLine());
28. } catch (Exception e) {
29. System.out.println("Invalid Input");
30. return;
31. }
32. int[] array = new int[size-1];
33. System.out.println("Enter array elements");
34. int i;
35. for (i = 0; i < array.length; i++) {
36. try {
37. array[i] = Integer.parseInt(br.readLine());
38. } catch (Exception e) {
39. System.out.println("An error occurred");
40. return;
41. }
42. }
43. int missing = findMissingInteger(array);
44. System.out.println("The missing integer is " + missing);
45. }
 46. }

Program Explanation
1. The function findMissingInteger(), initializes the variables XOR1 to array[0] and XOR2 to
1.
2. The loop for(i=1; i<array.length; i++) is used to iterate through the array and store the
XOR of its elements in XOR1 and XOR of first n-1 integers in XOR2.
3. The statement XOR2^=(i+1) XOR’s the integer n.
4. The statement (XOR1^XOR2) returns the missing integers.

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

advertisement
 
Case 1 (Simple Test Case):
 
Enter the range of the values (starts from 1)
5
Enter array elements
1
2
4
5
The missing integer is 3
 
Case 2 (Simple Test Case - another example):
 
Enter the range of the values (starts from 1)
8
Enter array elements
8
7
6
5
4
3
2
The missing integer is 1

Java Program to Split an Array and Concatenate First Part to

the End
This is the Java Program to Split an Array and Concatenate First Part to the End.

Problem Description
Given an array of integers, and a value n, denoting the number of parts in which array is to
be splitted. Concatenate the first part of the array to the end.

Example:
Array1: [1,2,3,4,5] n = 3

Output:

Array = [1,4,5]

Problem Solution
Create a new array. If the number of elements in the array is a multiple of n. Then the size
of the new array will be (number of elements / n)*2, else size = (number of elements / n) +
(number of elements % n). Concatenate the first and the last parts.

Program/Source Code
Here is the source code of the Java Program to Split an Array and Concatenate First Part to
the End. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. // Java Program to Split an Array and Concatenate First Part to the End.
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6. import java.util.Arrays;
7.  
8. public class SplitAndConcatenate {
9. // Function concatenate the first and last part
10. static int[] splitAndConcatenate(int[] array,int n){
11. int size = (array.length/n);
12. if(array.length%n == 0)
13. size*=2;
14. else
15. size+=array.length%n;
16. int[] output = new int[size];
17. int i,j=0;
18. for(i=0; i<array.length/n; i++){
19. output[j++] = array[i];
20. }
21. for(i= (array.length%n == 0 ? array.length-array.length/n
22. : array.length - array.length%n ); i<array.length; i++){
23. output[j++] = array[i];
24. }
25. return output;
26. }
27. // Function to read input and display the output
28. public static void main(String[] args) {
29. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
30. int size;
31. System.out.println("Enter the size of the array");
32. try {
33. size = Integer.parseInt(br.readLine());
34. } catch (Exception e) {
35. System.out.println("Invalid Input");
36. return;
37. }
38. int[] array = new int[size];
39. System.out.println("Enter array elements");
40. int i;
41. for (i = 0; i < array.length; i++) {
42. try {
43. array[i] = Integer.parseInt(br.readLine());
44. } catch (Exception e) {
45. System.out.println("An error occurred");
46. return;
47. }
48. }
49. int n;
50. System.out.println("Enter the number of parts in" +
51. " which array is to splitted");
52. try {
53. n = Integer.parseInt(br.readLine());
54. } catch (Exception e) {
55. System.out.println("Invalid Input");
56. return;
57. }
58. System.out.println("The final array is");
59. if(n==0){
60. System.out.println(Arrays.toString(array));
61. }
62. else{
63. int[] output = splitAndConcatenate(array,n);
64. System.out.println(Arrays.toString(output));
 65. }
66. }
67. }

Program Explanation
1. In function splitAndConcatenate(), first, the size of one part is calculated as int size =
(array.length/n).
2. Next the size of the total size of the output array is calculated as per the if conditions. If
number of parts is a multiple of total array size, the output size is doubled, otherwise, the
remainder is added to it.
3. Now, the output array is created and the loop for(i=0; i<array.length/n; i++) add the first
part of the array to the output array.
4. The loop for(i= (array.length%n == 0 ? array.length-array.length/n : array.length –
array.length%n ); i<array.length; i++) adds the last part of the array to the output array.
5. The variable i is initialized as per if total array size is a multiple of n the number of parts in
which array is to be broken.
advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
 
Case 1 (Simple Test Case):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
Enter the number of parts in which array is to splitted
3
The final array is
[1, 4, 5]
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
8
Enter array elements
12
23
45
23
2
56
5
87
Enter the number of parts in which array is to splitted
4
The final array is
[12, 23, 5, 87]

Java Program to Print all the Leaders in an Array

This is the Java program to print all the leaders in an array.

Problem Description
Given an array of integers, find and print all the leaders of the array. A leader is defined as
an element of the array which is greater than all the elements following it. The rightmost
element is always a leader.
For example:
In the array {8, 7, 4, 3, 5, 2}, leaders are 8, 7, 5 and 2.
Explanation:

8 > 7, 8 > 4, 8 > 3, 8 > 5, 8 > 2.

7 > 4, 7 > 3, 7 > 5, 7 > 2.
5 > 2.
2 is the rightmost element.

Problem Solution
The idea is to traverse the array from right to left and keep track of the maximum
element encountered. If the maximum element changes, then that element is a leader of the
array.

Program/Source Code
Here is the source code of the Java Program to print all the leaders of an array. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. // Java program to print all the leaders in an array.
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class LeaderInAnArray {
8. //The main function to take input from the user
9. //and display the leaders in an array
10. public static void main(String[] args) {
11. BufferedReader br=new BufferedReader(new
InputStreamReader(System.in));
12. int size;
13. System.out.println("Enter the size of the array");
14. try{
15. size=Integer.parseInt(br.readLine());
16. }
17. catch(Exception e)
18. {
19. System.out.println("Invalid Input");
20. return;
21. }
22. int[] array=new int[size];
23. System.out.println("Enter array elements");
24. int i;
25. for(i=0;i<array.length;i++){
26. try{
27. array[i]=Integer.parseInt(br.readLine());
28. }
29. catch(Exception e)
30. {
31. System.out.println("An error occurred. Exiting");
32. return;
33. }
34. }
35. System.out.println("The leaders of the array are");
36. \\ max variable is used to keep track of the current maximum
element
37. int max=Integer.MIN_VALUE;
38. \\ loop to print all the leaders of the array
39. for(i=array.length-1;i>=0;i--) {
40. if (array[i] > max) {
41. System.out.print(array[i] + " ");
42. max = array[i];
43. }
44. }
 45. }
46. }

Program Explanation
1. In function main(), firstly the user enters the array.
2. The variable max is initialized to Integer.MIN_VALUE.
3. The loop for(i=array.length-1;i>=0;i–) iterates through the array from right to left.
4. If any element, greater than max is found, then that element is displayed and the max
variable is set to array[i].

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
 
Case 1 (Simple Test Case):
 
Enter the size of the array
6
Enter array elements
8
7
4
3
5
2
The leaders of the array are
2 5 7 8
 
Case 2 (Simple Test Case - reverse sorted array):
 
Enter the size of the array
10
Enter array elements
9
8
7
6
5
4
3
2
1
0
The leaders of the array are
0 1 2 3 4 5 6 7 8 9
 
Case 3 (Simple Test Case - sorted array):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
The leaders of the array are
5

Java Program to Merge Two Arrays in Order

This is the Java Program to Merge Two Arrays in Order.

Problem Description
Given two arrays of integers, merge them into a single sorted array in order.

Example:
Array1: [1,2,3,4,5] 
Array2: [2,3,6,7,8]

Output:

Array = [1,2,2,3,3,4,5,6,7,8]

Problem Solution
Create a new array of size equal to the sum of the sizes of the two arrays. Now, compare
the first elements of the first two arrays and put the smaller element in the new array.
Increment the index counter of the array which contains the small element and continues
the process. If the elements of any of the arrays are completely copied, then copy the
remaining elements of the other array, into the new array.

Program/Source Code
Here is the source code of the Java Program to Merge Two Arrays in Order. The program is
successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output
is also shown below.
1.  
2. // Java Program to Merge Two Arrays in Order.
3.  
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7. import java.util.Arrays;
8.  
9. public class InOrderMerge {
10. // Function to merge the arrays
11. static int[] mergeArrays(int[] arrayOne,int[] arrayTwo)
12. {
13. int totalLength=arrayOne.length +arrayTwo.length;
14. int[] c=new int[totalLength];
15. int j,k,index=0;
16. j=0;
17. k=0;
18. while((j!=arrayOne.length) && (k!=arrayTwo.length)){
19. if(arrayOne[j]<=arrayTwo[k])
20. {
21. c[index++]=arrayOne[j++];
22. }
23. else
24. {
25. c[index++]=arrayTwo[k++];
26. }
27. }
28. while(k!=arrayTwo.length)
29. {
30. c[index++]=arrayTwo[k++];
31. }
32. while(j!=arrayOne.length)
33. {
34. c[index++]=arrayOne[j++];
35. }
36. return c;
37. }
38. // Function to read input and display the output
39. public static void main(String[] args){
40. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
41. int m, n;
42. System.out.println("Enter the size of the two arrays");
43. try {
44. n = Integer.parseInt(br.readLine());
45. m = Integer.parseInt(br.readLine());
46. }
47. catch (IOException e)
48. {
 49. System.out.println("Invalid input");
50. return;
51. }
52. int[] arrayOne = new int[n];
53. int[] arrayTwo = new int[m];
54. System.out.println("Enter the first array elements");
55. int i,j;
56. for(i=0; i<arrayOne.length; i++){
57. try {
58. arrayOne[i] = Integer.parseInt(br.readLine());
59. }
60. catch (IOException e)
61. {
62. System.out.println("Invalid array element. Enter it
again");
63. i--;
64. }
65. }
66. System.out.println("Enter the second array elements");
67. for(i=0; i<arrayTwo.length; i++){
68. try {
69. arrayTwo[i] = Integer.parseInt(br.readLine());
70. }
71. catch (IOException e)
72. {
73. System.out.println("Invalid array element. Enter it
again");
74. i--;
75. }
76. }
77. Arrays.sort(arrayOne);
78. Arrays.sort(arrayTwo);
79. int[] mergedArray=mergeArrays(arrayOne,arrayTwo);
80. System.out.println("The merged array is");
81. for(i=0;i<mergedArray.length;i++)
82. {
83. System.out.print(mergedArray[i]+" ");
84. }
85. }
86. }

Program Explanation
1. In function mergeArrays(), a new array c is created whose size is equal to the total size of
the two arrays.
2. The loop while((j!=arrayOne.length) && (k!=arrayTwo.length)) merges the two array in
ascending order, until one of the arrays is completely merged.
3. The loops while(k!=arrayTwo.length) and while(j!=arrayOne.length) merges the remaining
components of any array into the final array c.
advertisement

Time Complexity: O(n*log(n) + m*log(m)) where n is the number of elements in the first

array and m is the number of elements in the second array.

Runtime Test Cases

 
 
Case 1 (Simple Test Case):
 
Enter the size of the two arrays
5
5
Enter the first array elements
1
2
3
4
5
Enter the second array elements
2
3
6
7
8
The merged array is
1 2 2 3 3 4 5 6 7 8
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the two arrays
4
5
Enter the first array elements
89
45
32
6
Enter the second array elements
24
456
23
567
34
The merged array is
6 23 24 32 34 45 89 456 567

Java Program to Find Two Elements whose Sum is Equal to a

Given Number
This is the Java Program to Find Two Elements whose Sum is Equal to a Given Number.

Problem Description
Given an array of n integers and a value, say m. Find out the pairs of elements from the
array, whose sum values m.
Example:
Array = [ 1, 2, 4, 5, 8, 10, 11] m = 13

Output :
{8, 5}
{11, 2}

Problem Solution
Iterate through the array and in a temporary variable, say x, store the difference of the
current array element and the value m. Search for value x, in the map, if x is present in
the map, then the pair of elements x and the current array element, sums to m, else store x
in the map.

Program/Source Code
Here is the source code of the Java Program to Find Two Elements whose Sum is Equal to
a Given Number. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Find Two Elements whose Sum is Equal to a Given Number.
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6. import java.util.HashMap;
7.  
8. public class PairsHavingGivenSum {
9. // Function to print the pair of elements having a given sum
10. static void printPairs(int[] array,int sum)
11. {
12. HashMap<Integer,Integer> obj=new HashMap<>();
13. int i,search;
14. System.out.println("The pairs having sum "+sum+" are");
15. for(i=0;i<array.length;i++){
16. search=sum-array[i];
17. if(obj.containsValue(search)){
18. System.out.println(array[i]+" and "+search);
19. }
20. else
21. {
22. obj.put(i,array[i]);
23. }
24. }
25. }
26. // Main function to read the input
27. public static void main(String[] args) {
28. BufferedReader br= new BufferedReader(new
InputStreamReader(System.in));
29. int size;
30. System.out.println("Enter the size of the array");
31. try{
32. size=Integer.parseInt(br.readLine());
33. }
34. catch(Exception e)
35. {
36. System.out.println("Invalid Input");
37. return;
38. }
39. int[] array=new int[size];
40. System.out.println("Enter array elements");
41. int i;
42. for(i=0;i<array.length;i++){
43. try{
44. array[i]=Integer.parseInt(br.readLine());
45. }
46. catch(Exception e)
47. {
48. System.out.println("Invalid element. Enter it again");
49. i--;
50. }
51. }
52. int sum;
 53. System.out.println("Enter the sum you want to look for");
54. try{
55. sum=Integer.parseInt(br.readLine());
56. }
57. catch(Exception e)
58. {
59. System.out.println("Invalid Input");
60. return;
61. }
62. printPairs(array,sum);
63. }
64. }

Program Explanation
1. In function printPairs(), firstly a hashmap is created HashMap obj=new HashMap<>().
2. The loop for(i=0; i<array.length; i++), sets the value search to sum – array[i] in each
iteration.
3. The condition if(obj.containsValue(search)) looks for the variable search in the hashmap.
4. If it is present, then the present element and the element search has the given sum in the
array.
5. Otherwise, the value search is added to the hashmap.

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case) :
 
Enter the size of the array
7
Enter array elements
1
2
4
5
8
10
11
Enter the sum you want to look for
13
The pairs having sum 13 are
8 and 5
11 and 2
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
10
Enter array elements
12
324
45
34
123
435
23
56
32
47
Enter the sum you want to look for
79
The pairs having sum 79 are
34 and 45
56 and 23
47 and 32

Java Program to Print Pairs of Elements that have the Given

Difference
This is the Java Program to Print Pairs of Elements that have the Given Difference.

Problem Description
Given an array of n integers and a value, say m. Find out the pairs of elements from the
array, whose difference is value m.
Example:
Array = [ 1, 2, 4, 5, 8, 10, 11] m = 1

Output :
{1, 2}
{4, 5}
{10, 11}

Problem Solution
Iterate through the array and store all of its elements in a map. Now, re-iterate through the
array and in a temporary variable, say x, store the sum of the current array element and the
difference m. Search for value x, in the map, if x is present in the map, then the pairs of
elements x and the current array element exhibits the difference m.

Program/Source Code
Here is the source code of the Java Program to Print Pairs of Elements that have the Given
Difference. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Print Pairs of Elements that have the Given Difference.
3.  
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7. import java.util.HashMap;
8.  
9. public class PairsHavingGivenDifference {
10. //Function to print pair of elements having a given difference.
11. static void printPairs(int[] array,int difference){
12. HashMap<Integer,Integer> obj=new HashMap<>();
13. int i;
14. for(i=0;i<array.length;i++){
15. obj.put(i,array[i]);
16. }
17. System.out.println("The pairs of elements having the difference "
18. +difference+" are ");
19. int search;
20. for (i=0;i<array.length;i++){
21. search=array[i]+difference;
22. if(obj.containsValue(search)){
23. System.out.println(array[i] + " and "+search);
24. }
25. }
26. }
27. // Function to read input
28. public static void main(String[] args) {
29. BufferedReader br=new BufferedReader(new
InputStreamReader(System.in));
30. int size;
31. System.out.println("Enter the size of the array");
32. try{
33. size=Integer.parseInt(br.readLine());
34. }
35. catch(IOException e)
36. {
37. System.out.println("Invalid Input");
38. return;
 39. }
40. int[] array=new int[size];
41. System.out.println("Enter array elements");
42. int i;
43. for(i=0;i<array.length;i++){
44. try{
45. array[i]=Integer.parseInt(br.readLine());
46. }
47. catch(IOException e)
48. {
49. System.out.println("Invalid element. Enter it again");
50. i--;
51. }
52. }
53. int difference;
54. System.out.println("Enter the difference you want to look for");
55. try{
56. difference=Integer.parseInt(br.readLine());
57. }
58. catch(IOException e)
59. {
60. System.out.println("Invalid Input");
61. return;
62. }
63. printPairs(array,difference);
64. }
65. }

Program Explanation
1. In function printPairs(), firstly a hashmap is created HashMap obj=new HashMap<>().
2. The loop for(i=0; i<array.length; i++) is used to put all the array elements with their
indexes, into the map.
3. The second loop for(i=0; i<array.length; i++), sets the value search to array[i] + difference
in each iteration.
4. The condition if(obj.containsValue(search)) looks for the variable search in the hashmap.
5. If it is present, then the present element and the element search has the given difference
in the array.

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case - Positive Difference):
 
Enter the size of the array
10
Enter array elements
123
12
234
24
0
786
798
234
123
213
Enter the difference you want to look for
12
The pairs of elements having the difference 12 are
12 and 24
0 and 12
786 and 798
 
Case 2 (Simple Test Case - Negative difference):
 
Enter the size of the array
8
Enter array elements
8
7
6
5
4
3
2
1
Enter the difference you want to look for
-1
The pairs of elements having the difference -1 are
8 and 7
7 and 6
6 and 5
5 and 4
4 and 3
3 and 2
2 and 1

Java Program to Find the Largest and Smallest Word

This is the Java Program to Find the Largest and Smallest Word

Problem Description
Given a string of characters, find the largest and the smallest word if two or more words are
the largest or smallest then display the one that occurs first in the string.

Example:

String x = “We belong to Russia”

Output = We, belong

“We” and “to” both are the smallest words since “We” is encountered first, it comes in the
output, same is with “belong” and “Russia”.

Problem Solution
Split the given string into various substrings, whenever space is encountered. Iterate
through these substrings to find the first largest and smallest word.

Program/Source Code
Here is the source code of the Java Program to Find the Largest and Smallest Word. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. // Java program to Find the Largest and Smallest Word.
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class LargestAndSmallestWord {
8. // Method to split the string and find the largest and smallest word
9. static void printLargestAndSmallestWord(String str){
10. String[] arr=str.split(" ");
11. int i=0;
12. int maxlength,minlength;
13. maxlength=Integer.MIN_VALUE;
14. minlength=Integer.MAX_VALUE;
15. String largest,smallest;
16. largest = smallest = "";
17. for(i=0;i<arr.length;i++){
18. if(arr[i].length() < minlength){
19. smallest=arr[i];
20. minlength=arr[i].length();
21. }
22. if(arr[i].length() > maxlength) {
 23. largest=arr[i];
24. maxlength=arr[i].length();
25. }
26. }
27. System.out.println("The largest and smallest word is \"" + largest
+
28. "\" and \"" + smallest +
"\"");
29. }
30. // Main function to read the string
31. public static void main(String[] args) {
32. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
33. System.out.println("Enter the text string");
34. String str;
35. try{
36. str=br.readLine();
37. }
38. catch(Exception e){
39. System.out.println("Error reading input");
40. return;
41. }
42. printLargestAndSmallestWord(str);
43. }
44. }

Program Explanation
1. In function printLargestAndSmallestWord(), the string is split into various tokens using
s.split(” “) statement.
2. The minlength and maxlength variables are initialized to Integer.MAX_VALUE and
Integer.MIN_VALUE, respectively.
3. The loop for(i=0;i<arr.length;i++) is used to iterate through the array of tokens.
4. The condition if(arr[i].length() < minlength) checks if the current token is the smallest, if it
is the minlength and smallest variables are updated accordingly.
5. The condition if(arr[i].length() > maxlength) checks if the current token is the largest, if it
is the maxlength and largest variables are updated accordingly.
advertisement

Time Complexity: O(n) where n is the length of the string.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the text string
I am IronMan
The largest and smallest word is "IronMan" and "I"
 
Case 2 (Simple Test Case - another example):
 
Enter the text string
We belong to Russia
The largest and smallest word is "belong" and "We"

Java Program to Find the Row with the Maximum Number of 1’s
in a Sorted Matrix
This is the Java Program to Find the Row with the Maximum Number of 1’s in a Sorted
Matrix.

Problem Description
Given a boolean matrix of 0’s and 1’s, where each row is sorted, print the row first with the
maximum number of 1’s.
Example:
Matrix:
0 0 1 1
0 0 1 1
0 1 1 1
0011

Output:
0111

Problem Solution
Iterate through the first row to find the index of the leftmost one in it. For each of the next
row, if the element at the index before the leftmost one is zero, then skip that row, otherwise
update the index for leftmost one.

Program/Source Code
Here is the source code of the Java Program to Find the Row with the Maximum Number of
1’s in a Sorted Matrix. The program is successfully compiled and tested using IDE IntelliJ
Idea in Windows 7. The program output is also shown below.
1.  
2. //Java Program to Find the Row with the Maximum Number of 1's in a Sorted
Matrix
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class RowWithMaxOne {
8. // Function to find and display the row with maximum number of 1's
9. static void printRow(int[][] matrix) {
10. int i, j, rownumber = -1;
11. int leftmost = -1;
12. for (i = 0; i < matrix[0].length; i++) {
13. if (matrix[0][i] == 1) {
14. rownumber = 0;
15. leftmost = i;
16. break;
17. }
18. }
19. if (leftmost == -1) {
20. leftmost = matrix[0].length;
21. }
22. for (i = 1; i < matrix[0].length; i++) {
23. int x = leftmost - 1;
24. while (x >= 0 && matrix[i][x] == 1) {
25. rownumber = i;
26. leftmost = x;
27. x--;
28. }
29. }
30. if (rownumber != -1) {
31. System.out.println("Row with maximum number of" +
32. "One's in Sorted Matrix is");
33. for (i = 0; i < matrix[rownumber].length; i++) {
34. System.out.print(matrix[rownumber][i] + " ");
35. }
36. } else {
37. System.out.println("There is no row containing 1's");
38. }
39. }
40. //Main Function to read input
41. public static void main(String[] args) {
 42. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
43. int rows,columns;
44. try{
45. System.out.println("Enter the number of rows");
46. rows = Integer.parseInt(br.readLine());
47. System.out.println("Enter the number of columns");
48. columns = Integer.parseInt(br.readLine());
49. }
50. catch(Exception e){
51. System.out.println("An error occurred");
52. return;
53. }
54. int[][] matrix = new int[rows][columns];
55. int i,j,prev;
56. prev=Integer.MIN_VALUE;
57. System.out.println("Enter the Boolean Matrix");
58. try{
59. for(i=0; i<rows; i++){
60. for(j=0; j<columns; j++){
61. matrix[i][j] = Integer.parseInt(br.readLine());
62. }
63. }
64. }catch (Exception e){
65. System.out.println("An error occurred");
66. return;
67. }
68. System.out.println("The matrix is");
69. for(i=0; i<rows; i++){
70. for(j=0; j<columns; j++){
71. System.out.print(matrix[i][j]);
72. }
73. System.out.println();
74. }
75. if(rows > 0 && columns > 0)
76. printRow(matrix);
77. }
78. }

Program Explanation
1. In function printRow(), the loop for (i = 0; i < matrix[0].length; i++), iterates through the
first row and finds the index of the leftmost one.
2. If there is no one in the first row, then the variable leftmost is set equal to the number of
columns.
3. The loop for (i = 1; i < matrix[0].length; i++) traverses through the remaining rows.
4. The variable x is set to leftmost-1 and the nested loop while (x >= 0 && matrix[i][x] == 1)
is used to find the index of the leftmost 1 in the current row.
5. Finally, the row with maximum number of 1’s is displayed.

Time Complexity: O(n+m) where n is the number of rows and m is the number of columns
in the matrix respectively.

Runtime Test Cases

 
Case 1 (Positive Test Case):
 
Enter the number of rows
4
Enter the number of columns
4
Enter the Boolean Matrix
1
1
1
1
0
0
0
1
0
0
1
1
0
1
1
1
The matrix is
1111
0001
0011
0111
Row with the maximum number of One's in Sorted Matrix is
1 1 1 1
 
Case 2 (Positive Test Case - another example):
 
Enter the number of rows
4
Enter the number of columns
4
Enter the Boolean Matrix
0
0
0
1
0
0
1
1
0
1
1
1
0
0
1
1
The matrix is
0001
0011
0111
0011
Row with the maximum number of One's in Sorted Matrix is
0 1 1 1
 
Case 3 (Negative Test Case):
 
Enter the number of rows
3
Enter the number of columns
3
Enter the Boolean Matrix
0
0
0
0
0
0
0
0
0
The matrix is
000
000
000
There is no row containing 1's

Java Program to Print the Longest Sub-Array that is Decreasing

This is the Java Program to Print the Longest Sub-Array that is decreasing.

Problem Description
Given an array of integers, find the longest contiguous subarray whose elements are
decreasing, that is, the elements following the preceding elements in the subarray must be
smaller than them.
Example:

Array = [5, 6, 3, 0, 7, 8, 9, 1, 2]

Output: 6 3 0

Problem Solution
Traverse the array from beginning to end and check for the first element which is greater
than the element following it, from that index find out the subarray which is decreasing, if
the current subarray length is greater than the previous subarray length, then update the
longest decreasing subarray. Initially, the subarray would be of length one, referring to the
first elements of the array.

Program/Source Code
Here is the source code of the Java Program to Print the Longest Sub-Array that is
Decreasing. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Print the Longest Sub-Array that is Decreasing
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class LongestDecreasingSubarray {
8. // Function to calculate the longest decreaing subarray
9. static int[] longestDecreasingSubarray(int[] array){
10. int[] index = new int[2];
11. int i,j,start = 0;
12. int max = 0;
13. for(i=0; i<array.length-1; i++){
14. max = 0;
15. if(array[i] > array[i+1]){
16. start = i;
17. max++;
18. for(j = i+1; j<array.length-1; j++){
19. if(array[j] < array[j+1])
20. break;
 21. else
22. max++;
23. }
24. if(max > index[1] - index[0] + 1){
25. index[0] = start;
26. index[1] = j--;
27. }
28. i = j--;
29. }
30. }
31. return index;
32. }
33. // Function to read input and display the user output
34. public static void main(String[] args) {
35. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
36. int size;
37. System.out.println("Enter the size of the array");
38. try {
39. size = Integer.parseInt(br.readLine());
40. } catch (Exception e) {
41. System.out.println("Invalid Input");
42. return;
43. }
44. int[] array = new int[size];
45. System.out.println("Enter array elements");
46. int i;
47. for (i = 0; i < array.length; i++) {
48. try {
49. array[i] = Integer.parseInt(br.readLine());
50. } catch (Exception e) {
51. System.out.println("An error occurred");
52. }
53. }
54. int[] index = longestDecreasingSubarray(array);
55. System.out.println("The longest decreasing subarray is");
56. for(i=index[0];i<=index[1];i++){
57. System.out.print(array[i] + " ");
58. }
59. }
60. }

Program Explanation
1. In function longestDecreasingSubarray(), the array index is created to hold the starting
and ending indexes of the longest decreasing subarray.
2. The loop for(i=0; i<array.length-1; i++) is used to traverse the array from left to right.
3. The condition if(array[i] > array[i+1]) checks if the current element is greater than the
following element.
4. If the condition is true, then using the nested loop for(j = i+1; j<array.length-1; j++) the
length of the decreasing subarray is calculated.
5. The condition if(max > index[1] – index[0] + 1) checks whether the current subarray is
longer than the previous subarray.
6. If it is the indexes are updated.
advertisement

Time Complexity: O(n ) where n is the number of elements in the array.

2

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
9
Enter array elements
5
6
3
0
7
8
9
1
2
The longest decreasing subarray is
6 3 0
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
5
Enter array elements
9
7
5
3
1
The longest decreasing subarray is
9 7 5 3 1
Java Program to Find the First non-repeated Character in a
String
This is the Java Program to Find the First non-repeated Character in a String

Problem Description
Given a string of characters, find the first non-repeated character in the string.

Example:

String x = “Hi this is Marry”

Output = ‘H’

Problem Solution
Make two new arrays to store the frequency of each character and the indexes of
there occurrences. Iterate through the string to fill the two arrays. Finally, re-iterate through
the new arrays, to find the index of the minimum index of the characters whose frequency
are 1.

Program/Source Code
Here is the source code of the Java Program to Find the First non-repeated Character in a
String. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows
7. The program output is also shown below.
1.  
2. // Java Program to Find the First non-repeated Character in a String.
3.  
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7.  
8. public class NonRepeatedCharacter {
9. // Function to find the first non-repeating character
10. static int firstNonRepeatingCharacter(String str){
11. int[] arrayCount = new int[256];
12. int[] arrayIndex = new int[256];
13. int i;
14. for(i=0; i<str.length(); i++){
15. arrayCount[str.charAt(i)]++;
16. arrayIndex[str.charAt(i)] = i;
17. }
 18. int index = Integer.MAX_VALUE;
19. for(i=0; i<256; i++){
20. if(arrayCount[i] == 1 && arrayIndex[i] < index)
21. index = arrayIndex[i];
22. }
23. return index;
24. }
25. // Function to read user input
26. public static void main(String[] args) {
27. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
28. String str;
29. System.out.println("Enter the string");
30. try {
31. str = br.readLine();
32. } catch (IOException e) {
33. System.out.println("An I/O error occurred");
34. return;
35. }
36. int index = firstNonRepeatingCharacter(str);
37. if(index < str.length())
38. System.out.println("First Non Repeating Character is "
39. + str.charAt(index));
40. else
41. System.out.println("Each character is repeated");
42. }
43. }

Program Explanation
1. In function firstNonRepeatingCharacter(), two arrays arrayCount and arrayIndex are
created.
2. The loop for(i=0; i<str.length(); i++) iterates through the string and counts the frequency
of each character in arrayCount array and the index of the last occurence of a character in
arrayIndex array.
3. The loop for(i=0; i<256; i++) iterates through the two arrays arrayCount and arrayIndex.
4. The condition if(arrayCount[i] == 1 && arrayIndex[i] < index) checks if the frequency of
character is 1 and the second part looks for first non-repeating character.

Time Complexity: O(n) where n is the length of the string.

advertisement
Runtime Test Cases
 
Case 1 (Positive Test Case):
 
Enter the string
Hi this is Marry
First Non-Repeating Character is H
 
Case 2 (Positive Test Case - another example):
 
Enter the string
well well finally you are here
First Non-Repeating Character is f
 
Case 3 (Negative Test Case):
 
Enter the string
WellWell
Each character is repeated

Java Program to Remove Characters that belong to a Mask

String from the Input String
This is the Java Program to Remove Characters that belong to a Mask String from the Input
String

Problem Description
Given a string of characters and a mask string remove all the characters of the mask string
from the first string.
Example:

String x = “We belong to Russia”

Mask = “Wbos”

Output = “e elng t Ruia”

Problem Solution
Count the frequency of each character in the mask string in an array. Now, iterate
through the user string and check each characters frequency in the frequency array. If it is
zero, add that character to the output string.

Program/Source Code
Here is the source code of the Java Program to Remove Characters that belong to a Mask
String from the Input String. The program is successfully compiled and tested using IDE
IntelliJ Idea in Windows 7. The program output is also shown below.
1.  
2. // Java Program to Remove Characters that belong
3. // to a Mask String from the Input String
4.  
5. import java.io.BufferedReader;
6. import java.io.IOException;
7. import java.io.InputStreamReader;
8.  
9. public class RemoveMaskChar {
10. // Function to remove the mask characters
11. static String removeMaskCharacters(String str, String str2){
12. int[] array = new int[256];
13. int i;
14. for(i=0; i<str2.length(); i++){
15. array[str2.charAt(i)]++;
16. }
17. String output="";
18. for(i=0; i<str.length(); i++){
19. if(array[str.charAt(i)] == 0)
20. output+=str.charAt(i);
21. }
22. return output;
23. }
24. // Function to read input and display the output
25. public static void main(String[] args) {
26. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
27. String str;
28. System.out.println("Enter the string");
29. try {
30. str = br.readLine();
31. } catch (IOException e) {
32. System.out.println("An I/O error occurred");
33. return;
34. }
35. String str2;
36. System.out.println("Enter the second string");
37. try {
38. str2 = br.readLine();
 39. } catch (IOException e) {
40. System.out.println("An I/O error occurred");
41. return;
42. }
43. String output = removeMaskCharacters(str,str2);
44. System.out.println("Final String is " + output);
45. }
46. }

Program Explanation
1. In function removeMaskCharacters(), an array is created to count the frequency of each
character in the mask string.
2. The loop for(i=0; i<str2.length(); i++) is used to count the above mentioned frequencies.
3. The loop for(i=0; i<str.length(); i++) is used to iterate through the original string.
4. The condition if(array[str.charAt(i)] == 0) checks if the frequency of the current character
in the array is equal to zero.
5. If it is zero, then the element is added to the output string.

Time Complexity: O(n) where n is the length of the string.

advertisement

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the string
We belong to Russia
Enter the second string
Wbos
Final String is e elng t Ruia
 
Case 2 (Simple Test Case - another example):
 
Enter the string
xyz
Enter the second string
xyz
Final String is

Java Program to Find the Longest SubString Without Any

Repeated Characters
This is the Java Program to Find the Longest SubString Without Any Repeated Characters
Problem Description
Given a string, find and print the longest substring without any repeating characters, that is
all the characters in the substring must be unique.

Example:

String x = “ABBCDFGHC”
Output = “BCDFGH”

Problem Solution
Create a stack and push the first character of the string on it. Now, iterate through the
string, and check whether the current character of the string is present in the stack or not. If
it is present, update the longest substring as necessary.

Program/Source Code
Here is the source code of the Java Program to Find the Longest SubString Without Any
Repeated Characters. The program is successfully compiled and tested using IDE IntelliJ
Idea in Windows 7. The program output is also shown below.
1.  
2. // Java Program to Find the Longest SubString Without Any Repeated
Characters.
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6. import java.util.Stack;
7.  
8. public class LongestNonRepeatedSubstring {
9. // Function to find the longest non-repeating substring
10. static String longestSubstring(String str){
11. Stack<Character> stack = new Stack<>();
12. int last = 1;
13. int prev = 0;
14. String ans = "";
15. int i;
16. int max = -1;
17. stack.push(str.charAt(0));
18. for(i=1; i<str.length(); i++){
19. if(stack.search(str.charAt(i)) != -1){
20. if((i-prev) > max){
21. ans = str.substring(prev, i);
 22. max = i-prev;
23. }
24. prev = i;
25. stack.clear();
26. stack.push(str.charAt(i));
27. }
28. else{
29. stack.push(str.charAt(i));
30. }
31. }
32. if((i-prev) > max){
33. ans = str.substring(prev, i);
34. }
35. return ans;
36. }
37. // Function to read input and display the output
38. public static void main(String[] args) {
39. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
40. String str;
41. System.out.println("Enter the text string");
42. try{
43. str = br.readLine();
44. }catch (Exception e){
45. System.out.println("An error occurred");
46. return;
47. }
48. String ans = longestSubstring(str);
49. System.out.println("The longest substring without any repeated"
50. + " characters is " + ans);
51. }
52. }

Program Explanation
1. In function longestSubstring(), a stack is created to hold the characters and the first
character of the string is pushed onto it.
2. The variables prev and last are used to store the starting and ending indexes of the
substring and max stores the length of the longest substring.
3. The loop for(i=1; i<str.length(); i++) iterates through the string.
4. The condition if(stack.search(str.charAt(i)) != -1) checks if the current character of the
string is already present in the stack.
5. If it is, the condition if((i-prev) > max) checks if the length of the current substring from
prev to i is greater than the previous substring.
6. If it is, the max and ans variables are updated accordingly and the stack is cleared.
7. In case of the condition is point 4 failing, the current character is pushed onto the stack.
8. The longest substring is returned.

Time Complexity: O(n) where n is the length of the string.

advertisement

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the text string
ABBCDFGHC
The longest substring without any repeated characters is BCDFGH
 
Case 2 (Simple Test Case - another example):
 
Enter the text string
XXYYZUIOPZQWERTYKLA
The longest substring without any repeated characters is ZQWERTYKLA

Java Program to Delete Adjacent Pairs of Repeated Characters

This is the Java Program to Delete Adjacent Pairs of Repeated Characters.

Problem Description
Given a string, find and remove all the adjacent pairs of repeated characters.

Example:

String x = “ABBCCCD”
Output = “ACD”

Problem Solution
Create a stack and push the first character of the string on it. Now, iterate through the
string, and check whether the current character of the string is at the top of the stack. If it is,
then pop it off the stack. Form a string from the characters left in the string and reverse it.

Program/Source Code
Here is the source code of the Java Program to Delete Adjacent Pairs of Repeated
Characters. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. // Java Program to Delete Adjacent Pairs of Repeated Characters.
3.  
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7. import java.util.Stack;
8.  
9. public class AdjacentCharacters {
10. // Function to remove adjacent characters
11. static String removeAdjacentRepeatedCharacters(String str){
12. Stack<Character> stack = new Stack<>();
13. int i;
14. stack.push(str.charAt(0));
15. for(i=1; i<str.length(); i++){
16. if(stack.peek() == str.charAt(i)){
17. stack.pop();
18. continue;
19. }
20. stack.push(str.charAt(i));
21. }
22. StringBuffer obj = new StringBuffer();
23. while(!stack.isEmpty()){
24. obj.append(stack.pop());
25. }
26. return obj.reverse().toString();
27. }
28. // Function to read the input and display the output
29. public static void main(String[] args) {
30. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
31. String str;
32. System.out.println("Enter the string");
33. try {
34. str = br.readLine();
35. } catch (IOException e) {
36. System.out.println("An I/O error occurred");
37. return;
38. }
 39. String newString =removeAdjacentRepeatedCharacters(str);
40. System.out.println("The new string is \"" + newString + "\"");
41. }
42. }

Program Explanation
1. In function removeAdjacentRepeatedCharacters(), a stack is created and the first
character of the string is pushed onto the stack.
2. The loop for(i=1; i<str.length(); i++) iterates through the rest of the string.
3. The condition if(stack.peek() == str.charAt(i)) checks if the current character of the string
is equal to the character at the top of the stack.
4. If it is, a character is popped from the stack otherwise the current character of the string
is pushed onto the stack.
5. The loop while(!stack.isEmpty()) add all the characters of the stack to a StringBuffer
object and the reverse of the object is returned.

Time Complexity: O(n) where n is the length of the string.

advertisement

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the string
ABBCCCD
The new string is "ACD"
 
Case 2 (Simple Test Case - another example):
 
Enter the string
XYZ
The new string is "XYZ"

Java Program to Check if There are Any Pythagorean Triplets in

the Array
This is the Java Program to Check if There are Any Pythagorean Triplets in the Array.

Problem Description
Given an array of integers, check for any triplet of elements say a, b, and c where all three
elements form a Pythagorean triplet, that is, c  =
2
a  +
2
b 2

Example:

Array = [1, 3, 4, 5]

Output: 3, 4 and 5

Problem Solution
Use three nested loops, and inside the innermost loop, check for the array elements
satisfying the Pythagorean triplet equivalence, or not.

Program/Source Code
Here is the source code of the Java Program to Check if There are Any Pythagorean
Triplets in the Array. The program is successfully compiled and tested using IDE IntelliJ
Idea in Windows 7. The program output is also shown below.
1.  
2. //Java Program to Check if There are Any Pythagorean Triplets in the Array
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class PythagoreanTriplets {
8. // Function to find and display Pythagorean triplets
9. static void printPythagoreanTriplets(int[] array){
10. int i,j,k;
11. int x,y,z;
12. int count=0;
13. for(i=0;i<array.length;i++){
14. x=array[i];
15. for(j=0;j<array.length;j++){
16. y=array[j];
17. for(k=0;k<array.length;k++){
18. z=array[k];
19. if((z*z)==(x*x + y*y)){
20. count++;
21. System.out.println(x+", "+y+", "+z);
22. return;
23. }
24. }
25. }
 26. }
27. System.out.println("No pythagorean triplets exist in the array");
28. }
29. // Function to read user input
30. public static void main(String[] args) {
31. int size;
32. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
33. System.out.println("Enter the array size");
34. try {
35. size = Integer.parseInt(br.readLine());
36. } catch (Exception e) {
37. System.out.println("Invalid Size");
38. return;
39. }
40. int[] array = new int[size];
41. int i;
42. System.out.println("Enter array elements");
43. for (i = 0; i < array.length; i++) {
44. try {
45. array[i] = Integer.parseInt(br.readLine());
46. } catch (Exception e) {
47. System.out.println("An error occurred");
48. }
49. }
50. printPythagoreanTriplets(array);
51. }
52. }

Program Explanation
1. In function printPythagoreanTriplets(), triple nested loops are used to check every
combination of array elements.
2. If any combination of elements satisfies the Pythagorean triplet criteria if((z*z)==(x*x +
y*y)), then that triplet is printed and we return from the function.
3. If Pythagorean triplet existed, then a suitable message is displayed.

Runtime Test Cases

advertisement
 
Case 1 (Positive Test Case):
 
Enter the array size
4
Enter array elements
1
3
4
5
3, 4, and 5
 
Case 2 (Negative Test Case):
 
Enter the array size
4
Enter array elements
1
2
3
4
No pythagorean triplets exist in the array

Java Program to Print Elements Which Occurs Even Number of

Times
This is the Java Program to Print Elements Which Occurs Even Number of Times.

Problem Description
Given an array of elements, print the elements whose frequency is even.
Example:

array = {5, 5, 2, 2, 2, 4, 4, 1, 7, 1}
Output = 5 4 1

Problem Solution
Create a separate array of boolean values of the same length as that of the original array,
and initialize it to false. Iterate through the array to find the frequency of the frequency
of each element and also mark the index which is already visited as true, to avoid
printing the same element twice. Print the elements with even frequency.

Program/Source Code
Here is the source code of the Java Program to Print Elements Which Occurs Even Number
of Times. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Print Elements Which Occurs Even Number of Times
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class EvenFrequencyElements {
8. // Function to print even frequency elements
9. static void printEvenFrequencyElements(int[] array){
10. boolean[] check = new boolean[array.length];
11. int i,j,count;
12. for(i=0; i<array.length; i++){
13. if(!check[i]){
14. count=1;
15. for(j=i+1;j<array.length;j++){
16. if(array[j] == array[i]){
17. count++;
18. check[j]=true;
19. }
20. }
21. if(count%2==0){
22. System.out.println(array[i]);
23. }
24. }
25. }
26. }
27. // Main function to read input
28. public static void main(String[] args) {
29. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
30. int size;
31. System.out.println("Enter the size of the array");
32. try {
33. size = Integer.parseInt(br.readLine());
34. } catch (Exception e) {
35. System.out.println("Invalid Input");
36. return;
37. }
38. int[] array = new int[size];
39. System.out.println("Enter array elements");
40. int i;
41. for (i = 0; i < array.length; i++) {
42. try {
43. array[i] = Integer.parseInt(br.readLine());
44. } catch (Exception e) {
 45. System.out.println("An error occurred");
46. return;
47. }
48. }
49. System.out.println("The even frequency elements are");
50. printEvenFrequencyElements(array);
51. }
52. }

Program Explanation
1. In function printEvenFrequencyElements(), a boolean array check is created to store the
status if the array element is already visited or not.
2. The loop for(i=0; i<array.length; i++) iterates through the array.
3. The condition if(!check[i]) checks if the element is already visited.
4. If the element is not visited already, then the count is initialized to 1 and a nested loop
for(j=i+1;j<array.length;j++).
5. The elements with even frequency are printed.

Time Complexity: O(n ) where n is the number of elements in the array.

2

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
10
Enter array elements
5
5
2
2
2
4
4
1
7
1
The even frequency elements are
5 4 1
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
9
Enter array elements
1
2
1
2
3
3
3
8
9
The even frequency elements are
1 2

Java Program to Check if Any Anagram of the String is a

Palindrome
This is the Java Program to Check if Any Anagram of the String is a Palindrome

Problem Description
Given a string, check whether any of its anagrams is palindrome or not. An anagram is just
a new word formed by permuting the letters of the string.
Example:

String x = “ACBDABD”

Output = Yes

Problem Solution
Count the frequency of each character in the string. If there is only one character,
whose frequency is odd, and rest of the frequencies are even, then print Yes, otherwise
print No.

Program/Source Code
Here is the source code of the Java Program to Check if Any Anagram of the String is a
Palindrome. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. // Java Program to Check if Any Anagram of the String is a Palindrome
3.  
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7.  
8. public class PalindromeAnagram {
 9. // Function check if any palindrome anagram exists
10. static boolean anagram(String str){
11. int[] arr = new int[256];
12. int i;
13. for(i=0; i<str.length(); i++){
14. arr[str.charAt(i)]++;
15. }
16. int odd,even;
17. odd = even =0;
18. for(i=0; i<256; i++){
19. if(arr[i] % 2 == 0)
20. even++;
21. else
22. odd++;
23. }
24. boolean result;
25. if(odd > 1)
26. return false;
27. return true;
28. }
29. // Function to read input and display the output
30. public static void main(String[] args) {
31. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
32. String str;
33. System.out.println("Enter the string");
34. try {
35. str = br.readLine();
36. } catch (IOException e) {
37. System.out.println("An I/O error occurred");
38. return;
39. }
40. boolean result = anagram(str);
41. if(result)
42. System.out.println("Palindrome anagrams exist");
43. else
44. System.out.println("No palindrome anagrams exists");
45. }
46. }

Program Explanation
1. In function anagram(), an array is created to length 256 to count the frequency of various
characters as per ASCII code.
2. The loop for(i=0; i<str.length(); i++) traverses through the whole string and counts the
frequency of each character.
3. The loop for(i=0; i<256; i++) traverses through the array and count the number of
characters having even frequencies and odd frequencies.
4. The condition if(odd > 1) checks if the number of characters having odd frequency is
more than 1, false is returned, otherwise true is returned.

Time Complexity: O(n) where n is the length of the string.

advertisement

Runtime Test Cases

 
Case 1 (Positive Test Case):
 
Enter the string
ACBDABD
Palindrome anagrams exist
 
Case 2 (Negative Test Case):
 
Enter the string
bcddacbaaf
No palindrome anagrams exists

Java Program to Find the Sum and Product of Elements in a

Row/Column
This is the Java Program to Find the Sum and Product of Elements in a Row/Column.

Problem Description
Given a square matrix, print the sum and product of the elements in each row and column.
Example:
Matrix:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Output:
Sum Product
10     24
28     585
26     1680
32     1680
42     11880
36     3465
58     43680
40     6144

Problem Solution
Traverse through the matrix, and calculate the sum and product of each row and
column elements and display it.

Program/Source Code
Here is the source code of the Java Program to Find the Sum and Product of Elements in a
Row/Column. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Find the Sum and Product of Elements in a Row/Column
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class SumAndProduct {
8. // Function to calculate sum and products
9. static void displayOutput(int[][] matrix)
10. {
11. int i,j,sumr,productr,sumc,productc;
12. System.out.println("\t\tSum Product");
13. for(i=0; i<matrix.length; i++){
14. sumr = sumc = 0;
15. productr = productc = 1;
16. for(j=0; j<matrix[i].length; j++){
17. sumr+=matrix[i][j];
18. sumc+=matrix[j][i];
19. productr*=matrix[i][j];
20. productc*=matrix[j][i];
21. }
 22. System.out.format("%s %d %3d
%2d\n","Row",i+1,sumr,productr);
23. System.out.format("%s %d %3d
%2d\n","Col",i+1,sumc,productc);
24. }
25. }
26. // Function to read user input
27. public static void main(String[] args) {
28. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
29. int order;
30. System.out.println("Enter the order of the matrix");
31. try {
32. order = Integer.parseInt(br.readLine());
33. } catch (Exception e) {
34. System.out.println("An error occurred");
35. return;
36. }
37. int[][] matrix = new int[order][order];
38. System.out.println("Enter matrix elements");
39. int i, j;
40. for (i = 0; i < order; i++) {
41. for (j = 0; j < order; j++) {
42. try {
43. matrix[i][j] = Integer.parseInt(br.readLine());
44. } catch (Exception e) {
45. System.out.println("An error occurred");
46. return;
47. }
48. }
49. }
50. System.out.println("Tha matrix is");
51. for (i = 0; i < order; i++) {
52. for (j = 0; j < order; j++) {
53. System.out.print(matrix[i][j] + "\t");
54. }
55. System.out.println();
56. }
57. displayOutput(matrix);
58. }
59. }

Program Explanation
1. In function displayOutput(), four variables productr,productc,sumr and sumc are created.
2. The loop for(i=0; i< matrix.length; i++) traverses through the rows of the matrix and it sets
the variables productr, productc to 1 and sumr, sumc to 0.
3. The nested loop for(j=0; j<matrix[i].length; j++) calculates the sum and products of
elements in each row and column.
4. Finally, the output is displayed.

Time Complexity: O(nm) where n is the number of rows and m is the number of columns
in the matrix respectively.
advertisement

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the order of the matrix
4
Enter matrix elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
The matrix is
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Sum Product
Row 1 10 24
Col 1 28 585
Row 2 26 1680
Col 2 32 1680
Row 3 42 11880
Col 3 36 3465
Row 4 58 43680
Col 4 40 6144
Java Program to Find the First Capital Letter/Small
Letter/Vowel/Consonant/Number/White Space/Special
Character in a Given String
This is the Java Program to Find the First Capital Letter/Small
Letter/Vowel/Consonant/Number/White Space/Special Character in a Given String.

Problem Description
Given a string, find the first position of the capital letter, small letter, vowel, consonant,
whitespace, and special character if present in the string.
Example:

String x = “Ac @”

Output =
Capital letter = 1
Small letter = 2
Vowel = 1
Consonant = 2
Whitespace = 3
Special Character = 4

Problem Solution
Iterate through the string and find the first positions.

Program/Source Code
Here is the source code of the Java Program to Find the First Capital Letter/Small
Letter/Vowel/Consonant/Number/White Space/Special Character in a Given String. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. // Java Program to Find the First Capital Letter/Small Letter/Vowel
3. // Consonant/Number/White Space/Special Character in a Given String
4.  
5. import java.io.BufferedReader;
6. import java.io.InputStreamReader;
7.  
8. public class FirstIndexes {
9. // Function to display the output
10. static void firstIndexes(String str){
11. boolean consonant,vowel,capital,small,special,number,space;
12. consonant = vowel = capital = small = special = number = space
=false;
13. int i;
14. char ch;
15. int count = 0;
16. for(i=0; i<str.length(); i++){
17. if(count == 7)
18. break;
19. ch = str.charAt(i);
20. if(!space && ch == ' '){
21. System.out.println("The index of first whitespace is " +
(i+1));
22. space = true;
23. count++;
24. }
25. else if(!number && Character.isDigit(ch)){
26. System.out.println("The index of first number is " +
(i+1));
27. number = true;
28. count++;
29. }
30. if(Character.isLetter(ch)){
31. if(!small && Character.isLowerCase(ch)){
32. System.out.println("The index of first lowercase
character is "
33. +
(i+1));
34. small = true;
35. count++;
36. }
37. else if(!capital && Character.isUpperCase(ch)){
38. System.out.println("The index of first uppercase
character is "
39. +
(i+1));
40. capital = true;
41. count++;
42. }
43. if(!vowel || !consonant){
44. ch = Character.toLowerCase(ch);
45. if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o'
46. || ch == 'u'){
47. System.out.println("The index of first vowel is "
48. + (i+1));
49. vowel = true;
50. count++;
51. }
52. else{
53. System.out.println("The index of first consonant is
"
54. +
(i+1));
55. consonant = true;
56. count++;
57. }
58. }
59. }
60. else if(!special && ch != ' '){
61. System.out.println("The index of first special character is
"
62. +
(i+1));
63. special = true;
64. count++;
65. }
66. }
67. }
68. // Function to read the string
69. public static void main(String[] args) {
70. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
71. String str;
72. System.out.println("Enter the string");
73. try {
74. str = br.readLine();
75. } catch (Exception e) {
76. System.out.println("An I/O error occurred");
77. return;
78. }
79. System.out.println("The first indexes are");
80. firstIndexes(str);
81. }
82. }
Program Explanation
1. In function firstIndexes(), several boolean variables
consonant,vowel,capital,small,special,number and space are created and initialized to false.
2. The loop for(i=0; i<str.length(); i++) is used to iterate through the string.
3. The condition if(count == 7) checks whether each type of character is found, if is true,
break from the loop.
4. The condition if(!space && ch == ‘ ‘) checks if the given character is a whitespace and
displays it, if it is.
5. Similarly, the other else-if conditions check for remaining types of characters and display
them.

Time Complexity: O(n) where n is the length of the string.

advertisement

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the string
Ac @
The first indexes are
The index of first uppercase character is 1
The index of first vowel is 1
The index of first lowercase character is 2
The index of first consonant is 2
The index of first whitespace is 3
The index of first special character is 4
 
Case 2 (Simple Test Case - another example):
 
Enter the string
@Timbuchalka
The first indexes are
The index of first special character is 1
The index of first uppercase character is 2
The index of first consonant is 2
The index of first lowercase character is 3
The index of first vowel is 3

Java Program to Find Address of an Array Element Given the

Base Address
This is the Java Program to Find Address of an Array Element Given the Base Address.
Problem Description
Given the base address of an array, and the element size. Find out the address of the given
element.

Example:
Base address = 2400
Element Size = 5
Element index = 6

Output:
Element address = 2430

Problem Solution
The address of an array element at index i, and the base address b, with a given element
size s, is calculated using the formula

Element address = b + i*s.

Program/Source Code
Here is the source code of the Java Program to Find Address of an Array Element Given
the Base Address. The program is successfully compiled and tested using IDE IntelliJ Idea
in Windows 7. The program output is also shown below.
1.  
2. // Java Program to Find Address of an Array Element Given the Base Address.
3.  
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7.  
8. public class ArrayElementAddress {
9. // Function to read input and display the output
10. public static void main(String args[])throws IOException
11. {
12. BufferedReader br=new BufferedReader(new
InputStreamReader(System.in));
13. long size_of_element,base_address,index;
14. System.out.println("Enter the base address of the array(>=0)");
15. try{
16. base_address=Long.parseLong(br.readLine());
17. }
 18. catch(Exception e){
19. System.out.println("Invalid Base Address");
20. return;
21. }
22. System.out.println("Enter the size of the array element in
bytes(>0)");
23. try{
24. size_of_element=Long.parseLong(br.readLine());
25. }
26. catch(Exception e){
27. System.out.println("Invalid Size");
28. return;
29. }
30. System.out.println("Enter the index of the element(>=0)");
31. try{
32. index=Long.parseLong(br.readLine());
33. }
34. catch(Exception e){
35. System.out.println("Invalid Index");
36. return;
37. }
38. if( base_address < 0 || size_of_element <=0 || index < 0 ){
39. System.out.println("Invalid Input");
40. }
41. long element_Address;
42. element_Address = base_address + (size_of_element * index);
43. System.out.println("The address of the element at index "+ index
44. +" is "+element_Address);
45. }
46. }

Program Explanation
1. In main() function the base address, size of the element and the index of an element are
entered.
2. The condition if( base_address < 0 || size_of_element <=0 || index < 0 ) checks if any of
the three values is invalid.
3. If any one of the input is invalid, the program terminates after displaying a suitable
message.
4. Otherwise, the statement element_Address = base_address + (size_of_element * index);
calculates the address of the element and it is displayed.
advertisement
Time Complexity: O(1).

Runtime Test Cases

 
 
Case 1 (Simple Test Case):
 
Enter the base address of the array
2400
Enter the size of the array element in bytes
5
Enter the index of the element
6
The address of the element at index 6 is 2430
 
Case 2 (Simple Test Case - another example):
 
Enter the base address of the array
2800055680
Enter the size of the array element in bytes
10
Enter the index of the element
45
The address of the element at index 45 is 2800056130

Java Program to Find Repeated Elements and the Frequency of

Repetition
This is the Java Program to Find Repeated Elements and the Frequency of Repetition.

Problem Description
Given an array of integers, find and print the repeated elements and their frequency of
repetition.

Example:
Array: [1,2,3,4,5,5,3]

Output:
Element—–>Frequency

3—–>2
5—–>2

Problem Solution
Sort the array, and find the frequency of each repeated element and print it.
Program/Source Code
Here is the source code of the Java Program to Find Repeated Elements and the
Frequency of Repetition. The program is successfully compiled and tested using IDE IntelliJ
Idea in Windows 7. The program output is also shown below.
1.  
2. // Java Program to Find Repeated Elements and the Frequency of Repetition.
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6. import java.util.Arrays;
7.  
8. public class RepeatedElementsFrequency {
9. // Function to display the repeated elements and their frequencies
10. static void displayOutput(int[] array){
11. int i,j,frequency;
12. for(i=0; i<array.length; i++){
13. frequency = 1;
14. for(j=i+1; j<array.length; j++){
15. if(array[j] == array[i]){
16. frequency++;
17. }
18. else{
19. break;
20. }
21. }
22. i=j-1;
23. if(frequency > 1){
24. System.out.println("The element is " + array[i]
25. + " and its frequency is " + frequency);
26. }
27. }
28. }
29. // Function to read input
30. public static void main(String[] args){
31. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
32. int size;
33. System.out.println("Enter the size of the array");
34. try {
35. size = Integer.parseInt(br.readLine());
36. } catch (Exception e) {
 37. System.out.println("Invalid Input");
38. return;
39. }
40. int[] array = new int[size];
41. System.out.println("Enter array elements");
42. int i;
43. for (i = 0; i < array.length; i++) {
44. try {
45. array[i] = Integer.parseInt(br.readLine());
46. } catch (Exception e) {
47. System.out.println("An error occurred");
48. return;
49. }
50. }
51. Arrays.sort(array);
52. displayOutput(array);
53. }
54. }

Program Explanation
1. In function displayOutput(), a variable frequency is created.
2. The loop for(i=0; i<array.length; i++) is used to iterate through the array and it initializes
frequency to 1 in each iteration.
3. The nested loop for(j=i+1; i<array.length; j++) traverses the remaining part of the array
and count the elements frequency.
4. If the frequency is greater than 1, than the element is displayed along with frequency.
advertisement

Time Complexity: O(n*log(n)) where n is the number of elements in the array.

Runtime Test Cases

 
 
Case 1 (Simple Test Case):
 
Enter the size of the array
7
Enter array elements
1
2
3
4
5
5
3
The element is 3 and its frequency is 2
The element is 5 and its frequency is 2
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
5
Enter array elements
1
1
1
1
1
The element is 1 and its frequency is 5

ava Program to Cyclically Permute the Elements of an Array

This is the Java Program to Cyclically Permute the Elements of an Array.

Problem Description
Given an array of integers, cyclically permute its elements, that is, shift each array element
to the left by one index. The first value will go into the last index.

Example:
Array: [1,2,3,4,5]

Output: [2,3,4,5,1]

Problem Solution
Store the first value in a variable and shift all the remaining elements to the left using a
loop. Finally, put the first value into the last index.

Program/Source Code
Here is the source code of the Java Program to Cyclically Permute the Elements of an
Array. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows
7. The program output is also shown below.
1.  
2. // Java Program to Cyclically Permute the Elements of an Array.
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6. import java.util.Arrays;
 7.  
8. public class CyclicallyPermuteArray {
9. // Function to cyclically permute the array
10. static void cyclicallyPermute(int[] array){
11. int x = array[0];
12. int i;
13. for(i=0; i<array.length-1; i++)
14. array[i] = array[i+1];
15. array[i] = x;
16. }
17. // Function to read user input and display the output
18. public static void main(String[] args) {
19. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
20. int size;
21. System.out.println("Enter the size of the array");
22. try {
23. size = Integer.parseInt(br.readLine());
24. } catch (Exception e) {
25. System.out.println("Invalid Input");
26. return;
27. }
28. int[] array = new int[size];
29. System.out.println("Enter array elements");
30. int i;
31. for (i = 0; i < array.length; i++) {
32. try {
33. array[i] = Integer.parseInt(br.readLine());
34. } catch (Exception e) {
35. System.out.println("An error occurred");
36. return;
37. }
38. }
39. System.out.println("The initial array is");
40. System.out.println(Arrays.toString(array));
41. System.out.println();
42. cyclicallyPermute(array);
43. System.out.println("The array after permutation is");
44. System.out.println(Arrays.toString(array));
45. }
46. }

Program Explanation
1. In function cyclicallyPermute(), the loop for(i=0; i<array.length-1; i++) traverses through
the array and shifts each element one position before.
2. The first value of the array is stored in variable x before the loop.
3. Finally, the last element of the array is set to x.
advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
The initial array is
[1, 2, 3, 4, 5]
 
The array after permutation is
[2, 3, 4, 5, 1]
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
5
Enter array elements
9
8
7
6
5
The initial array is
[9, 8, 7, 6, 5]
 
The array after permutation is
[8, 7, 6, 5, 9]

Java Program to Print Elements Which Occur Odd Number of

Times
This is the Java Program to Print Elements Which Occur Odd Number of Times.

Problem Description
Given an array of integers, print all the elements whose frequency are odd.

Example:
Array = [5, 4, 4, 2, 1]

Output: 5 2 1.

Problem Solution
Iterate through the array, and for every element, count its frequency in the array using a
nested loop, and mark all the occurrences of that element as true in another boolean array,
just to avoid repeatedly checking it again. Print the elements if its frequency is odd.

Program/Source Code
Here is the source code of the Java Program to Print Elements Which Occur Odd Number
of Times. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Print Elements Which Occur Odd Number of Times
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class OddFrequencyElements {
8. // Function to print odd frequency elements
9. static void printOddFrequencyElements(int[] array){
10. boolean[] check = new boolean[array.length];
11. int i,j,count;
12. for(i=0; i<array.length; i++){
13. if(!check[i]){
14. count=1;
15. for(j=i+1;j<array.length;j++){
16. if(array[j] == array[i]){
17. count++;
18. check[j]=true;
19. }
20. }
21. if(count%2!=0){
22. System.out.print(array[i] + " ");
23. }
24. }
25. }
 26. }
27. // Function to read the input
28. public static void main(String[] args) {
29. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
30. int size;
31. System.out.println("Enter the size of the array");
32. try {
33. size = Integer.parseInt(br.readLine());
34. } catch (Exception e) {
35. System.out.println("Invalid Input");
36. return;
37. }
38. int[] array = new int[size];
39. System.out.println("Enter array elements");
40. int i;
41. for (i = 0; i < array.length; i++) {
42. try {
43. array[i] = Integer.parseInt(br.readLine());
44. } catch (Exception e) {
45. System.out.println("An error occurred");
46. return;
47. }
48. }
49. System.out.println("The odd frequency elements are");
50. printOddFrequencyElements(array);
51. }
52. }

Program Explanation
1. In function printOddFrequencyElements(), a boolean array check is created to store the
status if the array element is already visited or not.
2. The loop for(i=0; i<array.length; i++) iterates through the array.
3. The condition if(!check[i]) checks if the element is already visited.
4. If the element is not visited already, then the count is initialized to 1 and a nested loop
for(j=i+1;j<array.length;j++).
5. The elements with odd frequency are printed.
advertisement

Time Complexity: O(n ) where n is the number of elements in the array.

2
Runtime Test Cases
 
Case 1 (Simple Test Case):
 
Enter the size of the array
5
Enter array elements
5
4
4
2
1
The odd frequency elements are
5 2 1
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
8
Enter array elements
6
5
5
4
3
2
1
1
The odd frequency elements are
6 4 3 2

Java Program to Reverse a String Word by Word in Place

This is the Java Program to Reverse a String Word by Word in Place

Problem Description
Given a string, reverse each word in its place, where words are separated by whitespace.

Example:

String x = “We belong to Russia”

Output = “eW gnoleb ot aissuR”

Problem Solution
Split the given string into various substrings, whenever space is encountered. Reverse
each substring and create a new string from the reversed substrings.
Program/Source Code
Here is the source code of the Java Program to Reverse a String Word by Word in Place.
The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. // Java Program to Reverse a String Word by Word in Place.
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class ReverseWordsInPlace {
8. // Function to reverse the string
9. static String reverseString(String str) {
10. String[] words = str.split(" ");
11. String rev = "";
12. int i, j;
13. for (i = 0; i < words.length; i++) {
14. StringBuffer sb = new StringBuffer(words[i]);
15. rev+=sb.reverse().toString();
16. rev+=" ";
17. }
18. return rev;
19. }
20. // Function to read the input and display the output
21. public static void main(String[] args) {
22. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
23. System.out.println("Enter the text string");
24. String str;
25. try{
26. str=br.readLine();
27. }
28. catch(Exception e){
29. System.out.println("Error reading input");
30. return;
31. }
32. String rev = reverseString(str);
33. System.out.println("The reverse of the string word by word in place
is\n");
34. System.out.println(rev);
35. }
 36. }

Program Explanation
1. In function reverseString(), the string str is split into various tokens using split function
and the resulting array of tokens is stored in variable words.
2. The loop for (i = 0; i < words.length; i++) traverses through the words array.
3. The nested loop for (j = words[i].length() – 1; j >= 0; j–) traverses the various words in
reverse order, adding each character to the rev string.
4. Finally the rev string is displayed.

Time Complexity: O(n) where n is the length of the string.

advertisement

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the text string
We belong to Russia
The reverse of the string word by word in place is
eW gnoleb ot aissuR
 
Case 2 (Simple Test Case - another example):
 
Enter the text string
Hello I am Jane
The reverse of the string word by word in place is
olleH I ma enaJ

Java Program to Convert a String to an Integer Array

This is the Java Program to Convert a String to an Integer Array.

Problem Description
Given a string consisting of various numbers separated by spaces, convert it into an array
of Integers, such that every number occupies a position in the array, and for every invalid
number, there is a -1 in the array.

Example:
For the String str = “19 46 8999 abc 133”;
The array will be [19, 46, 8999, -1, 133].

Problem Solution
The idea is to split the string into various substrings whenever space is
encounteredwhile traversing through the string, and then convert those substrings into the
integers they represent.

Program/Source Code
Here is the source code of the Java Program to Convert a String to an Integer Array. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Convert a String to an Integer Array
3.  
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7.  
8. public class StringToIntegerArray {
9. // Function to convert String into an Integer array
10. static int[] toIntegerArray(String str){
11. int
12. String[] splitArray = str.split(" ");
13. int[] array = new int[splitArray.length];
14. for(i=0;i<splitArray.length;i++)
15. {
16. try {
17. array[i] = Integer.parseInt(splitArray[i]);
18. } catch (NumberFormatException e) {
19. array[i]=-1;
20. }
21. }
22. return array;
23. }
24. // main function to read the string
25. public static void main(String[] args) {
26. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
27. String str;
28. System.out.println("Enter the string");
29. try {
30. str = br.readLine();
31. }
32. catch (IOException e){
 33. System.out.println("An I/O error occurred");
34. return;
35. }
36. int i;
37. int[] array=toIntegerArray(str);
38. System.out.println("The contents of the array are");
39. for(i=0;i<array.length;i++){
40. System.out.print(array[i]+" ");
41. }
42. }
43. }

Program Explanation
1. In function toIntegerArray(), the string is split into various tokens using s.split(” “)
statement.
2. The loop for(i=0;i<splitArray.length;i++) is used to iterate through the array of tokens.
3. Using a try block, the current token is converted into integer through
Integer.parseInt(splitArray[i]).
4. If the conversions fails, the catch block catches the failure and sets the value of array[i] to
-1.

Time Complexity: O(n) where n is the length of the string.

Runtime Test Cases

 
Case 1 (Simple Test Case - all integers):
 
Enter the string
12 23 34 45 56 67 78 89
The contents of the array are
12 23 34 45 56 67 78 89
 
Case 2 (Simple Test Case - all strings):
 
Enter the string
abc pqr xyz
The contents of the array are
-1 -1 -1
 
Case 3 (Simple Test Case - mixed values):
 
Enter the string
99999 z 1244765 989
The contents of the array are
99999 -1 1244765 989
Java Program to Find the Smallest Positive Integer Missing in
an Unsorted Integer Array
This is the Java Program to Find the Smallest Positive Integer Missing in an Unsorted
Integer Array.

Problem Description
Given an array of integers, find out the smallest positive integer missing from the array.

Example:
Array = [-1, -3, 3, 2, 8 ,6]

Output: 1.

Problem Solution
First sort the array. Then initialize a variable to 1 and using a loop scan through the array.
Check the value of the variable if it matches the current array element, increment it if that is
the case. The value of the variable after the loop is the smallest positive missing integer.

Program/Source Code
Here is the source code of the Java Program to Find the Smallest Positive Integer Missing
in an Unsorted Integer Array. The program is successfully compiled and tested using IDE
IntelliJ Idea in Windows 7. The program output is also shown below.
1.  
2. //Java Program to Find the Smallest Positive Integer Missing in
3. //an Unsorted Integer Array
4.  
5. import java.io.BufferedReader;
6. import java.io.InputStreamReader;
7.  
8. public class SmallestPositiveInteger {
9. // Function to find the smallest positive missing integer
10. static int findSmallestPositiveMissingInteger(int[] array){
11. Arrays.sort(array);
12. int j,i = 1;
13. for(j = 0; j<array.length; j++){
14. if(array[j] == i){
15. i++;
16. }
17. }
 18. return i;
19. }
20. // Function to read input and display the output
21. public static void main(String[] args) {
22. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
23. int size;
24. System.out.println("Enter the size of the array");
25. try {
26. size = Integer.parseInt(br.readLine());
27. } catch (Exception e) {
28. System.out.println("Invalid Input");
29. return;
30. }
31. int[] array = new int[size];
32. System.out.println("Enter array elements");
33. int i;
34. for (i = 0; i < array.length; i++) {
35. try {
36. array[i] = Integer.parseInt(br.readLine());
37. } catch (Exception e) {
38. System.out.println("An error occurred");
39. return;
40. }
41. }
42. int missing = findSmallestPositiveMissingInteger(array);
43. System.out.println("The smallest positive missing integer is " +
missing);
44. }
45. }

Program Explanation
1. In function findSmallestPositiveMissingInteger, firstly the array is sorted.
2. Then, the loop for(j = 0; j<array.length; j++) traverses the array to find the smallest
positive missing integer.
3. Finally, the smallest positive missing integer i is returned.
advertisement

Time Complexity: O(n*(log(n)) ) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
6
Enter array elements
-1
-3
3
2
8
6
The smallest positive missing integer is 1
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
5
Enter array elements
-1
-2
-3
-4
-5
The smallest positive missing integer is 1

Java Program to Solve the passing Car Codility Problem

This is the Java Program to Solve the passing Car Codility Problem.

Problem Description
Given a boolean array of 0’s and 1’s, where 0’s represent cars going to east and 1’s
represent cars going to the west.
Find out the pairs of the cars that will cross each other, that is, the pairs of cars going in
another direction.

Example:
ArrayOne = [1, 0, 1, 1, 0, 0, 1, 0] 
Output
5
Explanation:
The last 0 has no 1 following it, so their will be no car pairs crossing each other.
The 0’s at positions 5 and 6, have a 1 following them, so there will be two car pairs crossing
each other.
The 0 at position 2, have three 1’s following it, so there will be 3 car pairs crossing each
other.
So, total 5 car pairs are crossing each other.

Problem Solution
Traverse from the right end of the array and count the number of 1’s encountered,
whenever a 0 is encountered, add the number of 1’s obtained till that point to the number of
pairs and continue traversing.

Program/Source Code
Here is the source code of the Java Program to Solve the passing Car Codility Problem.
The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. // Java Program to Solve the passing Car Codility Problem
3. import java.io.BufferedReader;
4. import java.io.InputStreamReader;
5.  
6. public class CarsCodilityProblem {
7. // Function to count the number of pairs
8. static int passingPairs(int[] array){
9. int pairs=0;
10. int count=0;
11. int i;
12. for(i = array.length-1; i>=0; i--){
13. if(array[i] == 1)
14. {
15. count++;
16. }
17. else{
18. pairs+=count;
19. }
20. }
21. return pairs;
22. }
23. // Function to read input and display the output
24. public static void main(String[] args) {
25. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
26. int size;
27. System.out.println("Enter the size of the array");
 28. try {
29. size = Integer.parseInt(br.readLine());
30. } catch (Exception e) {
31. System.out.println("Invalid Input");
32. return;
33. }
34. int[] array = new int[size];
35. System.out.println("Enter the binary array elements only 0 and 1");
36. int i;
37. for (i = 0; i < array.length; i++) {
38. try {
39. array[i] = Integer.parseInt(br.readLine());
40. } catch (Exception e) {
41. System.out.println("An error Occurred");
42. }
43. }
44. int noOfPairs = passingPairs(array);
45. System.out.println("The number of car pairs passing each other are
"
46. +
noOfPairs);
47. }
48. }

Program Explanation
1. In function passingPairs(), the variable pairs and count are initialized to zero.
2. The loop for(i = array.length-1; i>=0; i–) traverses the array from right to left.
3. The condition if(array[i] == 1) counts the number of 1’s encountered till present.
4. The else part, indicating the value zero, adds the number of 1’s encountered to the pairs,
since these car pairs are travelling in the opposite direction.
5. The pairs variable is returned.

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
8
Enter the binary array elements only 0 and 1
1
0
1
1
0
0
1
0
The number of car pairs passing each other are 5
 
Case 2 (Simple Test Case - sorted array) :
 
Enter the size of the array
6
Enter the binary array elements only 0 and 1
0
0
0
1
1
1
The number of car pairs passing each other are 9
 
Case 3 (Simple Test Case - reverse sorted array):
 
Enter the size of the array
4
Enter the binary array elements only 0 and 1
1
1
0
0
The number of car pairs passing each other are 0

Java Program to Replace the Element with its Next Greatest

Element, Rightmost Element will be Replaced by 0
This is the Java Program to Replace the Element with its Next Greatest Element, Rightmost
Element will be Replaced by 0.

Problem Description
Given an array of integers, replace each element of the array with the greatest element
present on the right side of the element, in the array. The rightmost element or the last
element should be replaced by 0.

Example:
Array = [-1, -3, 3, 2, 8 ,6]

Output: [8, 8, 8, 8, 6, 0].

Problem Solution
Traverse the array from right to left and keep track of the maximum element found. Replace
each element with the current maximum element, until the maximum changes. At the point
of new maximum, swap the current element with the current maximum and continue.
Finally, update the rightmost element to zero.

Program/Source Code
Here is the source code of the Java Program to Replace the Element with its Next Greatest
Element, Rightmost Element will be Replaced by 0. The program is successfully compiled
and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.
1.  
2. //Java Program to Replace the Element with its Next Greatest Element,
3. //Rightmost Element will be Replaced by 0
4.  
5. import java.io.BufferedReader;
6. import java.io.InputStreamReader;
7.  
8. public class ReplaceNextGreatest {
9. // Function to replace all the array elements
10. // with the next greatest element
11. static void nextGreatest(int[] array){
12. int max=array[array.length-1];
13. int i,temp;
14. for(i= array.length-2; i>=0; i--){
15. temp = array[i];
16. array[i] = max;
17. if(temp > max)
18. max= temp;
19. }
20. array[array.length-1] = 0;
21. }
22. // Function to read input and display the output
23. public static void main(String[] args) {
24. BufferedReader br = new BufferedReader
25. (new InputStreamReader(System.in));
26. int size;
27. System.out.println("Enter the size of the array");
28. try {
29. size = Integer.parseInt(br.readLine());
30. } catch (Exception e) {
 31. System.out.println("Invalid Input");
32. return;
33. }
34. int[] array = new int[size];
35. System.out.println("Enter array elements");
36. int i;
37. for (i = 0; i < array.length; i++) {
38. try {
39. array[i] = Integer.parseInt(br.readLine());
40. } catch (Exception e) {
41. System.out.println("An error occurred");
42. return;
43. }
44. }
45. System.out.println("The initial array is");
46. for(i = 0;i < array.length; i++){
47. System.out.print(array[i] + " ");
48. }
49. nextGreatest(array);
50. System.out.println("\nThe final array is");
51. for(i = 0;i < array.length; i++){
52. System.out.print(array[i] + " ");
53. }
54. }
55. }

Program Explanation
1. In function nextGreatest(), the variable max is initialized to the last value in the array (int
max=array[array.length-1]).
2. The loop for(i=array.length-1; i>=0; i–) traverses the array from right to left.
3. The element array[i] is stored in a variable temp and its value is changed to max.
4. The variable max is updated using the condition if(temp > max).
5. Finally, the last value in the array is set to zero.
advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
6
Enter array elements
-1
-3
3
2
8
6
The initial array is
-1 -3 3 2 8 6
The final array is
8 8 8 8 6 0
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
5
Enter array elements
5
4
3
2
1
The initial array is
5 4 3 2 1
The final array is
4 3 2 1 0

Java Program to Solve the Dutch National Flag Problem

This is the Java Program to Solve the Dutch National Flag Problem.

Problem Description
Given an array of 0’s, 1’s and 2’s, all the elements in the random order,  sort the array in
linear time, without using extra space. This is known as the Dutch National Flag problem.
Example:

Array = [1 0 2 2 0 1]

Output
Array = [0 0 1 1 2 2]

Problem Solution
The idea here is to divide the array into three regions such that the starting region
contains all the zeroes, the next season contains all the ones and the final region contains
all the zeroes. Start from the beginning of the array and check if the element is zero or two,
if it is then interchange it with the first one, if it is a one continue iterating.
Program/Source Code
Here is the source code of the Java Program to Solve the Dutch National Flag Problem.
The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Solve the Dutch National Flag Problem
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class DutchNationalFlag {
8. // Function to solve the Dutch National Flag problem
9. static void dutchNationalFlag(int[] array){
10. int low,high,middle,temp;
11. low = middle = 0;
12. high = array.length-1;
13. while(middle<=high){
14. if(array[middle] == 0)
15. {
16. temp = array[low];
17. array[low] = array[middle];
18. array[mid] = temp;
19. low = low + 1;
20. middle = middle + 1;
21. }
22. else if(array[middle] == 1)
23. middle++;
24. else
25. {
26. temp = array[high];
27. array[high] = array[middle];
28. array[middle] = temp;
29. high = high - 1;
30. }
31. }
32. }
33.  
34. // Function to read input and display the output
35. public static void main(String[] args) {
36. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
 37. int size;
38. System.out.println("Enter the size of the array");
39. try {
40. size = Integer.parseInt(br.readLine());
41. } catch (Exception e) {
42. System.out.println("Invalid Input");
43. return;
44. }
45. int[] array = new int[size];
46. System.out.println("Enter array elements");
47. int i;
48. for (i = 0; i < array.length; i++) {
49. try {
50. array[i] = Integer.parseInt(br.readLine());
51. } catch (Exception e) {
52. System.out.println("An error occurred");
53. return;
54. }
55. }
56. System.out.println("The initial array is");
57. for(i = 0;i < array.length; i++){
58. System.out.print(array[i] + " ");
59. }
60. dutchNationalFlag(array);
61. System.out.println("\nThe final array is");
62. for(i = 0;i < array.length; i++){
63. System.out.print(array[i] + " ");
64. }
65. }
66. }

Program Explanation
1. In the function dutchNationalFlag(), we take three variables low, mid and high.
2. low and mid are initialized to zero, whereas high is initialized to array.length – 1.
3. Now using the loop while (mid <= high), we check the array elements at index mid, using
a switch statement.
4. If the element is zero according to case 0, then we interchange the elements at index low
and mid, and increment both low and mid.
5. If the element is one according to case 1, we increment mid.
6. Finally, if the element is two according to case 2, we swap the element at mid and high,
along with decrementing high.
 advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple test Case):
 
Enter the size of the array
6
Enter array elements
1
0
2
2
0
1
The initial array is
1 0 2 2 0 1
The final array is
0 0 1 1 2 2
 
Case 2 (Simple test Case - another example):
 
Enter the size of the array
8
Enter array elements
2
2
0
0
0
1
1
1
The initial array is
2 2 0 0 0 1 1 1
The final array is
0 0 0 1 1 1 2 2

Java Program to Find the Length of the Longest Repeating

Sub-sequence in a String
This is the Java Program to Find the Length of the Longest Repeating Sub-sequence in a
String.

Problem Description
Given a string s, find and print the length of the longest repeating subsequence in the string,
that is, the length of the subsequence consisting of some of the characters in the original
string, which are present in two different locations in the string and in the same order.

Example:
String str =”HELLO”;

Output = 1

Problem Solution
In this question, take care that the character in the same position, should not be counted
in longest repeated subsequence. Create a matrix of size (n+1) * (n+1) and initialize its first
row and column as zero. Now, using nested loops to check if the characters at different
indexes match if they do increment the current value as follows L[i][j] = L[i-1][j-1] + 1,
otherwise maximum of L[i-1][j] and L[i][j-1]. Return L[n][n].

Program/Source Code
Here is the source code of the Java Program to Find the Length of the Longest Repeating
Sub-sequence in a String. The program is successfully compiled and tested using IDE
IntelliJ Idea in Windows 7. The program output is also shown below.
1.  
2. //Java Program to Find the Length of the Longest Repeating Sub-sequence in a
String
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class LongestRepeatingSubsequence {
8. // Function to find the length of longest repeating subsequence
9. static int lengthOfLRS(String str){
10. int[][] M = new int[str.length()+1][strlength()+1];
11. for(int i=1;i<=str.length();i++){
12. for(int j=1;j<=str.length();j++){
13. if(str.charAt(i-1) == str.charAt(j-1) && i!=j){
14. M[i][j] = M[i-1][j-1] + 1;
15. }
16. else
17. {
18. M[i][j] = Math.max(M[i-1][j],M[i][j-1]);
19. }
 20. }
21. }
22. return M[str.length()][str.length()];
23. }
24. // Function to read user input and display the output
25. public static void main(String[] args) {
26. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
27. String str;
28. System.out.println("Enter a string");
29. try{
30. str = br.readLine();
31. }catch (Exception e){
32. System.out.println("An error occurred");
33. return;
34. }
35. int x=lengthOfLRS(str);
36. System.out.println("The length of the longest repeating subsequence
is "
37.
+ x);
38. }
39. }

Program Explanation
1. In function lengthOfLRS(), a new matrix of size (n+1)*(n+1) is created, where n is the
length of the string.
2. The set of nested loops for(i=1; i<n; i++) { for(j=1; j<n; j++) are used to match the
characters at different positions.
3. The condition if(str.charAt(i-1) == str.charAt(j-1) && i!=j), checks whether the characters
at different positions are equal.
4. If they are, then the length of longest repeated subsequence upto current indices i and j
is updated as M[i][j] = M[i-1][j-1] + 1.
5. Otherwise, the length is updated as M[i][j] = Math.max(M[i-1][j],M[i][j-1]).
6. The value M[n][n] is finally returned as the length of the longest repeated subsequence.

Time Complexity: O(n ) where n is the length of the string.

2

advertisement

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter a string
AABEBCDD
The length of the longest repeating subsequence is 3
 
Case 2 (Simple Test Case - another example):
 
Enter a string
Hello
The length of the longest repeating subsequence is 1

Java Program to Find the Sum of the Series 1/1+1/2+1/3+…1/N

This is the Java Program to Find the Sum of the Series 1/1+1/2+1/3+…1/N.

Problem Description
Given a number n, write a java program to find the sum of the series 1/1+1/2+1/3+…1/N.

Problem Solution

Start a loop from 1 to n, and add the reciprocal of the loop variable to the sum.

Program/Source Code
Here is the source code of the Java Program to Find the Sum of the Series 1/1+1/2+1/3+…
1/N. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7.
The program output is also shown below.
1.  
2. //Java Program to Find the Sum of the Series 1/1+1/2+1/3+...1/N
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class Series80 {
8. // Function to find the sum of the series
9. public static void main(String[] args) {
10. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
11. int n;
12. try{
13. System.out.println("Enter the number of terms in the series");
 14. n = Integer.parseInt(br.readLine());
15. }catch (Exception e){
16. System.out.println("An error occurred");
17. return;
18. }
19. double sum = 0;
20. double i;
21. for(i=1; i<=n;i++){
22. sum +=(1/i);
23. }
24. System.out.println("The sum is " + sum);
25. }
26. }

Program Explanation
In the function main(), firstly the variable n is entered, then the loop for(i=1; i<=n;i++), is
used to sum the reciprocal of the loop variable.

Time Complexity: O(n).

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the number of terms in the series
34
The sum is 4.118209990445433

Java Program to Find the Sum of the Series 1/1+1/4+1/9+…

1/N^2
This is the Java Program to Find the Sum of the Series 1/1+1/4+1/9+…1/N . 2

Problem Description
Given a number n, write a java program to find the sum of the series 1/1+1/4+1/9+…1/N . 2

Problem Solution

Start a loop from 1 to n, and add the square of the reciprocal of the loop variable to
the sum.

Program/Source Code
Here is the source code of the Java Program to Find the Sum of the Series 1/1+1/4+1/9+…
1/N . The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7.
2

The program output is also shown below.

1.  
2. //Java Program to Find the Sum of the Series 1/1+1/4+1/9+...1/N^2
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class Series81 {
8. // Function to find the sum of the series
9. public static void main(String[] args) {
10. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
11. int n;
12. try{
13. System.out.println("Enter the number of terms in the series");
14. n = Integer.parseInt(br.readLine());
15. }catch (Exception e){
16. System.out.println("An error occurred");
17. return;
18. }
19. double sum = 0;
20. double i;
21. for(i=1; i<=n;i++){
22. sum +=(1/(Math.pow(i,2)));
23. }
24. System.out.println("The sum is " + sum);
25. }
26. }

Program Explanation
In the function main(), firstly the variable n is entered, then the loop for(i=1; i<=n;i++), is
used to sum the squares of the reciprocal of the loop variable.

Time Complexity: O(n).

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the number of terms in the series
34
The sum is 1.6159505883765848

Java Program to Find the Sum of the Series 1/1!+1/2!+1/3!+…

1/N!
This is the Java Program to Find the Sum of the Series 1/1!+1/2!+1/3!+…1/N!.

Problem Description
Given a number n, write a Java Program to Find the Sum of the Series 1/1!+1/2!+1/3!+…
1/N!.

Problem Solution

Start a loop from 1 to n, and add the factorial of the reciprocal of the loop variable to
the sum.
The factorial of the loop variable can be calculated using a nested loop.

Program/Source Code
Here is the source code of the Java Program to Find the Sum of the series 1/1!+1/2!+1/3!+
…1/N!. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows
7. The program output is also shown below.
1.  
2. //Java Program to Find the Sum of the series 1/1!+1/2!+1/3!+...1/N!
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class Series82 {
8. // Function to calculate and display the sum of the series.
9. public static void main(String[] args) {
10. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
11. int n;
12. try{
13. System.out.println("Enter the number of terms in the series");
14. n = Integer.parseInt(br.readLine());
15. }catch (Exception e){
16. System.out.println("An error occurred");
 17. return;
18. }
19. double sum = 0;
20. double i;
21. int j;
22. long fac;
23. for(i=1; i<=n;i++){
24. fac =1;
25. for(j=2; j<=i;j++){
26. fac*=j;
27. }
28. sum +=(1.0d/fac);
29. }
30. System.out.println("The sum is " + sum);
31. }
32. }

Program Explanation
In the function main(), firstly the variable n is entered, then the loop for(i=1; i<=n;i++), is
used to sum the reciprocal of the factorial of the loop variable. The loop for(j=2; j<=i;j++) is
used to calculate the factorial of i.

Time Complexity: O(n ). 2

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the number of terms in the series
34
The sum is 1.7182818284590455

Java Program to Reverse a Given Number Without Using

Recursion
This is the Java Program to Reverse a Given Number Without Using Recursion.

Problem Description
Write a Java Program to Reverse a Given Number Without Using Recursion.

Problem Solution
Using a loop, extract the last digit of the number and add it at the end of the reverse
formed till now.
.

Program/Source Code
Here is the source code of the Java Program to Reverse a Given Number Without Using
Recursion. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Reverse a Given Number Without Using Recursion
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class ReverseNumber {
8. // Function to reverse the number without using recursion
9. public static void main(String[] args) {
10. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
11. int n;
12. try {
13. System.out.println("Enter a number");
14. n = Integer.parseInt(br.readLine());
15. } catch (Exception e) {
16. System.out.println("An error occurred");
17. return;
18. }
19. int rev,i,s;
20. rev = 0;
21. for(i=n; i!=0; i/=10){
22. rev= rev*10+(i%10);
23. }
24. System.out.println("The reverse is " + rev);
25. }
26. }

Program Explanation
1. In function main(), firstly the number is taken as input.
2. Then, the loop for(i=n; i!=0; i/=10), runs until the each digit is extracted, in the reverse
order.
3. The statement rev= rev*10+(i%10); adds the digit obtained to the reverse.

Time Complexity: O(1).

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter a number
214224
The reverse is 422412

Java Program to Print 1,2,3,4…in Triangular Pattern

This is the Java Program to Print 1,2,3,4…in Triangular Pattern.

Problem Description
Write a Java Program to print the values 1,2,3,4.. in a triangular pattern, upto n lines.

Problem Solution

The idea is to use nested loops.

Iterate the first loop from 1 to n. Print the required number of spaces using a nested loop
and finally display the values using a nested loop.

Program/Source Code
Here is the source code of the Java Program to Print 1,2,3,4…in Triangular Pattern. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Print 1,2,3,4...in Triangular Pattern
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class Pattern1 {
8. // Function to display the pattern
9. public static void main(String[] args) {
10. int i,j,k,n;
 11. System.out.println("Enter the number of lines");
12. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
13. try{
14. n = Integer.parseInt(br.readLine());
15. }catch (Exception e){
16. System.out.println("An error occurred");
17. return;
18. }
19. System.out.println("The triangular pattern is");
20. int space = n-2;
21. for(i=1; i<=n; i++){
22. for(k=space;k>=0;k--){
23. System.out.print(" ");
24. }
25. space--;
26. for(j = 1; j<=i; j++){
27. System.out.print(j + " ");
28. }
29. System.out.println();
30. }
31. }
32. }

Program Explanation
1. In function main(), firstly the number of lines n is entered.
2. The outer loop for(i=1; i<=n; i++) is used to print n lines.
3. The nested loop for(k=space;k>=0;k–), is used to print the required spaces.
4. The nested loop for(j = 1; j<=i; j++), is used to print the values.

Time Complexity: O(n ). 2

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the number of lines
10
The triangular pattern is
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
 1 2 3 4 5 6
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10

Java Program to Print the Multiplication Table in Triangular

Form
This is the Java Program to Print the Multiplication Table in Triangular Form.

Problem Description
Write a Java Program to Print the Multiplication Table in Triangular Form. In this form, a
table is displayed row and column wise, in such a way such that in every row, only the
entries up to the same column number filled.

Problem Solution

The idea is to use nested loops.

First display the column numbers. Then, use to a nested loop to fill out the entries of the
row.

Program/Source Code
Here is the source code of the Java Program to Print the Multiplication Table in Triangular
Form. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows
7. The program output is also shown below.
1.  
2. //Java Program to Print the Multiplication Table in Triangular Form
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class TableInTriangularForm {
8. // Function to print tables in triangular form
9. public static void main(String[] args) {
10. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
11. int n;
12. System.out.println("Enter the value of n");
13. try{
 14. n = Integer.parseInt(br.readLine());
15. }catch(Exception e){
16. System.out.println("An error occurred");
17. return;
18. }
19. int i,j;
20. System.out.println("The table in triangular form is");
21. for(i=1; i<=n; i++){
22. System.out.printf("%2d ",i);
23. }
24. System.out.println();
25. for(i=1; i<=n; i++){
26. for(j=1; j<=i; j++){
27. System.out.printf("%2d ",i*j);
28. }
29. System.out.println();
30. }
31. }
32. }

Program Explanation
1. In function main(), firstly the number of lines n is entered.
2. The loop for(i=1; i<=n; i++) is used to print the column number lines.
3. The loop for(i=1; i<=n; i++), is used to print the n rows entries. 4. The nested loop for(j =
1; j<=i; j++), is used to print the current entry. 
Time Complexity: O(n ). 2

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the value of n
10
The table in triangular form is
1 2 3 4 5 6 7 8 9 10
1
2 4
3 6 9
4 8 12 16
5 10 15 20 25
6 12 18 24 30 36
7 14 21 28 35 42 49
8 16 24 32 40 48 56 64
9 18 27 36 45 54 63 72 81
10 20 30 40 50 60 70 80 90 100
Java Program to Implement the sin() Function (approximately)
This is the Java Program to Implement the sin() Function (approximately).

Problem Description
Given an angle say x, in degrees find out the sine of the angle approximately.

Problem Solution
The sine of an angle x can be calculated using the following equation

sin x = x – (x )/3! + (x )/5! – (x )/7! + ….. = Summation ((-1) * x

3 5 7 n (2n+1)
/(2n+1)!) for n = 0 to n =
infinity.

Note: In the series, x is in radians.

Program/Source Code
Here is the source code of the Java Program to Implement the cos()
Function(approximately). The program is successfully compiled and tested using IDE IntelliJ
Idea in Windows 7. The program output is also shown below.
1.  
2. // Java Program to Implement the cos() Function(approximately)
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class Sine {
8. // Function to calculate and display sine of an angle
9. public static void main(String[] args) {
10. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
11. double x;
12. try {
13. System.out.println("Enter the angle whose sine is to be
14. calculated in degrees");
15. x = Double.parseDouble(br.readLine());
16. } catch (Exception e) {
17. System.out.println("An error occurred");
18. return;
19. }
20. double y;
21. y = x*Math.PI/180;
 22. int n = 10;
23. int i,j,fac;
24. double sine = 0;
25. for(i=0; i<=n; i++){
26. fac = 1;
27. for(j=2; j<=2*i+1; j++){
28. fac*=j;
29. }
30. sine+=Math.pow(-1.0,i)*Math.pow(y,2*i+1)/fac;
31. }
32. System.out.format("The sine of " + x + " is %f",sine);
33. }
34. }

Program Explanation
1. In function main(), firstly the angle is entered in degrees and it is converted into radians.
2. The loop for(i=0; i<=n; i++) is used to calculate the ith term of the series.
3. The nested loop for(j=2; j<=2*i+1; j++) is used to calculate the factorial of 2i+1.
4. Finally, the ith term is added to the variable sine.

Time Complexity: O(1).

advertisement

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the angle whose sine is to be calculated in degrees
30
The sine of 30.0 is 0.500000
 
Case 2 (Simple Test Case - another example):
 
Enter the angle whose sine is to be calculated in degrees
60
The sine of 60.0 is 0.866025

Java Program to Implement the cos() Function(approximately)

This is the Java Program to Implement the cos() Function (approximately).

Problem Description
Given an angle say x, in degrees find out the cosine of the angle approximately.
Problem Solution
The cosine of an angle x can be calculated using the following equation

cos x = 1 – (x )/2! + (x )/4! – (x )/6! + ….. = Summation ((-1)  * x /(2n)!) for n = 0 to n =

2 4 6 n (2n)

infinity.

Note: In the series, x is in radians.

Program/Source Code
Here is the source code of the Java Program to Implement the cos()
Function(approximately). The program is successfully compiled and tested using IDE IntelliJ
Idea in Windows 7. The program output is also shown below.
1.  
2. // Java Program to Implement the cos() Function(approximately)
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class Cosine {
8. // Function to read user input and calculate the cosine of the angle
9. public static void main(String[] args) {
10. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
11. double x;
12. try {
13. System.out.println("Enter the angle whose cosine is to be
14. calculated in degrees");
15. x = Double.parseDouble(br.readLine());
16. } catch (Exception e) {
17. System.out.println("An error occurred");
18. return;
19. }
20. double y;
21. y = x*Math.PI/180;
22. int n = 10;
23. int i,j,fac;
24. double cosine = 0;
25. for(i=0; i<=n; i++){
26. fac = 1;
27. for(j=2; j<=2*i; j++){
28. fac*=j;
 29. }
30. cosine+=Math.pow(-1.0,i)*Math.pow(y,2*i)/fac;
31. }
32. System.out.format("The cosine of " + x + " is %f",cosine);
33. }
34. }

Program Explanation
1. In function main(), firstly the angle is entered in degrees and it is converted into radians.
2. The loop for(i=0; i<=n; i++) is used to calculate the ith term of the series.
3. The nested loop for(j=2; j<=2*i; j++) is used to calculate the factorial of 2i.
4. Finally, the ith term is added to the variable cosine.

Time Complexity: O(1).

advertisement

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the angle whose cosine is to be calculated in degrees
45
The cosine of 45.0 is 0.707107
 
Case 2 (Simple Test Case - another example):
 
Enter the angle whose cosine is to be calculated in degrees
75
The cosine of 75.0 is 0.258819

Java Program to Print the First n square Numbers

This is the Java Program to Print the First n square Numbers.

Problem Description
Given an integer says n, write a java program to print the first n squared numbers.

Problem Solution

Iterate through the loop from 1 to n and print the square of the loop variable.

Program/Source Code
Here is the source code of the Java Program to Print the First n square Numbers. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Print the First n square Numbers
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class PrintNSquareNumbers {
8. // Function to read n and display the numbers
9. public static void main(String[] args) {
10. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
11. int n;
12. System.out.println("Enter the value of n");
13. try{
14. n = Integer.parseInt(br.readLine());
15. }catch (Exception e){
16. System.out.println("An error occurred");
17. return;
18. }
19. if(n<=0){
20. System.out.println("n should be greater than zero");
21. return;
22. }
23. System.out.println("First " + n + " square numbers are ");
24. int i;
25. for(i=1; i<=n; i++){
26. System.out.print(i*i + " ");
27. }
28. }
29. }

Program Explanation
In the function main(), first, an integer say n is entered and then using the loop for(i=1; i<=n;
i++) the first n squared numbers are displayed.

Time Complexity: O(n).

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the value of n
15
First 15 square numbers are
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225

Java Program to Find the Sum of n Square Numbers

This is the Java Program to Find the Sum of n Square Numbers.

Problem Description
Given an integer says n, find out the sum of the first n squared numbers.

Problem Solution
The sum of the first n squared numbers can be calculated using the formula :

sum = n*(n+1)*(2n+1)/6

Program/Source Code
Here is the source code of the Java Program to Find the Sum of n Square Numbers. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Find the Sum of n Square Numbers
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class SumOfNSquareNumbers {
8. // Function to read n and display the sum
9. public static void main(String[] args) {
10. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
11. int n;
12. System.out.println("Enter the value of n");
13. try{
14. n = Integer.parseInt(br.readLine());
15. }catch (Exception e){
16. System.out.println("An error occurred");
 17. return;
18. }
19. if(n<0){
20. System.out.println("n cannot take negative values");
21. return;
22. }
23. double sum = n*(n+1)*(2*n+1)/6;
24. System.out.println("The sum of first " + n + " squared numbers is "
+ sum);
25. }
26. }

Program Explanation
In the function main(), firstly an integer n is entered and then the sum is calculated as per
the line,
double sum = n*(n+1)*(2*n+1)/6. Finally, the sum is displayed.

Time Complexity: O(1).

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the value of n
15
The sum of first 15 squared numbers is 1240.0

Java Program to Find the Sum of n Cube Numbers

This is the Java Program to Find the Sum of n Cube Numbers.

Problem Description
Given an integer says n, find out the sum of the first n cubed numbers.

Problem Solution
The sum of the first n cubed numbers can be calculated using the formula :

sum = (n*(n+1)/2) 2

Program/Source Code
Here is the source code of the Java Program to Find the Sum of n Cube Numbers. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. //Java Program to Find the Sum of n Cube Numbers
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class SumOfNCubeNumbers {
8. // Function to read n and display the sum
9. public static void main(String[] args) {
10. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
11. int n;
12. System.out.println("Enter the value of n");
13. try{
14. n = Integer.parseInt(br.readLine());
15. }catch (Exception e){
16. System.out.println("An error occurred");
17. return;
18. }
19. if(n<0){
20. System.out.println("n cannot take negative values");
21. return;
22. }
23. double sum = Math.pow(n*(n+1)/2,2);
24. System.out.println("The sum of first " + n + " cube numbers is " +
sum);
25. }
26. }

Program Explanation
In the function main(), firstly an integer n is entered and then the sum is calculated as per
the line,
double sum = Math.pow(n*(n+1)/2,2). Finally, the sum is displayed.

Time Complexity: O(1).

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the value of n
15
The sum of first 15 cube numbers is 14400.0

Java Program to Implement Heap Sort Using a Priority Queue

This is the Java Program to Implement Heap Sort Using a Priority Queue.

Problem Description
Given an array of integers, sort the array using heap sort which uses a priority queue. A
priority queue is a min-heap in which every node is smaller than its elements.

Problem Solution
Add all the elements of the array to the priority queue. Now, remove the minimum
element of the array and store it in the array starting from index 0.

Program/Source Code
Here is the source code of the Java Program to Implement Heap Sort Using a Priority
Queue. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows
7. The program output is also shown below.
1.  
2. //Java Program to Implement Heap Sort Using a Priority Queue
3.  
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7. import java.util.Arrays;
8.  
9. class PriorityQueue{
10. int[] arr;
11. int size;
12. int count;
13. PriorityQueue(int size){
14. this.size = size;
15. arr = new int[size];
16. count = 0;
17. }
18. // Function to insert an element into the priority queue
19. void insert(int value){
20. if(count == size){
21. System.out.println("Cannot insert the key");
22. return;
23. }
24. arr[count++] = value;
25. heapifyUpwards(count);
26. }
27. // Function to heapify an element upwards
28. void heapifyUpwards(int x){
29. if(x<=0)
30. return;
31. int par = (x-1)/2;
32. int temp;
33. if(arr[x-1] < arr[par]){
34. temp = arr[par];
35. arr[par] = arr[x-1];
36. arr[x-1] = temp;
37. heapifyUpwards(par+1);
38. }
39. }
40. // Function to extract the minimum value from the priority queue
41. int extractMin(){
42. int rvalue = arr[0];
43. arr[0] = Integer.MAX_VALUE;
44. heapifyDownwards(0);
45. return rvalue;
46. }
47. // Function to heapify an element downwards
48. void heapifyDownwards(int index){
49. if(index >=arr.length)
50. return;
51. int temp;
52. int min = index;
53. int left,right;
54. left = 2*index;
55. right = left+1;
56. if(left<arr.length && arr[index] > arr[left]){
57. min =left;
58. }
59. if(right <arr.length && arr[min] > arr[right]){
60. min = right;
61. }
62. if(min!=index) {
63. temp = arr[min];
64. arr[min] = arr[index];
65. arr[index] = temp;
66. heapifyDownwards(min);
67. }
68. }
69. // Function to implement the heapsort using priority queue
70. static void heapSort(int[] array){
71. PriorityQueue object = new PriorityQueue(array.length);
72. int i;
73. for(i=0; i<array.length; i++){
74. object.insert(array[i]);
75. }
76. for(i=0; i<array.length; i++){
77. array[i] = object.extractMin();
78. }
79. }
80. }
81. public class PriorityQueueTest {
82. // Function to read user input
83. public static void main(String[] args) {
84. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
85. int n;
86. System.out.println("Enter the number of elements in the array");
87. try{
88. n = Integer.parseInt(br.readLine());
89. }catch (IOException e){
90. System.out.println("An error occurred");
91. return;
92. }
93. System.out.println("Enter array elements");
94. int[] array = new int[n];
95. int i;
96. for(i=0; i<array.length; i++){
97. try{
98. array[i] = Integer.parseInt(br.readLine());
99. }catch (IOException e){
100. System.out.println("An error occurred");
101. }
102. }
103. System.out.println("The initial array is");
104. System.out.println(Arrays.toString(array));
 105. PriorityQueue.heapSort(array);
106. System.out.println("The sorted array is");
107. System.out.println(Arrays.toString(array));
108. }
109. }

Program Explanation
1. In class PriorityQueue, insert() function is used to add an element to the priority queue
and heapifyUpwards() function is used to move a leaf node to its appropriate position.
2. The extractMin() function returns the minimum element from the priority queue.
3. The heapifyDownwards() function, moves an element at index i to its correct position in
the min-heap.
4. In heapsort function, first, all the elements are added to the priority queue, then the
elements are extracted one by one.

Time Complexity: O(n*log(n)) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the number of elements in the array
10
Enter array elements
10
9
8
7
6
5
4
3
2
1
The initial array is
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
The sorted array is
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 
Case 2 (Simple Test Case - another example):
 
Enter the number of elements in the array
7
Enter array elements
24
124
4
658
43
547
43
The initial array is
[24, 124, 4, 658, 43, 547, 43]
The sorted array is
[4, 24, 43, 43, 124, 547, 658]

Java Program to Implement the pow() Function

This is the Java Program to Implement the pow() Function.

Problem Description
Given a value say x, and an exponent n, write a program to calculate x raised to the power
n.

Problem Solution
The value x raised to the power n can be calculated, using a simple recursive algorithm. If
the exponent is 1 return the variable x. Otherwise, recursively call the function on half of the
exponent. If the exponent is even, multiply the result obtained from the recursive call by
itself and in case if the exponent is odd also multiply x after multiplying the result.

Program/Source Code
Here is the source code of the Java Program to Implement the pow() Function. The
program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The
program output is also shown below.
1.  
2. // Java Program to Implement the pow() Function
3.  
4. import java.io.BufferedReader;
5. import java.io.InputStreamReader;
6.  
7. public class Power {
8. // Function to calculate power of x raised to n
9. static double pow(double x, int n){
10. if(n<0){
11. return pow(1/x,-n);
12. }
13. if(n==1)
14. return x;
15. else if(n%2 == 0){
 16. double y = pow(x,n/2);
17. return y*y;
18. }
19. double y = pow(x,n/2);
20. return y*y*x;
21. }
22. // Function to read user input
23. public static void main(String[] args) {
24. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
25. double x;
26. int n;
27. try {
28. System.out.println("Enter the number");
29. x = Double.parseDouble(br.readLine());
30. System.out.println("Enter the exponent (in integer)");
31. n = Integer.parseInt(br.readLine());
32. } catch (Exception e) {
33. System.out.println("An error occurred");
34. return;
35. }
36. double result = pow(x,n);
37. System.out.printf(x + " raised to " + n + " is %f", result);
38. }
39. }

Program Explanation
1. In function pow(), firstly the exponent is checked. If it is negative, then the recursive call is
made on the reciprocal of x, with negative of the exponent.
2. If the exponent is 1, then simply x is returned.
3. If the exponent is even, then a recursive call with half of the exponent is made and finally
the result is squared.
4. If the exponent is odd, then a recursive call with half of the exponent is made and finally
the result is squared and multiplied with x.

Time Complexity: O(log(n)) where n is the exponent.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the number
3.5
Enter the exponent (in integer)
5
3.5 raised to 5 is 525.218750
 
Case 2 (Simple Test Case - another example):
 
Enter the number
2
Enter the exponent (in integer)
-2
2.0 raised to -2 is 0.250000

Java Program to Implement Heap Sort on an Array of n

Elements
This is the Java Program to Implement Heap Sort on an Array of n Elements.

Problem Description
Given an array of integers, sort the array using heap sort algorithm.

Problem Solution
The idea is to create a max heap of the array elements. Then, obtain the maximum
element from the heap, interchange it with the last element and finally heapify the remaining
(n-1) elements. Repeat this procedure until zero elements are left.

Program/Source Code
Here is the source code of the Java Program to Implement Heap Sort on an Array of n
Elements. The program is successfully compiled and tested using IDE IntelliJ Idea in
Windows 7. The program output is also shown below.
1.  
2. //Java Program to Implement Heap Sort on an Array of n Elements
3. import java.io.BufferedReader;
4. import java.io.InputStreamReader;
5. import java.util.Arrays;
6.  
7. public class HeapSort {
8. //Function to sort the array using heapsort
9. static void heapSort(int[] array){
10. buildHeap(array);
11. int i,temp = array.length-1;
12. for(i = array.length-1; i>=1; i--){
13. int x = array[0];
14. array[0] = array[temp];
15. array[temp] = x;
16. temp--;
17. heapifyDownwards(array,0,temp);
18. }
19. }
20. // Function to heapify the array
21. static void heapifyDownwards(int[] array,int i,int n){
22. if(i>n)
23. {
24. return;
25. }
26. int left,right,index = i;
27. left = 2*i;
28. right= 2*i+1;
29. boolean change = false;
30. if(left<=n && array[i]<array[left]){
31. index = left;
32. change = true;
33. }
34. if(right<=n && array[right]>array[index]){
35. index = right;
36. change = true;
37. }
38. if(!change)
39. {
40. return;
41. }
42. int temp = array[index];
43. array[index] = array[i];
44. array[i] = temp;
45. heapifyDownwards(array,index,n);
46. }
47. // Function to build a max-heap
48. static void buildHeap(int[] array){
49. int i = array.length/2-1;
50. for(;i>=0;i--){
51. heapifyDownwards(array,i,array.length-1);
52. }
53. }
54. // Function to read input and display the output
55. public static void main(String[] args) {
 56. BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
57. int size;
58. System.out.println("Enter the size of the array");
59. try {
60. size = Integer.parseInt(br.readLine());
61. } catch (Exception e) {
62. System.out.println("Invalid Input");
63. return;
64. }
65. int[] array = new int[size];
66. System.out.println("Enter array elements");
67. int i;
68. for (i = 0; i < array.length; i++) {
69. try {
70. array[i] = Integer.parseInt(br.readLine());
71. } catch (Exception e) {
72. System.out.println("An error Occurred");
73. }
74. }
75. System.out.println("The initial array is");
76. System.out.println(Arrays.toString(array));
77. heapSort(array);
78. System.out.println("The sorted array is");
79. System.out.println(Arrays.toString(array));
80. }
81. }

Program Explanation
1. The function buildHeap() is used to build a max-heap from the array elements. It starts
from the internal nodes of the heaps and heapifies them downwards.
2. In function heapifyDownwards(), the element at index i, is compared with its children. If
any child is greater than the parent, the nodes are swapped and the function is called
recursively on the children.
3. In function heapSort(), firstly the buildHeap function is called.
4. The loop for(i = array.length-1; i>=1; i–), iterates through the heap swaps the first element
with the last and heapifies the first element.

Time Complexity: O(n*log(n)) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the size of the array
5
Enter array elements
9
8
7
6
5
The initial array is
[9, 8, 7, 6, 5]
The sorted array is
[5, 6, 7, 8, 9]
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
8
Enter array elements
8
7
6
9
9
6
7
8
The initial array is
[8, 7, 6, 9, 9, 6, 7, 8]
The sorted array is
[6, 6, 7, 7, 8, 8, 9, 9]