manchester program
#include<stdio.h>
#include<stdlib.h>
int* manchester(int *arr,int len)
{
int* res=(int*)malloc(sizeof(int)*len);
arr[-1]=0;
for(int i=0;i<len;i++)
{
res[i]=arr[i]==arr[i-1]?0:1;
}
return res;
}
int main() {
int n,a[100],i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
int* x=manchester(a,n);
for(i=0;i<n;i++)
printf("%d ",x[i]);
}
#include<stdlib.h>
int* manchester(int *arr,int len)
{
int* res=(int*)malloc(sizeof(int)*len);
arr[-1]=0;
for(int i=0;i<len;i++)
{
res[i]=arr[i]==arr[i-1]?0:1;
}
return res;
}
int main() {
int n,a[100],i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
int* x=manchester(a,n);
for(i=0;i<n;i++)
printf("%d ",x[i]);
}
input:
8
0 1 0 0 1 1 1 0
output:
0 1 1 0 1 0 0 1
pattern alternating 0's and 1's
#include<stdio.h>
int main()
{
int i,j,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i%2!=0&&j%2!=0)
{
printf("1");
}
else if(i%2==0&&j%2==0)
{
printf("1");
}
else
{
printf("0");
}
}
printf("\n");
}
}
input:
5
output:
10101
01010
10101
01010
10101
int main()
{
int i,j,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i%2!=0&&j%2!=0)
{
printf("1");
}
else if(i%2==0&&j%2==0)
{
printf("1");
}
else
{
printf("0");
}
}
printf("\n");
}
}
input:
5
output:
10101
01010
10101
01010
10101
factorial of a number
#include<stdio.h>
long int multiply(int n);
int main()
{
int n;
scanf("%d",&n);
printf("factoraial of %d is %d",n,multiply(n));
return 0;
}
long int multiply(int n)
{
if(n>=1)
return n*multiply(n-1);
else
return 1;
}
input:
5
output:
factoraial of 5 is 120
long int multiply(int n);
int main()
{
int n;
scanf("%d",&n);
printf("factoraial of %d is %d",n,multiply(n));
return 0;
}
long int multiply(int n)
{
if(n>=1)
return n*multiply(n-1);
else
return 1;
}
input:
5
output:
factoraial of 5 is 120
CTS TRAINING PROGRAMS
reverse-of-sentence
exponent of a number
sum of squares of elements in the given array
removal of vowels in the string
find greatest factor of a given number
find LCM of n numbers
multiplication table
print palindrome in the range
print even or odd pattern
print prime numbers in the range
getday of the week
binary search
find pythagorean triplets
pattern program
check weather sum of digits of minimum element in the array is even or odd
factorial of a number
pattern alternating 0's and 1's
manchester program
exponent of a number
sum of squares of elements in the given array
removal of vowels in the string
find greatest factor of a given number
find LCM of n numbers
multiplication table
print palindrome in the range
print even or odd pattern
print prime numbers in the range
getday of the week
binary search
find pythagorean triplets
pattern program
check weather sum of digits of minimum element in the array is even or odd
factorial of a number
pattern alternating 0's and 1's
manchester program
exponent of a number
#include<stdio.h>
int positiveexponent(int base,int exponent);
float allexponent(int base,int exponent);
int main() {
int base, exponent;
scanf("%d%d",&base,&exponent);
allexponent(base,exponent);
}
float allexponent(int base,int exponent){
if(exponent>0){
printf("%d",positiveexponent(base,exponent));
}
else{
printf("%f",1/(float)positiveexponent(base,exponent*-1));
}
}
int positiveexponent(int base,int exponent){
if(exponent==1){
return base*exponent;
}
else{
return base*positiveexponent(base,exponent-1);
}
}
int positiveexponent(int base,int exponent);
float allexponent(int base,int exponent);
int main() {
int base, exponent;
scanf("%d%d",&base,&exponent);
allexponent(base,exponent);
}
float allexponent(int base,int exponent){
if(exponent>0){
printf("%d",positiveexponent(base,exponent));
}
else{
printf("%f",1/(float)positiveexponent(base,exponent*-1));
}
}
int positiveexponent(int base,int exponent){
if(exponent==1){
return base*exponent;
}
else{
return base*positiveexponent(base,exponent-1);
}
}
input:
2 3
output:
8
reverse of a sentence
#include <stdio.h>
#include<string.h>
int main()
{
char str[100];
int i,len;
gets(str);
len=strlen(str);
for(i=len-1;i>=0;i--)
{
printf("%c", str[i]);
}
}
input:
good morning
output:
gninrom doog
#include<string.h>
int main()
{
char str[100];
int i,len;
gets(str);
len=strlen(str);
for(i=len-1;i>=0;i--)
{
printf("%c", str[i]);
}
}
input:
good morning
output:
gninrom doog
removal vowels in the string
#include <stdio.h>
#include<string.h>
int main()
{
char str[100];
int i;
gets(str); // fgets(str,100,stdin);
for(i=0;str[i]!='\0';i++)
{
if(str[i]!='U'&&str[i]!='O'&&str[i]!='I'&&str[i]!='E'&&str[i]!='A'&&str[i]!='a'&&str[i]!='e'&&str[i]!='o'&&str[i]!='i'&&str[i]!='u')
{
printf("%c",str[i]);
}
}
getchar();
}
#include<string.h>
int main()
{
char str[100];
int i;
gets(str); // fgets(str,100,stdin);
for(i=0;str[i]!='\0';i++)
{
if(str[i]!='U'&&str[i]!='O'&&str[i]!='I'&&str[i]!='E'&&str[i]!='A'&&str[i]!='a'&&str[i]!='e'&&str[i]!='o'&&str[i]!='i'&&str[i]!='u')
{
printf("%c",str[i]);
}
}
getchar();
}
input:
good morning
output:
gd mrnng
sum of squares of elements in the given array
#include<stdio.h>
int sqarr(int);
int main()
{
int a[50],n,i,j,res,sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<5;i++)
{
res=sqarr(a[i]);
sum=sum+res;
}
printf("%d ",sum);
}
int sqarr(int n)
{
int a;
a=n*n;
return a;
}
input:
int sqarr(int);
int main()
{
int a[50],n,i,j,res,sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<5;i++)
{
res=sqarr(a[i]);
sum=sum+res;
}
printf("%d ",sum);
}
int sqarr(int n)
{
int a;
a=n*n;
return a;
}
input:
5
1 2 3 4 5
output:
55
find greatest factor of a given number
#include <stdio.h>
int caluculatefactor(int number);
int checkgreatestfactor(int num);
int main()
{
int num,res;
scanf("%d",&num);
res=checkgreatestfactor(num);
printf("%d ",res);
}
int caluculatefactor(int number)
{
int i=0,maxfactor=0;
for(i=1;i<=number/2;i++)
{
if(number%i==0)
maxfactor=i;
}
return maxfactor;
}
int checkgreatestfactor(int num)
{
if(num==0)
return 0;
else
return (caluculatefactor(num));
}
int caluculatefactor(int number);
int checkgreatestfactor(int num);
int main()
{
int num,res;
scanf("%d",&num);
res=checkgreatestfactor(num);
printf("%d ",res);
}
int caluculatefactor(int number)
{
int i=0,maxfactor=0;
for(i=1;i<=number/2;i++)
{
if(number%i==0)
maxfactor=i;
}
return maxfactor;
}
int checkgreatestfactor(int num)
{
if(num==0)
return 0;
else
return (caluculatefactor(num));
}
input:
100
output:
50
find LCM of n numbers
#include<stdio.h>
int caluculategenerallcm(int arr[],int);
int caluculatelcm(int,int);
int main()
{
int arr[50],n,res,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
res=caluculategenerallcm(arr,n);
printf("%d",res);
}
int caluculatelcm(int a,int b)
{
int lcm=a;
while(1)
{
if(lcm%b==0&&lcm%a==0)
{
break;
}
lcm++;
}
return lcm;
}
int caluculategenerallcm(int *arr,int len)
{
int i,m;
int l=arr[0];
for(i=1;i<len;i++)
{
m=arr[i];
l=caluculatelcm(l,m);
}
return l;
}
input:
5
10 20 30 40 50
output:
600
int caluculategenerallcm(int arr[],int);
int caluculatelcm(int,int);
int main()
{
int arr[50],n,res,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
res=caluculategenerallcm(arr,n);
printf("%d",res);
}
int caluculatelcm(int a,int b)
{
int lcm=a;
while(1)
{
if(lcm%b==0&&lcm%a==0)
{
break;
}
lcm++;
}
return lcm;
}
int caluculategenerallcm(int *arr,int len)
{
int i,m;
int l=arr[0];
for(i=1;i<len;i++)
{
m=arr[i];
l=caluculatelcm(l,m);
}
return l;
}
input:
5
10 20 30 40 50
output:
600
multiplication table
#include <stdio.h>
void printtable(int);
int main()
{
int num;
scanf("%d",&num);
printtable(num);
}
void printtable(int num)
{
int value=0,i;
for(i=1;i<=10;i++)
{
value=num*i;
printf("%d * %d = %d \n",num,i,value);
}
}
input:
5
output:
5 * 1 = 5
5 * 2 = 10
5 * 3 = 15
5 * 4 = 20
5 * 5 = 25
5 * 6 = 30
5 * 7 = 35
5 * 8 = 40
5 * 9 = 45
5 * 10 = 50
void printtable(int);
int main()
{
int num;
scanf("%d",&num);
printtable(num);
}
void printtable(int num)
{
int value=0,i;
for(i=1;i<=10;i++)
{
value=num*i;
printf("%d * %d = %d \n",num,i,value);
}
}
input:
5
output:
5 * 1 = 5
5 * 2 = 10
5 * 3 = 15
5 * 4 = 20
5 * 5 = 25
5 * 6 = 30
5 * 7 = 35
5 * 8 = 40
5 * 9 = 45
5 * 10 = 50
print palindrome in the range
#include <stdio.h>
void printpalindrome(int,int);
int main()
{
int num,digit;
scanf("%d%d",&num,&digit);
printpalindrome(num,digit);
}
void printpalindrome(int num,int digit)
{
int i,ds=1;
for(i=1;i<=digit;i++)
ds*=10;
for(i=num;i<ds;i++)
{
int temp=i,rem;
int rev=0;
while(temp)
{
rem=temp%10;
rev=(rev*10)+rem;
temp=temp/10;
}
if(i==rev)
printf("%d ",i);
}
}
input:
793 3
output:
797 808 818 828 838 848 858 868 878 888 898 909 919 929 939 949 959 969 979 989 999
void printpalindrome(int,int);
int main()
{
int num,digit;
scanf("%d%d",&num,&digit);
printpalindrome(num,digit);
}
void printpalindrome(int num,int digit)
{
int i,ds=1;
for(i=1;i<=digit;i++)
ds*=10;
for(i=num;i<ds;i++)
{
int temp=i,rem;
int rev=0;
while(temp)
{
rem=temp%10;
rev=(rev*10)+rem;
temp=temp/10;
}
if(i==rev)
printf("%d ",i);
}
}
793 3
output:
797 808 818 828 838 848 858 868 878 888 898 909 919 929 939 949 959 969 979 989 999
print even or odd pattern
#include <stdio.h>
void printpattern(int);
int main()
{
int num;
scanf("%d",&num);
printpattern(num);
}
void printpattern(int num)
{
int i,print=0;
if(num%2==0)
{
print=0;
for(i=0;i<num;i++)
{
printf("%d ",print);
print+=2;
}
}
else
{
print=1;
for(i=0;i<num;i++)
{
printf("%d ", print);
print+=2;
}
}
}
void printpattern(int);
int main()
{
int num;
scanf("%d",&num);
printpattern(num);
}
void printpattern(int num)
{
int i,print=0;
if(num%2==0)
{
print=0;
for(i=0;i<num;i++)
{
printf("%d ",print);
print+=2;
}
}
else
{
print=1;
for(i=0;i<num;i++)
{
printf("%d ", print);
print+=2;
}
}
}
input:
11
ouput:
1 3 5 7 9 11 13 15 17 19 21
getday of the week
#include <stdio.h>
char *getday(int num);
int main()
{
int num=4;
char* res;
res=getday(num);
printf("%s",res);
}
char *getday(int num)
{
char *str;
switch(num)
{
case 1:str="monday";
break;
case 2:str="monday";
break;
case 3:str="monday";
break;
case 4:str="monday";
break;
case 5:str="monday";
break;
case 6:str="monday";
break;
case 7:str="monday";
break;
default: printf("invalid");
break;
}
return str;
}
output:
monday
print prime numbers in the range
#include<stdio.h>
void printPrime(int,int);
int main()
{
int num,digit;
scanf("%d %d",&num,&digit);
printPrime(num,digit);
return 0;
}
void printPrime(int num,int digit)
{
int i;
while(num>=digit)
{
int flag=0;
for(i=2;i<=num/2;i++)
{
if(num%i==0)
{
flag=1;
break;
}
}
if(flag==0)
printf(" %d",num);
num--;
}
}
input:
25 3
output:
23 19 17 13 11 7 5 3
void printPrime(int,int);
int main()
{
int num,digit;
scanf("%d %d",&num,&digit);
printPrime(num,digit);
return 0;
}
void printPrime(int num,int digit)
{
int i;
while(num>=digit)
{
int flag=0;
for(i=2;i<=num/2;i++)
{
if(num%i==0)
{
flag=1;
break;
}
}
if(flag==0)
printf(" %d",num);
num--;
}
}
25 3
output:
23 19 17 13 11 7 5 3
binary search
#include <stdio.h>
int binarysearch(int arr[],int len,int target);
int main()
{
int arr[100],n,res,i,target;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
scanf("%d",&target);
res=binarysearch(arr,n-1,target);
printf("%d",res);
}
int binarysearch(int arr[],int len,int target)
{
int hi=len,lo=0;
while(lo<=hi)
{
int mid=(lo+hi)/2;
if(arr[mid]==target)
{
return mid;
}
else if(arr[mid]<target)
{
lo=mid+1;
}
else
{
hi=mid-1;
}
}
return -1;
}
7
5 9 11 12 14 16 17
11
output:
2
find pythagorean triplets
#include<stdio.h>
void pytriplets(int);
int main()
{
int limit;
scanf("%d",&limit);
pytriplets(limit);
return 0;
}
void pytriplets(int limit)
{
int a,b,c=0,n;
int m=2;
while(c<limit)
{
for(n=1;n<m;n++)
{
a=m*m-n*n;
b=2*m*n;
c=m*m+n*n;
if(c>limit)
break;
printf("%d %d %d\n",a,b,c);
}
m++;
}
}
input:
10
output
3 4 5
8 6 10
void pytriplets(int);
int main()
{
int limit;
scanf("%d",&limit);
pytriplets(limit);
return 0;
}
void pytriplets(int limit)
{
int a,b,c=0,n;
int m=2;
while(c<limit)
{
for(n=1;n<m;n++)
{
a=m*m-n*n;
b=2*m*n;
c=m*m+n*n;
if(c>limit)
break;
printf("%d %d %d\n",a,b,c);
}
m++;
}
}
input:
10
output
3 4 5
8 6 10
pattern program
void main()
{
int r,c,n,i;
scanf("%d",&n);
for(r=1;r<=n;r++)
{
for(c=1;c<=r;c++)
{
if(r%2==0)
//printf("%d",r/2);
printf("0");
else
//printf("%c",'A'+r/2);
printf("1");
}
printf("\n");
}
}
input: 5
output:
1
00
111
0000
11111
{
int r,c,n,i;
scanf("%d",&n);
for(r=1;r<=n;r++)
{
for(c=1;c<=r;c++)
{
if(r%2==0)
//printf("%d",r/2);
printf("0");
else
//printf("%c",'A'+r/2);
printf("1");
}
printf("\n");
}
}
input: 5
output:
1
00
111
0000
11111
check weather sum of digits of minimum element in the array is even or odd
// if even print 1 otherwise print 0
#include<stdio.h>
int get(int *arr,int n){
int min,i,rem,c=0;
min=arr[0];
for(i=1;i<n;i++)
if(arr[i]<min)
min=arr[i];
while(min!=0){
rem=min%10;
c=c+rem;
min=min/10;
}
if(c%2==0)
return 1;
else
return 0;
}
void main(){
int arr[100],n,i,j,sum;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
sum=get(arr,n);
printf("%d",sum);
}
Input:
6
62 13 21 55 61 72
Output:
1
#include<stdio.h>
int get(int *arr,int n){
int min,i,rem,c=0;
min=arr[0];
for(i=1;i<n;i++)
if(arr[i]<min)
min=arr[i];
while(min!=0){
rem=min%10;
c=c+rem;
min=min/10;
}
if(c%2==0)
return 1;
else
return 0;
}
void main(){
int arr[100],n,i,j,sum;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
sum=get(arr,n);
printf("%d",sum);
}
Input:
6
62 13 21 55 61 72
Output:
1
insertion sort using functions
#include<stdio.h>
void insertion(int a[],int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
j=i;
while(a[j-1]>a[j]&& j>0)
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
j--;
}
}
for (i=0;i<n;i++)
printf("%d ",a[i]);
}
int main() {
int a[20],n,i;
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &a[i]);
insertion(a,n);
return 0;
}
Input
6
5 4 2 7 6 9
Output:
2 4 5 6 7 9
void insertion(int a[],int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
j=i;
while(a[j-1]>a[j]&& j>0)
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
j--;
}
}
for (i=0;i<n;i++)
printf("%d ",a[i]);
}
int main() {
int a[20],n,i;
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &a[i]);
insertion(a,n);
return 0;
}
Input
6
5 4 2 7 6 9
Output:
2 4 5 6 7 9
Selection sort using functions
#include<stdio.h>
void selection(int a[],int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if (a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for (i=0;i<n;i++)
printf("%d ",a[i]);
}
int main() {
int a[20],n,i;
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &a[i]);
selection(a,n);
return 0;
}
Input:
6
5 4 2 7 6 9
Output
2 4 5 6 7 9
void selection(int a[],int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if (a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for (i=0;i<n;i++)
printf("%d ",a[i]);
}
int main() {
int a[20],n,i;
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &a[i]);
selection(a,n);
return 0;
}
Input:
6
5 4 2 7 6 9
Output
2 4 5 6 7 9
Bubble Sort using functions
#include<stdio.h>
void bubble(int a[],int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if (a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for (i=0;i<n;i++)
printf("%d ",a[i]);
}
int main() {
int a[20],n,i;
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &a[i]);
bubble(a,n);
return 0;
}
Input
6
5 4 2 7 6 9
Output
2 4 5 6 7 9
void bubble(int a[],int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if (a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for (i=0;i<n;i++)
printf("%d ",a[i]);
}
int main() {
int a[20],n,i;
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &a[i]);
bubble(a,n);
return 0;
}
Input
6
5 4 2 7 6 9
Output
2 4 5 6 7 9
return an element whose sum of left side and right side is equal in the array
Find the index of equilibrium element in the given array. In an array
equilibrium element is the one where the sum of all the elements to the
left side is equal to the sum of all the elements in the right side.
Return Value:
1) Return -1 if no equilibrium element is found
2) In case there is more than one equilibrium element, return the element with least index value.
You are required to complete the given code by reusing the existing function. You can click on Compile & run anytime to check the compilation/execution status of the program you can use printf to debug your code. The submitted code should be logically/syntactically correct and pass all the test cases.
solution:
#include<stdio.h>
int left_side_sum(int a[], int n, int idx)
{
int sum = 0, i;
for(i = 0; i < idx; i++)
{
sum += a[i];
}
return sum;
}
// Return the sum of elements from index (idx + 1) to (n – 1)
int right_side_sum(int a[], int n, int idx)
{
int sum = 0, i;
for(i = idx + 1; i < n; i++)
{
sum += a[i];
}
return sum;
}
// returns -1 if no equilibrium index found
int findEquilibriumIndex(int a[], int n)
{
int i;
for(i = 0; i < n; i++)
{
if(left_side_sum(a, n, i) == right_side_sum(a, n, i))
{
return i;
}
}
return -1;
}
int main()
{
//code
int a[10], n, i;
// get the elements count
scanf("%d",&n);
// get the array elements
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
int equiIndex = findEquilibriumIndex(a, n);
if(equiIndex != -1)
{
printf("%d", a[equiIndex]);
}
return 0;
}
input:
6
1 2 3 4 3 3
output:
4
Return Value:
1) Return -1 if no equilibrium element is found
2) In case there is more than one equilibrium element, return the element with least index value.
You are required to complete the given code by reusing the existing function. You can click on Compile & run anytime to check the compilation/execution status of the program you can use printf to debug your code. The submitted code should be logically/syntactically correct and pass all the test cases.
solution:
#include<stdio.h>
int left_side_sum(int a[], int n, int idx)
{
int sum = 0, i;
for(i = 0; i < idx; i++)
{
sum += a[i];
}
return sum;
}
// Return the sum of elements from index (idx + 1) to (n – 1)
int right_side_sum(int a[], int n, int idx)
{
int sum = 0, i;
for(i = idx + 1; i < n; i++)
{
sum += a[i];
}
return sum;
}
// returns -1 if no equilibrium index found
int findEquilibriumIndex(int a[], int n)
{
int i;
for(i = 0; i < n; i++)
{
if(left_side_sum(a, n, i) == right_side_sum(a, n, i))
{
return i;
}
}
return -1;
}
int main()
{
//code
int a[10], n, i;
// get the elements count
scanf("%d",&n);
// get the array elements
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
int equiIndex = findEquilibriumIndex(a, n);
if(equiIndex != -1)
{
printf("%d", a[equiIndex]);
}
return 0;
}
input:
6
1 2 3 4 3 3
output:
4
Frequency of each character in the string
#include<stdio.h>
void main()
{
char s[100];
int f[256]={0},i,j;
fgets(s,100,stdin); //gets(s);
for(i=0;s[i]!='\0';i++)
{
f[s[i]]++;
}
for(i=0;i<256;i++)
{
if(f[i]>0)
printf("%c occurs %d times\n",i,f[i]);
}
}
Input:
helLo how@are_raju*@#
Output
occurs 1 times
occurs 1 times
# occurs 1 times
* occurs 1 times
@ occurs 2 times
L occurs 1 times
_ occurs 1 times
a occurs 2 times
e occurs 2 times
h occurs 2 times
j occurs 1 times
l occurs 1 times
o occurs 2 times
r occurs 2 times
u occurs 1 times
w occurs 1 times
Frequency of each character in a string of lowercase letters only
void main()
{
char s[100];
int f[26]={0},i,j;
clrscr();
scanf("%s",s);
for(i=0;s[i]!='\0';i++)
{
f[s[i]-'a']++;
}
for(i=0;i<26;i++)
{
if(f[i]>0)
printf("%c occurs %d times\n",i+'a',f[i]);
}
}
input:
hello
output:
e occurs 1 times
h occurs 1 times
l occurs 2 times
o occurs 1 times
{
char s[100];
int f[26]={0},i,j;
clrscr();
scanf("%s",s);
for(i=0;s[i]!='\0';i++)
{
f[s[i]-'a']++;
}
for(i=0;i<26;i++)
{
if(f[i]>0)
printf("%c occurs %d times\n",i+'a',f[i]);
}
}
input:
hello
output:
e occurs 1 times
h occurs 1 times
l occurs 2 times
o occurs 1 times
Find neatest (lowest) common ancestor of two given nodes X1 and X2
/* Find neatest (lowest) common ancestor of two given nodes X1 and X2
input format : an integer T denoting number of test cases followed by 3 T Lines as each test case will
contain 3 lines
first line N
second line elements
where the no at index i is the parent of node i . The parent of root is -1
third line X1 and X2
output:
for each test case out put a single line that has the neatest (lowest) common ancestor of two given nodes X1 and X2
*/
#include<stdio.h>
#include <queue>
#include <vector>
using namespace std;
# define MAX_Q_SIZE 25
// A tree node
struct Node
{
int key;
struct Node *left, *right;
};
// Utility function to create new Node
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Creates a node with key as 'i'. If i is root, then it changes
// root. If parent of i is not created, then it creates parent first
void createNode(int parent[], int i, Node *created[], Node **root)
{
// If this node is already created
if (created[i] != NULL)
return;
// Create a new node and set created[i]
created[i] = newNode(i);
// If 'i' is root, change root pointer and return
if (parent[i] == -1)
{
*root = created[i];
return;
}
// If parent is not created, then create parent first
if (created[parent[i]] == NULL)
createNode(parent, parent[i], created, root);
// Find parent pointer
Node *p = created[parent[i]];
// If this is first child of parent
if (p->left == NULL)
p->left = created[i];
else // If second child
p->right = created[i];
}
// Creates tree from parent[0..n-1] and returns root of the created tree
Node *createTree(int parent[], int n)
{
// Create an array created[] to keep track
// of created nodes, initialize all entries
// as NULL
Node *created[n];
for (int i=0; i<n; i++)
created[i] = NULL;
Node *root = NULL;
for (int i=0; i<n; i++)
createNode(parent, i, created, &root);
return root;
}
// Finds the path from root node to given root of the tree, Stores the
// path in a vector path[], returns true if path exists otherwise false
bool findPath(Node *root, vector<int> &path, int k)
{
// base case
if (root == NULL) return false;
// Store this node in path vector. The node will be removed if
// not in path from root to k
path.push_back(root->key);
// See if the k is same as root's key
if (root->key == k)
return true;
// Check if k is found in left or right sub-tree
if ( (root->left && findPath(root->left, path, k)) ||
(root->right && findPath(root->right, path, k)) )
return true;
// If not present in subtree rooted with root, remove root from
// path[] and return false
path.pop_back();
return false;
}
// Returns LCA if node n1, n2 are present in the given binary tree,
// otherwise return -1
int findLCA(Node *root, int n1, int n2)
{
// to store paths to n1 and n2 from the root
vector<int> path1, path2;
// Find paths from root to n1 and root to n1. If either n1 or n2
// is not present, return -1
if ( !findPath(root, path1, n1) || !findPath(root, path2, n2))
return -1;
/* Compare the paths to get the first different value */
int i;
for (i = 0; i < path1.size() && i < path2.size() ; i++)
if (path1[i] != path2[i])
break;
return path1[i-1];
}
// Driver method
int main()
{
int x1,x2;
int k,T,n;
int result[100] ;
int parent[1000];
scanf("%d",&T);
k=T;
while(k>=1)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&parent[i]);
Node *root = createTree(parent, n);
scanf("%d%d",&x1,&x2);
result[k]=findLCA(root, x1, x2);
//printf("\nresult %d",result[k]);
k--;
}
for(int j=T;j>=1;j--)
printf("\n%d",result[j]);
}
input:
2
6
5 -1 1 1 5 2
0 3
7
-1 0 0 1 1 3 5
6 5
o/p
1
5
input format : an integer T denoting number of test cases followed by 3 T Lines as each test case will
contain 3 lines
first line N
second line elements
where the no at index i is the parent of node i . The parent of root is -1
third line X1 and X2
output:
for each test case out put a single line that has the neatest (lowest) common ancestor of two given nodes X1 and X2
*/
#include<stdio.h>
#include <queue>
#include <vector>
using namespace std;
# define MAX_Q_SIZE 25
// A tree node
struct Node
{
int key;
struct Node *left, *right;
};
// Utility function to create new Node
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Creates a node with key as 'i'. If i is root, then it changes
// root. If parent of i is not created, then it creates parent first
void createNode(int parent[], int i, Node *created[], Node **root)
{
// If this node is already created
if (created[i] != NULL)
return;
// Create a new node and set created[i]
created[i] = newNode(i);
// If 'i' is root, change root pointer and return
if (parent[i] == -1)
{
*root = created[i];
return;
}
// If parent is not created, then create parent first
if (created[parent[i]] == NULL)
createNode(parent, parent[i], created, root);
// Find parent pointer
Node *p = created[parent[i]];
// If this is first child of parent
if (p->left == NULL)
p->left = created[i];
else // If second child
p->right = created[i];
}
// Creates tree from parent[0..n-1] and returns root of the created tree
Node *createTree(int parent[], int n)
{
// Create an array created[] to keep track
// of created nodes, initialize all entries
// as NULL
Node *created[n];
for (int i=0; i<n; i++)
created[i] = NULL;
Node *root = NULL;
for (int i=0; i<n; i++)
createNode(parent, i, created, &root);
return root;
}
// Finds the path from root node to given root of the tree, Stores the
// path in a vector path[], returns true if path exists otherwise false
bool findPath(Node *root, vector<int> &path, int k)
{
// base case
if (root == NULL) return false;
// Store this node in path vector. The node will be removed if
// not in path from root to k
path.push_back(root->key);
// See if the k is same as root's key
if (root->key == k)
return true;
// Check if k is found in left or right sub-tree
if ( (root->left && findPath(root->left, path, k)) ||
(root->right && findPath(root->right, path, k)) )
return true;
// If not present in subtree rooted with root, remove root from
// path[] and return false
path.pop_back();
return false;
}
// Returns LCA if node n1, n2 are present in the given binary tree,
// otherwise return -1
int findLCA(Node *root, int n1, int n2)
{
// to store paths to n1 and n2 from the root
vector<int> path1, path2;
// Find paths from root to n1 and root to n1. If either n1 or n2
// is not present, return -1
if ( !findPath(root, path1, n1) || !findPath(root, path2, n2))
return -1;
/* Compare the paths to get the first different value */
int i;
for (i = 0; i < path1.size() && i < path2.size() ; i++)
if (path1[i] != path2[i])
break;
return path1[i-1];
}
// Driver method
int main()
{
int x1,x2;
int k,T,n;
int result[100] ;
int parent[1000];
scanf("%d",&T);
k=T;
while(k>=1)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&parent[i]);
Node *root = createTree(parent, n);
scanf("%d%d",&x1,&x2);
result[k]=findLCA(root, x1, x2);
//printf("\nresult %d",result[k]);
k--;
}
for(int j=T;j>=1;j--)
printf("\n%d",result[j]);
}
input:
2
6
5 -1 1 1 5 2
0 3
7
-1 0 0 1 1 3 5
6 5
o/p
1
5
Level Order Traversal
// C program to construct a Binary Tree from parent array
#include<stdio.h>
#include <queue>
using namespace std;
# define MAX_Q_SIZE 25
// A tree node
struct Node
{
int key;
struct Node *left, *right;
};
// Utility function to create new Node
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Creates a node with key as 'i'. If i is root, then it changes
// root. If parent of i is not created, then it creates parent first
void createNode(int parent[], int i, Node *created[], Node **root)
{
// If this node is already created
if (created[i] != NULL)
return;
// Create a new node and set created[i]
created[i] = newNode(i);
// If 'i' is root, change root pointer and return
if (parent[i] == -1)
{
*root = created[i];
return;
}
// If parent is not created, then create parent first
if (created[parent[i]] == NULL)
createNode(parent, parent[i], created, root);
// Find parent pointer
Node *p = created[parent[i]];
// If this is first child of parent
if (p->left == NULL)
p->left = created[i];
else // If second child
p->right = created[i];
}
// Creates tree from parent[0..n-1] and returns root of the created tree
Node *createTree(int parent[], int n)
{
// Create an array created[] to keep track
// of created nodes, initialize all entries
// as NULL
Node *created[n];
for (int i=0; i<n; i++)
created[i] = NULL;
Node *root = NULL;
for (int i=0; i<n; i++)
createNode(parent, i, created, &root);
return root;
}
void printLevelOrder(Node *root)
{
// Base Case
if (root == NULL) return;
// Create an empty queue for level order tarversal
queue<Node *> q;
// Enqueue Root and initialize height
q.push(root);
while (q.empty() == false)
{
// nodeCount (queue size) indicates number
// of nodes at current lelvel.
int nodeCount = q.size();
// Dequeue all nodes of current level and
// Enqueue all nodes of next level
while (nodeCount > 0)
{
Node *node = q.front();
printf("%d\t",node->key);
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
nodeCount--;
}
printf("\n");
}
}
// Driver method
int main()
{
int k,T,n;
int result[100] ;
int parent[1000];
scanf("%d",&T);
k=T;
while(k>=1)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&parent[i]);
Node *root = createTree(parent, n);
printLevelOrder(root);
k--;
}
}
input:
2
6
5 -1 1 1 5 2
7
-1 0 0 1 1 3 5
output:
1
2 3
5
0 4
0
1 2
3 4
5
6
#include<stdio.h>
#include <queue>
using namespace std;
# define MAX_Q_SIZE 25
// A tree node
struct Node
{
int key;
struct Node *left, *right;
};
// Utility function to create new Node
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Creates a node with key as 'i'. If i is root, then it changes
// root. If parent of i is not created, then it creates parent first
void createNode(int parent[], int i, Node *created[], Node **root)
{
// If this node is already created
if (created[i] != NULL)
return;
// Create a new node and set created[i]
created[i] = newNode(i);
// If 'i' is root, change root pointer and return
if (parent[i] == -1)
{
*root = created[i];
return;
}
// If parent is not created, then create parent first
if (created[parent[i]] == NULL)
createNode(parent, parent[i], created, root);
// Find parent pointer
Node *p = created[parent[i]];
// If this is first child of parent
if (p->left == NULL)
p->left = created[i];
else // If second child
p->right = created[i];
}
// Creates tree from parent[0..n-1] and returns root of the created tree
Node *createTree(int parent[], int n)
{
// Create an array created[] to keep track
// of created nodes, initialize all entries
// as NULL
Node *created[n];
for (int i=0; i<n; i++)
created[i] = NULL;
Node *root = NULL;
for (int i=0; i<n; i++)
createNode(parent, i, created, &root);
return root;
}
void printLevelOrder(Node *root)
{
// Base Case
if (root == NULL) return;
// Create an empty queue for level order tarversal
queue<Node *> q;
// Enqueue Root and initialize height
q.push(root);
while (q.empty() == false)
{
// nodeCount (queue size) indicates number
// of nodes at current lelvel.
int nodeCount = q.size();
// Dequeue all nodes of current level and
// Enqueue all nodes of next level
while (nodeCount > 0)
{
Node *node = q.front();
printf("%d\t",node->key);
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
nodeCount--;
}
printf("\n");
}
}
// Driver method
int main()
{
int k,T,n;
int result[100] ;
int parent[1000];
scanf("%d",&T);
k=T;
while(k>=1)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&parent[i]);
Node *root = createTree(parent, n);
printLevelOrder(root);
k--;
}
}
input:
6
5 -1 1 1 5 2
7
-1 0 0 1 1 3 5
output:
1
2 3
5
0 4
0
1 2
3 4
5
6
maximum depth of a tree in ds
//Create a tree with N values where the number at index i is the parent of node i. The parent of root is -1.
#include<bits/stdc++.h>
using namespace std;
// A tree node
struct Node
{
int key;
struct Node *left, *right;
};
// Utility function to create new Node
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Creates a node with key as 'i'. If i is root, then it changes
// root. If parent of i is not created, then it creates parent first
void createNode(int parent[], int i, Node *created[], Node **root)
{
// If this node is already created
if (created[i] != NULL)
return;
// Create a new node and set created[i]
created[i] = newNode(i);
// If 'i' is root, change root pointer and return
if (parent[i] == -1)
{
*root = created[i];
return;
}
// If parent is not created, then create parent first
if (created[parent[i]] == NULL)
createNode(parent, parent[i], created, root);
// Find parent pointer
Node *p = created[parent[i]];
// If this is first child of parent
if (p->left == NULL)
p->left = created[i];
else // If second child
p->right = created[i];
}
// Creates tree from parent[0..n-1] and returns root of the created tree
Node *createTree(int parent[], int n)
{
// Create an array created[] to keep track
// of created nodes, initialize all entries
// as NULL
Node *created[n];
for (int i=0; i<n; i++)
created[i] = NULL;
Node *root = NULL;
for (int i=0; i<n; i++)
createNode(parent, i, created, &root);
return root;
}
}
}
//Find Depth of the tree
int maxDepth(struct Node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
// Driver method
int main()
{
int parent[] = {-1,0,0,1,1,3,5};
int n = sizeof parent / sizeof parent[0];
Node *root = createTree(parent, n);
printf("\nHight of tree is %d", maxDepth(root)-1);
newLine();
}
#include<bits/stdc++.h>
using namespace std;
// A tree node
struct Node
{
int key;
struct Node *left, *right;
};
// Utility function to create new Node
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Creates a node with key as 'i'. If i is root, then it changes
// root. If parent of i is not created, then it creates parent first
void createNode(int parent[], int i, Node *created[], Node **root)
{
// If this node is already created
if (created[i] != NULL)
return;
// Create a new node and set created[i]
created[i] = newNode(i);
// If 'i' is root, change root pointer and return
if (parent[i] == -1)
{
*root = created[i];
return;
}
// If parent is not created, then create parent first
if (created[parent[i]] == NULL)
createNode(parent, parent[i], created, root);
// Find parent pointer
Node *p = created[parent[i]];
// If this is first child of parent
if (p->left == NULL)
p->left = created[i];
else // If second child
p->right = created[i];
}
// Creates tree from parent[0..n-1] and returns root of the created tree
Node *createTree(int parent[], int n)
{
// Create an array created[] to keep track
// of created nodes, initialize all entries
// as NULL
Node *created[n];
for (int i=0; i<n; i++)
created[i] = NULL;
Node *root = NULL;
for (int i=0; i<n; i++)
createNode(parent, i, created, &root);
return root;
}
}
}
//Find Depth of the tree
int maxDepth(struct Node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
// Driver method
int main()
{
int parent[] = {-1,0,0,1,1,3,5};
int n = sizeof parent / sizeof parent[0];
Node *root = createTree(parent, n);
printf("\nHight of tree is %d", maxDepth(root)-1);
newLine();
}
Subscribe to:
Posts (Atom)