PRACTICE SET

DATA STRUCTURE
SOLVED BY:
PROF. BRIJENDRA SIR (BRAJ KUMAR)
(जावा का बाप)
“क्यूं पड़े हो चक्कर में, कोई नह ूं है टक्कर में”

Join Official group for more:

https://chat.whatsapp.com/CjhLnhqPByLIIQIDi12GeL

YouTube Channel:
https://youtube.com/@roomno547
 PRACTICE SET DSA
Question 1: Arrange all the given time complexities in ascending order. O(n), O(n^2), O(n!), O(log n), O(3^n), O(n log
n), O(10), O(n^4)
Solution: Here are the given time complexities arranged in ascending order:
1. O(10)
2. O(log n)
3. O(n)
4. O(n log n)
5. O(n^2)
6. O(n^4)
7. O(3^n)
8. O(n!)

Question 2: Consider the linear arrays A[ 3:24], B[-3:12]. Find the number of elements in each array.

Solution:

No. of element in 1D array = (Upper limit – Lower Limit) +1

Number of elements in A = 24 - 3 + 1 = 22
Number of elements in B = 12 - (-3) + 1 = 16

Question 3: Suppose an array, B[-5 ..... +4 ] having Base address (BA) = 100 and size of an element = 4 bytes, find the
location of B[-2].

Solution:
Location=Base Address+(Index−Lower Bound)×Size of an Element
Location of B[−2]=100+((−2)−(−5))×4
Location of B[−2]=112
So, the location of B[−2] is 112.

Question 4: Apply the binary search on the given numbers to find location of 25 (Show all steps). Given Array:
2,4,7,12,14,17,23,25,35,41,47

Solution:
Given array: 2, 4, 7, 12, 14, 17, 23, 25, 35, 41, 47

Step 1: Initial Setup

Array: 2, 4, 7, 12, 14, 17, 23, 25, 35, 41, 47
Target: 25
Low: 0
High: 10

Step 2: First Comparison

Mid = (Low + High) / 2 = (0 + 10) / 2 = 5
Array[5] = 17 (less than 25)
Since the target (25) is greater than the element at the midpoint, update Low to Mid + 1.
Low = 6
High = 10
Step 3: Second Comparison
Mid = (Low + High) / 2 = (6 + 10) / 2 = 8
Array[8] = 35 (greater than 25)
Since the target (25) is less than the element at the midpoint, update High to Mid - 1.
Low = 6
High = 7

Step 4: Third Comparison

Mid = (Low + High) / 2 = (6 + 7) / 2 = 6
Array[6] = 23 (less than 25)
Since the target (25) is greater than the element at the midpoint, update Low to Mid + 1.
Low = 7
High = 7

Step 5: Fourth Comparison

Mid = (Low + High) / 2 = (7 + 7) / 2 = 7
Array[7] = 25 (equal to the target)
The target (25) is found at index 7.

Result:
The target value 25 is found at index 7.

BINARY SEARCH PROGRAM(Additional):

import java.util.Scanner;

