*Ques 1: Given an array of integers, write an algorithm and a program to left rotate the
array by specific number of elements.
Name :- Tejassvi Bhhati
Section :- I2
Roll No.:-119
Course :- B.Tech (CSE)
*/
#include <stdio.h>
void rotate(int arr[],int n,int k)
{
int temp;
for(int i=0;i<k/2;i++)
{
temp=arr[i];
arr[i]=arr[k-i-1];
arr[k-i-1]=temp;
}
for(int i=k;i<(n+k)/2;i++){
temp=arr[i];
arr[i]=arr[n-i-1+k];
arr[n-i-1+k]=temp;
}
for(int i=0;i<n/2;i++)
{
temp=arr[i];
arr[i]=arr[n-i-1];
arr[n-i-1]=temp;
}
}
int main()
{
int n,k,test;
printf("Enter test-cases: ");
scanf("%d",&test);
while(test!=0){
printf("\nEnter size of array: ");
scanf("%d",&n);
int arr[n];
printf("enter %d elements\n",n);
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("Enter number of rotation: ");
scanf("%d",&k);
rotate(arr,n,k);
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
test--;
}
return 0;
}
OUTPUT:
PS C:\Users\acetr\OneDrive\Desktop\DSA> cd "c:\Users\acetr\OneDrive\Desktop\DSA\C\" ;
if ($?) { g++ 1.C -o 1 } ; if ($?) { .\1 }
Enter test-cases: 3
Enter size of array: 5
enter 5 elements
12345
Enter number rotation: 6
23451
Enter size of array: 5
enter 5 elements
2 4 -3 2 3
Enter number rotation: 3
2 3 2 4 -3
Enter size of array: 10
enter 10 elements
1632914236
Enter number rotation: 4
9142361632
/*Ques 2: Given an unsorted array of integers and two numbers a and b. Design an
algorithm and write a program to find minimum distance between a and b in this array.
Minimum distance between any two numbers a and b present in array is the minimum
difference between their indices.
Name :- Tejassvi Bhhati
Section :- I2
Roll No.:-119
Course :- B.Tech (CSE)
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int distance(int arr[],int n,int a,int b)
{
int pos_a=-1,pos_b=-1,diff,min=INT_MAX;
for(int i=0;i<n;i++)
{
if(arr[i]==a)
{
pos_a=i;
if(pos_b!=-1)
{
diff=abs(pos_a-pos_b);
if(min>diff)
{
min=diff;
}
}
}
if(arr[i]==b)
{
pos_b=i;
if(pos_a!=-1)
{
diff=abs(pos_a-pos_b);
if(min>diff)
{
min=diff;
}
}
}
}
return min;
}
int main()
{
int n,a,b,test;
printf("Enter test-cases: ");
scanf("%d",&test);
while(test!=0){
printf("\nEnter size of array: ");
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("a and b: ");
scanf("%d %d",&a,&b);
int min=distance(arr,n,a,b);
if(min>n)
{
printf("Not present...");
}
else{
printf("Minimum distance: %d",min);
}
test--;
}
return 0;
}
OUTPUT:
PS C:\Users\acetr\OneDrive\Desktop\DSA> cd "c:\Users\acetr\OneDrive\Desktop\DSA\c\" ;
if ($?) { gcc 2.c -o 2 } ; if ($?) { .\2 }
Enter test-cases: 3
Enter size of array: 5
2 4 -3 2 3
a and b: 4 2
Minimum distance: 1
Enter size of array: 10
1632914362
a and b: 3 2
Minimum distance: 1
Enter size of array: 15
-2 8 7 1 2 6 8 9 0 2 -6 12 9 7 1
a and b: 7 2
Minimum distance: 2
/* Ques 3 : Given an array of nonnegative integers, where all numbers occur even
number of times except one number which occurs odd number of times. Write an
algorithm and a program to find this number. (Time complexity = O(n))
Name :- Tejassvi Bhhati
Section :- I2
Roll No.:-119
Course :- B.Tech (CSE)
*/
#include <stdio.h>
int odd(int arr[],int n)
{
int num=0;
for(int i=0;i<n;i++)
{
num=num^arr[i];
}
return num;
}
int main()
{
int n,test;
printf("Enter test-cases: ");
scanf("%d",&test);
while(test!=0)
{
printf("\nEnter size of the array: ");
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
int var=odd(arr,n);
printf("%d",var);
test--;
}
return 0;
}
OUTPUT:
PS C:\Users\acetr\OneDrive\Desktop\DSA> cd "c:\Users\acetr\OneDrive\Desktop\DSA\c\" ;
if ($?) { gcc 3.c -o 3 } ; if ($?) { .\3 }
Enter test-cases: 3
Enter size of the array: 5
24323
4
Enter size of the array: 11
16324142366
6
Enter size of the array: 15
287126890262971
0
/* Ques 4: Given a matrix of size n X n, where every row and every column is sorted in
increasing order. Write an algorithm and a program to find whether the given key
element is present in the matrix or not. (Linear time complexity)
Name :- Tejassvi Bhhati
Section :- I2
Roll No.:-119
Course :- B.Tech (CSE)
*/
#include <stdio.h>
int find(int n,int mat[n][n],int search)
{
int i=0,j=n-1;
while(i<n && j>=0)
{
if(mat[i][j]==search)
{
return 1;
}
else if(mat[i][j]>search)
{
j--;
}
else
{
i++;
}
}
return 0;
}
int main(){
int n,search,test;
printf("Enter test-cases: ");
scanf("%d",&test);
while(test!=0){
printf("\nEnter size of the Matrix: ");
scanf("%d",&n);
int mat[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&mat[i][j]);
}
}
printf("Enter key element: ");
scanf("%d",&search);
int var=find(n,mat,search);
if(var==1)
{
printf("Present");
}
else
{
printf("Not Present");
}
test--;
}
return 0;
}
OUTPUT:
PS C:\Users\acetr\OneDrive\Desktop\DSA> cd "c:\Users\acetr\OneDrive\Desktop\DSA\c\" ;
if ($?) { gcc 4.c -o 4 } ; if ($?) { .\4 }
Enter test-cases: 3
Enter size of the Matrix: 3
123
456
789
Enter key element: 5
Present
Enter size of the Matrix: 4
10 20 30 40
15 25 34 41
27 29 35 45
32 33 38 49
Enter key element:
33
Present
Enter size of the Matrix: 3
147
258
369
Enter key element: 10
Not Present
/*Ques 5: Given a boolean matrix (contains only 0 and 1) of size m X n where each row
is sorted, write an algorithm and a program to find which row has maximum number
of 1's. (Linear time complexity)
Name :- Tejassvi Bhhati
Section :- I2
Roll No.:-119
Course :- B.Tech (CSE)
*/
#include <stdio.h>
int find(int m,int n,int mat[m][n])
{
int i=0,j=n-1,row=0;
while(i<m && j>=0)
{
if(mat[i][j]==1)
{
j--;
row=i+1;
}
else
{
i++;
}
}
return row;
}
int main()
{
int m,n,test;
printf("Enter test-cases: ");
scanf("%d",&test);
while(test!=0){
printf("\nEnter size of the matrix: ");
scanf("%d %d",&m,&n);
int mat[m][n];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&mat[i][j]);
}
}
int var=find(m,n,mat);
printf("%d",var);
test--;
}
return 0;
}
OUTPUT:
PS C:\Users\acetr\OneDrive\Desktop\DSA> cd "c:\Users\acetr\OneDrive\Desktop\DSA\c\" ;
if ($?) { gcc 5.c -o 5 } ; if ($?) { .\5 }
Enter number of test-cases: 3
Enter size of the matrix (m*n): 4 3
enter 12 boolean elemnets:
011
001
111
000
row: 3
Enter size of the matrix (m*n): 3 3
enter 9 boolean elemnets:
010
111
011
row: 2
Enter size of the matrix (m*n): 4 4
enter 16 boolean elemnets:
1110
0101
1000
1100
row: 1
/* Ques 6: Given a matrix of size n X n containing positive integers, write an algorithm
and a program to rotate the elements of matrix in clockwise direction.
Name :- Tejassvi Bhhati
Section :- I2
Roll No.:-119
Course :- B.Tech (CSE)
*/
#include <stdio.h>
void rotate(int n, int mat[n][n])
{
for(int k=0;k<n/2;k++)
{
int a=k,b=n-k-1;
int top_left=mat[a][a];
int top_right=mat[a][b];
int bottom_right=mat[b][b];
int bottom_left=mat[b][a];
for(int i=b;i>a;i--)
{
mat[a][i]=mat[a][i-1];
}
for(int i=b;i>a;i--)
{
mat[i][b]=mat[i-1][b];
}
for(int i=a;i<b;i++)
{
mat[b][i]=mat[b][i+1];
}
for(int i=a;i<b-1;i++)
{
mat[i][a]=mat[i+1][a];
}
mat[a][a+1]=top_left;
mat[a+1][b]=top_right;
mat[b][b-1]=bottom_right;
mat[b-1][a]=bottom_left;
}
}
int main()
{
int n,test;
printf("Enter test-cases: ");
scanf("%d",&test);
while(test!=0){
printf("\nEnter size of the matrix: ");
scanf("%d",&n);
int mat[n][n];
printf("enter %d elements:\n",n*n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&mat[i][j]);
}
}
rotate(n,mat);
printf("elements of matrix after rotation in clockwise direction:\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
printf("%d ",mat[i][j]);
}
printf("\n");
}
test--;
}
return 0;
}
OUTPUT:
PS C:\Users\acetr\OneDrive\Desktop\DSA> cd "c:\Users\acetr\OneDrive\Desktop\DSA\c\" ;
if ($?) { gcc 6.c -o 6 } ; if ($?) { .\6 }
Enter test-cases: 3
Enter size of the matrix: 4
enter 16 elements:
11 12 13 14
15 16 17 18
19 20 21 22
23 24 25 26
elements of matrix after rotation in clockwise direction
15 11 12 13
19 20 16 14
23 21 17 18
24 25 26 22
Enter size of the matrix: 3
enter 9 elements:
123
456
789
elements of matrix after rotation in clockwise direction:
412
753
896
Enter size of the matrix: 3
enter 9 elements:
147
258
369
elements of matrix after rotation in clockwise direction:
214
357
698
/*Ques 7: Design an algorithm and a program to implement stack using array. The
program should implement following stack operations:
a) Create() - create an empty stack
b) Push(k) - push an element k into the stack
c) Pop() - pop an element from the stack and return it
d) IsEmpty() - check if stack is empty or not
e) Size() - finds the size of the stack
f) Print() - prints the contents of stack
Name :- Tejassvi Bhhati
Section :- I2
Roll No.:-119
Course :- B.Tech (CSE)
*/
#include <stdio.h>
void push(int size,int stack[],int *top,int num)
{
if(*top==size-1)
{
printf("Stack is full\n");
return;
}
(*top)++;
stack[*top]=num;
}
int pop(int stack[],int *top)
{
if(*top==-1)
{
printf("Stack is empty\n");
return 0;
}
return stack[(*top)--];
}
int isEmpty(int *top)
{
if(*top==-1)
{
return 1;
}
else
{
return 0;
}
}
int topelement(int stack[],int top)
{
if(top==-1)
{
printf("Stack is empty\n");
return 0;
}
else
{
int value=stack[top];
return value;
}
}
void display(int stack[],int top)
{
if(top==-1)
{
printf("Stack is Empty\n");
}
else
{
for(int i=top;i>=0;i--)
{
printf("%d ",stack[i]);
}
}
}
int SIZE(int top)
{
return top+1;
}
int main()
{
int n,choice,size;
printf("Enter size of stack: ");
scanf("%d",&size);
int stack[size];
int top=-1;
while(1)
{
printf("\n1 for Push\n");
printf("2 for Pop\n");
printf("3 to Print top element\n");
printf("4 to Print all elements\n");
printf("5 for Size of stack\n");
printf("6 for IsEmpty?\n");
printf("7 to Quit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
if(choice==1)
{
printf("Enter element: ");
scanf("%d",&n);
push(size,stack,&top,n);
}
else if(choice==2)
{
printf("Poped: %d",pop(stack,&top));
}
else if(choice==3)
{
printf("Top element: %d",topelement(stack,top));
}
else if(choice==4)
{
display(stack,top);
}
else if(choice==5)
{
printf("Size: %d",SIZE(top));
}
else if(choice==6)
{
if(isEmpty(&top))
printf("Stack is Empty\n");
else
printf("Stack is Not Empty\n");
}
else if(choice==7)
{
printf("End\n");
break;
}
}
return 0;
}
OUTPUT:
PS C:\Users\acetr\OneDrive\Desktop\DSA> cd "c:\Users\acetr\OneDrive\Desktop\DSA\c\" ;
if ($?) { gcc 7.c -o 7 } ; if ($?) { .\7 }
Enter size of stack: 10
1 for Push
2 for Pop
3 to Print top element
4 to Print all elements
5 for Size of stack
6 for IsEmpty?
7 to Quit
Enter your choice: 1
Enter element: 34
1 for Push
2 for Pop
3 to Print top element
4 to Print all elements
5 for Size of stack
6 for IsEmpty?
7 to Quit
Enter your choice: 1
Enter element: 42
1 for Push
2 for Pop
3 to Print top element
4 to Print all elements
5 for Size of stack
6 for IsEmpty?
7 to Quit
Enter your choice: 1
Enter element: 6
1 for Push
2 for Pop
3 to Print top element
4 to Print all elements
5 for Size of stack
6 for IsEmpty?
7 to Quit
Enter your choice: 4
6 42 34
1 for Push
2 for Pop
3 to Print top element
4 to Print all elements
5 for Size of stack
6 for IsEmpty?
7 to Quit
Enter your choice: 2
Poped: 6
1 for Push
2 for Pop
3 to Print top element
4 to Print all elements
5 for Size of stack
6 for IsEmpty?
7 to Quit
Enter your choice: 4
42 34
1 for Push
2 for Pop
3 to Print top element
4 to Print all elements
5 for Size of stack
6 for IsEmpty?
7 to Quit
Enter your choice: 5
Size: 2
1 for Push
2 for Pop
3 to Print top element
4 to Print all elements
5 for Size of stack
6 for IsEmpty?
7 to Quit
Enter your choice: 6
Stack is Not Empty
1 for Push
2 for Pop
3 to Print top element
4 to Print all elements
5 for Size of stack
6 for IsEmpty?
7 to Quit
Enter your choice: 7
End
/* Ques 8: Given an expression string consisting of opening and closing brackets
“{“,”}”,”(“,”)”,”[“,”]”, design an algorithm and a program to check whether this
expression has balanced parenthesis or not.
Name :- Tejassvi Bhhati
Section :- I2
Roll No.:-119
Course :- B.Tech (CSE)
*/
#include <stdio.h>
#include <string.h>
int check(char str[],int size)
{
if(size%2!=0)
{
return 0;
}
int stack[size];
int top=-1;
for(int i=0;i<size;i++)
{
if(str[i]=='(' || str[i]=='[' || str[i]=='{')
{
push(stack,&top,str[i]);
}
else if(str[i]==')')
{
if(top==-1)
{
return 0;
}
else if(stack[top]=='(')
{
pop(&top);
}
else
{
return 0;
}
}
else if(str[i]==']')
{
if(top==-1)
{
return 0;
}
else if(stack[top]=='[')
{
pop(&top);
}
else
{
return 0;
}
}
else if(str[i]=='}')
{
if(top==-1)
{
return 0;
}
else if(stack[top]=='{')
{
pop(&top);
}
else
{
return 0;
}
}
}
if(top==-1)
{
return 1;
}
else
{
return 0;
}
}
void push(int stack[],int *top,int num)
{
stack[++(*top)]=num;
}
void pop(int *top)
{
(*top)--;
}
int main()
{
char str[1000];
int test;
printf("Enter test-cases: ");
scanf("%d",&test);
getchar();
while(test!=0){
printf("\nEnter bracktes: ");
fgets(str,sizeof(str),stdin);
int size=strlen(str)-1;
int flag=check(str,size);
if(flag==1)
{
printf("Balanced\n");
}
else
{
printf("Unbalanced\n");
}
test--;
}
return 0;
}
OUTPUT:
PS C:\Users\acetr\OneDrive\Desktop\DSA> cd "c:\Users\acetr\OneDrive\Desktop\DSA\c\" ;
if ($?) { gcc 8.c -o 8 } ; if ($?) { .\8 }
Enter test-cases: 3
Enter bracktes: {{(()())}}
Balanced
Enter bracktes: ([][])(){(())}
Balanced
Enter bracktes: {()(()}
Unbalanced
/* Ques 9: Given a string of opening and closing parenthesis, design an algorithm and
a program to find the length of the longest valid parenthesis substring. Valid
parenthesis substring is a string which contains balanced parenthesis
Name :- Tejassvi Bhhati
Section :- I2
Roll No.:-119
Course :- B.Tech (CSE)
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int longestvalid(char str[],int size)
{
int top=0,len=0,max=0;
int *stack=(int *)malloc((size+1)*sizeof(int));
stack[top]=-1;
for(int i=0;i<size;i++)
{
if(str[i]=='(')
{
stack[++top]=i;
}
else
{
top--;
if(top==-1)
{
stack[++top]=i;
}
else
{
len=i-stack[top];
if(len>max)
max=len;
}
}
}
return max;
}
int main()
{
char str[1000];
int test;
printf("Enter test-cases: ");
scanf("%d",&test);
getchar();
while(test!=0)
{
printf("\nEnter bracktes: ");
fgets(str,sizeof(str),stdin);
int size=strlen(str)-1;
int result=longestvalid(str,size);
printf("%d",result);
test--;
}
return 0;
}
OUTPUT:
PS C:\Users\acetr\OneDrive\Desktop\DSA> cd "c:\Users\acetr\OneDrive\Desktop\DSA\c\" ;
if ($?) { gcc 9.c -o 9 } ; if ($?) { .\9 }
Enter test-cases: 3
Enter bracktes: ()())))
4
Enter bracktes: ((()())(
6
Enter bracktes: (()()(()))()
12