public class BinarySearch {

public static boolean binarySearch(int[]arr, int target){
int n = arr.length;
int st = 0, end = n-1;
while (st<=end){
int mid = (st+end)/2;
if (target == arr[mid]){
return true;
}
else if (target<arr[mid]){
end = mid-1;
}
else {
st = mid+1;
}
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
int n = sc.nextInt();
int []arr = new int[n];
System.out.print("Enter "+n+" elements: ");
for (int i = 0; i<arr.length; i++){
arr[i] = sc.nextInt();
}
System.out.print("Enter the target: ");
int target = sc.nextInt();

System.out.println(binarySearch(arr,target));
}
}
NOTE:
int mid = (st+end)/2; // --> this formula sometimes result to overflow & give error
int mid = st + (end-st)/2; // better way to find mid

Question 5: Sort the given numbers using bubble sort(show all steps). Given Array: 15,32,27,31,8,11

Solution:
Given array: 15, 32, 27, 31, 8, 11

Here are the steps of the bubble sort algorithm:

Pass 1:
Compare 15 and 32. No swap needed. Array: 15, 32, 27, 31, 8, 11
Compare 32 and 27. Swap needed. Array: 15, 27, 32, 31, 8, 11
Compare 32 and 31. Swap needed. Array: 15, 27, 31, 32, 8, 11
Compare 32 and 8. Swap needed. Array: 15, 27, 31, 8, 32, 11
Compare 32 and 11. Swap needed. Array: 15, 27, 31, 8, 11, 32

Pass 2:
Compare 15 and 27. No swap needed. Array: 15, 27, 31, 8, 11, 32
Compare 27 and 31. No swap needed. Array: 15, 27, 31, 8, 11, 32
Compare 31 and 8. Swap needed. Array: 15, 27, 8, 31, 11, 32
Compare 31 and 11. Swap needed. Array: 15, 27, 8, 11, 31, 32

Pass 3:
Compare 15 and 27. No swap needed. Array: 15, 27, 8, 11, 31, 32
Compare 27 and 8. Swap needed. Array: 15, 8, 27, 11, 31, 32
Compare 27 and 11. Swap needed. Array: 15, 8, 11, 27, 31, 32

Pass 4:
Compare 15 and 8. Swap needed. Array: 8, 15, 11, 27, 31, 32
Compare 15 and 11. Swap needed. Array: 8, 11, 15, 27, 31, 32

Pass 5:
Compare 8 and 11. No swap needed. Array: 8, 11, 15, 27, 31, 32

Now, the array is sorted: 8, 11, 15, 27, 31, 32. The bubble sort algorithm has completed sorting the given numbers.
BUBBLE SORT PROGRAM(Additional):
import java.util.Scanner;

public class BubbleSort {

public static void BubbleSort(int[]arr){
int n = arr.length;
for (int i =0; i<n-1;i++){
boolean flag = false;
for (int j =0; j<n-i-1;j++){
if (arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;
}
}
if (!flag){
return;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
int n = sc.nextInt();
int [] arr = new int[n];
System.out.print("Enter "+n+" elements: ");
for (int i = 0; i<arr.length; i++){
arr[i] = sc.nextInt();
}

BubbleSort(arr);
System.out.println("Sorted Array: ");
for (int i =0; i<arr.length;i++){
System.out.print(arr[i]+"\t");
}
}
}
Question 6: Show all the steps of Tower of Hanoi to move 4 disks from source peg to destination peg.

Solution:

Step 1: Initial Setup Peg B: 3 Peg C: 4 1

Peg A: 4 3 2 1 Peg C: 2
Peg B: Step 12: Move Disk 1 from C to A
Peg C: Step 7: Move Disk 2 from C to B Peg A: 2 1
Peg A: 4 1 Peg B: 3
Step 2: Move Disk 1 from A to B Peg B: 3 2 Peg C: 4
Peg A: 4 3 2 Peg C:
Peg B: 1 Step 13: Move Disk 3 from B to C
Peg C: Peg A: 2 1
Step 8: Move Disk 1 from A to B Peg B:
Step 3: Move Disk 2 from A to C Peg A: 4 Peg C: 4 3
Peg A: 4 3 Peg B: 3 2 1
Peg B: 1 Peg C: Step 14: Move Disk 1 from A to B
Peg C: 2 Peg A: 2
Step 9: Move Disk 4 from A to C Peg B: 1
Step 4: Move Disk 1 from B to C Peg A: Peg C: 4 3
Peg A: 4 3 Peg B: 3 2 1
Peg B: Peg C: 4 Step 15: Move Disk 2 from A to C
Peg C: 2 1 Peg A:
Step 10: Move Disk 1 from B to C Peg B: 1
Step 5: Move Disk 3 from A to B Peg A: Peg C: 4 3 2
Peg A: 4 Peg B: 3 2
Peg B: 3 Peg C: 4 1 Step 16: Move Disk 1 from B to C
Peg C: 2 1 Peg A:
Step 11: Move Disk 2 from B to A Peg B:
Step 6: Move Disk 1 from C to A Peg A: 2 Peg C: 4 3 2 1
Peg A: 4 1 Peg B: 3

Now, all 4 disks have been successfully moved from peg A to peg C using peg B as a helper.

TOWER OF HANOI PROGRAM(Additional):

public class HanoiTower {

public static void towerOfHanoi(int n, char src, char aux, char dest){
if (n==1){
System.out.println(src+" -> "+dest);
return;
}
towerOfHanoi(n-1,src,dest,aux);
towerOfHanoi(1,src,aux,dest);
towerOfHanoi(n-1,aux,src,dest);
}
public static void main(String[] args) {
towerOfHanoi(4,'A','B','C');
}
}
Question 7: Write a java program for inserting an element in given location in array.

Solution:
package PracticeSet;

import java.util.Scanner;

public class Solution7 {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int []arr = new int[50];
System.out.print("Enter the size of the array: ");
int size = sc.nextInt();
System.out.print("Enter "+size+" elements: ");
for (int i =0; i<size;i++){
arr[i] = sc.nextInt();
}
System.out.println("Array before insertion: ");
for (int i =0; i<size;i++){
System.out.print(arr[i]+"\t");
}
System.out.println();

System.out.print("Enter the element to be inserted: ");

int num = sc.nextInt();
System.out.print("Enter the position: ");
int pos = sc.nextInt();

for (int i = size; i>pos;i--){

arr[i] = arr[i-1];
}
arr[pos] = num;
++size;
System.out.println("Array after insertion: ");
for (int i =0; i<size;i++){
System.out.print(arr[i]+"\t");
}
}
}

Output:
Question 8: Write a java program to find sum of digits of an integer using tail recursion.

Solution:
import java.util.Scanner;
public class Solution8 {
public static int sumOfDigit(int n ){
if (n>=0 && n<=9){
return n;
}
return sumOfDigit(n/10) + n%10;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number: ");
int n = sc.nextInt();
System.out.print("Sum of digits of "+n+" is: ");
System.out.println(sumOfDigit(n));
}
}

Output:

Question 9: Write a Java program to replace a specific element with an other element in array each time.

Solution:
package PracticeSet;

import java.util.Arrays;
import java.util.Scanner;

public class Solution9 {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int []arr = {1,2,3,2,4,5,6,4,2};
System.out.print("Enter old number: ");
int oldNumber = sc.nextInt();
System.out.print("Enter new number: ");
int newNumber = sc.nextInt();
System.out.print("Original Array: "+ Arrays.toString(arr));
for (int i=0;i<arr.length;i++){
if (arr[i]==oldNumber){
arr[i]=newNumber;
}
}
System.out.print("\nModified Array: "+Arrays.toString(arr));
}
}
Output:
Question 10: Consider the multi-dimensional array A (2:18, 10:15, -5:5). Suppose Base (A)=200 with word size = 2.
Find the effective indices E1, E2 & E3 and address of A[5, 12,3] using column-major order.

Solution:

Question 11: Write a Java program to print elements which are appeared single time in array of integers.

Solution:
package PracticeSet;
import java.util.Arrays;
public class Solution11 {
public static void main(String[] args) {
int []arr = {1,2,2,3,4,5,5};
System.out.println("Array: "+ Arrays.toString(arr));
for(int i =0;i<arr.length;i++){
int count =0;
int key = arr[i];
for (int j=0;j<arr.length;j++){
if (i!=j && key==arr[j]){
count++;
break;
}
}
if (count==0){
System.out.println(arr[i]);
}
}
}
}
Question 12: Write a program in Java to find the smallest element in array using recursion.
Solution:

package PracticeSet;
public class Solution12 {
static int getMin(int arr[], int n) {
if (n == 1)
return arr[0];

return Math.min(arr[n - 1], getMin(arr, n - 1));

}

public static void main(String args[]) {

int arr[] = {12, 13, 1, 10, 34, 10};

int n = arr.length;
System.out.print(getMin(arr, n));
}
}

Question 13: Write a java program to reverse a string using recursion.

Solution:
package PracticeSet;

public class Solution13 {

public static String reverseString(String str) {
// Check if the string is empty or null
if (str.isEmpty()) {
return str;
} else {
return reverseString(str.substring(1)) + str.charAt(0);
}
}

public static void main(String[] args) {

String str = "Code copy karke aukat dikha di!";
System.out.println("Original String: " + str);
System.out.println("Reversed String: " + reverseString(str));
}
}
Question 14: Write a pseudocode or Java program to find all pairs of elements in an array whose product is equal to
a specified number.

Solution:
Pseudocode:
• Initialize an array array with the values [2, 4, 3, 6, 8, 5, 10].
• Set the target product to 20.
• Print the original array: array.
• Create two nested loops to iterate through the array:
o Outer loop: Iterate from index 0 to array.length - 1.
o Inner loop: Iterate from index 1 to array.length for each iteration of the outer loop.
• Inside the inner loop, check if the product of the current pair (array[i] and array[j]) is equal to the target
product (20). a. If the product is equal to the target product, print the pair: (" + array[i] + ", " + array[j] + ")".

package PracticeSet;

import java.util.Arrays;

public class Solution14 {

public static void main(String[] args) {
int[] array = {2, 4, 3, 6, 8, 5, 10};
int targetProduct = 20;

System.out.println("Original Array: " + Arrays.toString(array));

System.out.println("\nPairs with product equal to " + targetProduct + ": ");

for (int i = 0; i < array.length-1; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] * array[j] == targetProduct) {
System.out.println("(" + array[i] + ", " + array[j] + ")");
}
}
}
}
}
Question 15: Write a Java program to find non common elements in two sorted (in non-decreasing order) arrays.

Solution:
package PracticeSet;
public class Solution15 {
public static void main(String[] args) {
int[] array1 = {2, 4, 6, 8, 10};
int[] array2 = {4, 8, 12, 14, 16};

System.out.println("Array 1: ");
printArray(array1);

System.out.println("\nArray 2: ");
printArray(array2);

System.out.println("\nNon-common elements: ");

findNonCommonElements(array1, array2);
}

// Method to print an array

private static void printArray(int[] array) {
for (int num : array) {
System.out.print(num + " ");
}
System.out.println();
}

// Method to find non-common elements in two sorted arrays

private static void findNonCommonElements(int[] array1, int[] array2) {
int i = 0, j = 0;

while (i < array1.length && j < array2.length) {

if (array1[i] < array2[j]) {
System.out.print(array1[i] + " ");
i++;
} else if (array1[i] > array2[j]) {
System.out.print(array2[j] + " ");
j++;
} else {
// Move both pointers if elements are equal (common element)
i++;
j++;
}
}

// Print remaining elements from both arrays

while (i < array1.length) {
System.out.print(array1[i] + " ");
i++;
}

while (j < array2.length) {

System.out.print(array2[j] + " ");
j++;
}
}
}
Question 16: Write a program to move all the duplicate values of the given numbers at the start of the array.

Solution:
package PracticeSet;

import java.util.Arrays;
import java.util.Scanner;

public class Solution16 {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {2,3,5,3,4,5,3,6,3,9};
System.out.print("Enter the number: ");
int n = sc.nextInt();
int[] result = new int[arr.length];
int k = 0;

for (int i = 0; i < arr.length; i++) {

if (arr[i] == n) {
result[k++] = arr[i];
}
}

for (int i = 0; i < arr.length; i++) {

if (arr[i] != n) {
result[k++] = arr[i];
}
}

System.out.println(Arrays.toString(result));
}
}

Output:
Question 17: Solve a Tower of Hanoi problem for n disks and 4 towers.

Answer:
package PracticeSet;

public class Solution17 {

public static void toh4(int n, char src, char dest, char aux1, char aux2) {
if (n == 1) {
System.out.println(src + " -> " + dest);
return;
} else if (n == 2) {
System.out.println(src + " -> " + aux1);
System.out.println(src + " -> " + dest);
System.out.println(aux1 + " -> " + dest);
return;
} else {
toh4(n - 2, src, aux2, dest, aux1);
System.out.println(src + " -> " + aux1);
System.out.println(src + " -> " + dest);
System.out.println(aux1 + " -> " + dest);
toh4(n - 2, aux2, dest, aux1, src);
}
}

public static void main(String[] args) {

toh4(3, 'S', 'D', 'A', 'B');
}
}

Output:
Question 18: Drive the formula for address calculation of 3-D array in row major order.

Answer:
Question 19: Write a program in Java to find sum of odd elements of even rows and even elements of odd rows.

Answer:
package PracticeSet;

public class Solution19 {

public static void main(String[] args) {
int [][]matrix = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16}
};
System.out.println("Given Matrix: ");
for (int[] row : matrix) {
for (int element : row) {
System.out.print(element + " ");
}
System.out.println();
}
int sum = 0;
for (int i =0; i<matrix.length;i++){
for (int j=0; j<matrix[0].length;j++){
if (i%2==0 && matrix[i][j]%2==1 || i%2==1 && matrix[i][j]%2==0){
sum+=matrix[i][j];
}
}
}
System.out.println("Sum: "+sum);
}
}

Output:
Question 20: Write a Java program to print first row from left to right then last column from top to bottom then last
row from right to left then first column from bottom to top in NxN matrix.

Answer:
package PracticeSet;

public class Solution20 {

public static void main(String[] args) {
int [][]matrix = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16}
};
System.out.println("Given Matrix: ");
for (int[] row : matrix) {
for (int element : row) {
System.out.print(element + " ");
}
System.out.println();
}
int n = matrix.length;
int m = matrix[0].length;
for (int i =0;i<n;i++){
for (int j =0; j<m;j++){
if (i==0 || i == n-1 || j==0 || j==m-1){
System.out.print(matrix[i][j]+"\t");
}
else {
System.out.print("\t");
}
}
System.out.println("\t");
}
}
}

Output: