Competitive Programming
Practical No: 01
Title: Write a program on 3n+1 Problem.
Aim: Implement the 3n+1 program.
Theory:
Consider the following algorithm to generate a sequence of numbers. Start with an
integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with
the new value of n, terminating when n = 1.
For example, the following sequence of numbers will be generated for n = 22:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every
integer n. Still, the conjecture holds for all integers up to at least 1,000,000. For an input n, the
cycle-length of n is the number of numbers generated up to and including the 1.
In the example above, the cycle length of 22 is 16.
Given an integer i determine the cycle length .
Input Format
An integer n
Output Format
An integer : cycle length
Sample Input
22
Sample Output
16
Explanation
for n = 22:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Cycle length = 16
Source Code:
#include<stdio.h>
int main ()
,
int n, m,i,k,j,c,s;
while (scanf("%d %d",&n,&m)==2)
, s=0; printf ("%d %d", n,m);
if(n>m)
,
k=m
;
m=n
;
n=k; -
for(i=n;i<=m;
i++)
, c=1;
j=i;
while(j > 1)
, if(j % 2==0) j=j/2;
else j=(3*j)+1; c++; -
if(c>=s) s=c; -
printf ("%d",s);
-
return 0;
-
Output:
Conclusion:-
In this Practical we learned that Program on 3n+1 Problem.
Practical No: 02
Title: Write a program for Counting.
Aim: Implement a program for Counting.
Theory:
C program to find the frequency of characters in a string: This program counts the
frequency of characters in a string, i.e., which character is present how many times in the
string. For example, in the string "code" each of the characters 'c,' 'd,' 'e,' and 'o' has occurred
one time. Only lower case alphabets are considered, other characters (uppercase and special
characters) are ignored. You can easily modify this program to handle uppercase and special
symbols.
Source Code:
#include<stdio.h>
/* #include<conio.h>*/
#include<stdlib.h>
#include<string.h>
int main()
,
char string*100+;
int c = 0, count*26+ = ,0-, x;
//clrscr();
printf("Enter a
string\n");
gets(string);
while (string*c+ != '\0') ,
/** Considering characters from 'a' to 'z' only and ignoring others. */
if (string*c+ >= 'a' && string*c+
<= 'z') , x = string*c+ - 'a';
count*x+++;
-
c++;
-
for (c = 0; c < 26; c++) printf("%c occurs %d times in
the string.\n", c + 'a', count*c+);
//getch()
; return
0;
-
Output:
Conclusion:-
In this Practical we learned that Program on Counting.
Practical No: 03
Title: Write a Program on Permutation.
Aim: Implementation of the permutation.
Theory:
Permutation refers number of ways in which set members can be arranged
or ordered in some fashion. The formula of permutation of arranging k elements
out of n elements is
nPk = n! / (n – k)!
Algorithm:
This algorithm only focuses on permutation without going into details of factorial −
START
Step 1 → Define values for n and r
Step 2 → Calculate factorial of n and (n-r) Step 3
→ Divide factorial(n) by factorial(n-r)
Step 4 → Display result as permutation STOP
Syntax:
procedure permutation()
Define n and r
P = factorial(n) / factorial(n-r)
DISPLAY P
end procedure.
Source Code:
#include
<stdio.h> int
factorial(int n) ,
int f;
for(f = 1; n > 1; n--) f
*= n;
return f;
int npr(int n,int r)
return factorial(n)/factorial(n-r);
-
int main()
,
int n, r;
n = 4;
r = 3; printf("%dp%d = %d \n", n, r,
npr(n,r));
return 0;
-
Output:
Conclusion:- In this practical we learned that Program on Permutation.
Practical No: 04
Title: Program for contest Scoreboard.
Aim: Implementation of contest Scoreboard.
Theory:
Think the contest score boards are wrong? Here’s your chance to come up with the
right rankings. Contestants are ranked first by the number of problems solved (the more the
better), then by decreasing amounts of penalty time. If two or more contestants are tied in
both problems solved and penalty time, they are displayed in order of increasing team
numbers. A problem is considered solved by a contestant if any of the submissions for that
problem was judged correct. Penalty time is computed as the number of minutes it took for
the first correct submission for a problem to be received plus 20 minutes for each incorrect
submission received prior to the correct solution.
Unsolved problems incur no time penalties.
Input:
The input begins with a single positive integer on a line by itself indicating the number
of the cases following, each of them as described below. This line is followed by a blank line,
and there is also a blank line between two consecutive inputs. Input consists of a snapshot of
the judging queue, containing entries from some or all of contestants 1 through 100 solving
problems 1 through 9. Each line of input will consist of three numbers and a letter in the
format contestant problem time L where L can be ‘C’, ‘I’, ‘R’, ‘U’ or ‘E’. These stand for Correct,
Incorrect, clarification Request, Unjudged and Erroneous submission. The last three cases do
not affect scoring. Lines of input are in the order in which submissions were received.
Output:
For each test case, the output must follow the description below. The outputs of two
consecutive cases
will be separated by a blank line. Output will consist of a scoreboard sorted as previously
described. Each line of output will contain a contestant number, the number of problems
solved by the contestant and the time penalty accumulated by the contestant. Since not all of
contestants 1-
100 are actually participating, display only the contestants that have made a submi ssion.
Source Code:
#include<stdio.h> struct cricketer
,
int runs,wickets;
char name*25+;
-player*100+;
int main()
,
int i,n;
printf("Enter the no of cricket players\n"); scanf("%d",&n);
printf("Enter player info as name , runs scored , wickets taken\n"); for(i=0;i<n;i++)
, scanf("%s %d
%d",player*i+.name,&player*i+.runs,&player*i+.wickets);
-
printf("\nNAME\t\tRUNS\t\tWICKETS\n");
for(i=0;i<n;i++)
,
printf("%s\t\t%d\t\t%d\n",player*i+.name,player*i+.runs,player*i+.wickets);
-
return 0;
-
Output:-
1 1 2 10 1
3 1 11 C
1 2 19 R
1 2 21 C
1 1 25 C
1 2 66
3 1 11
Conclusion:-
In this practical we learned that program for Contest Scoreboard.
Practical No: 05
Title : Write Program To Find Prime Numbers.
Aim : Implement Program To Find Prime Numbers.
Theory:
Prime Number : A prime number is a natural number greater than 1 that has no positive
divisors other than 1 and itself. The first few prime numbers are ,2, 3, 5, 7, 11, ….-
The idea to solve this problem is to iterate through all the numbers starting from 2 to sqrt(N)
using a for loop and for every number check if it divides N. If we find any number that divides,
we return false. If we did not find any number between 2 and sqrt(N) which divides N then it
means that N is prime and we will return True.
Why did we choose sqrt(N)?
The reason is that the smallest and greater than one factor of a number cannot be more than
the sqrt of N. And we stop as soon as we find a factor. For example, if N is 49, the smallest
factor is 7. For 15, smallest factor is 3. Below is the C program to check if a number is prime:
Program:-
// C program to check if a
// number is prime
#include
<math.h>
#include
<stdio.h>
int main()
,
int n, i, flag = 1;
// Ask user for input
printf("Enter a number:
\n");
// Store input number in a variable
scanf("%d", &n);
// Iterate from 2 to
sqrt(n) for (i = 2; i <=
sqrt(n); i++) ,
// If n is divisible by any number between
// 2 and n/2, it is
not prime if (n % i
== 0) , flag = 0;
break;
-
-
if (n <=
1)
fl
a
g
=
0;
if (flag == 1) , printf("%d is a prime
number", n);
-
else printf("%d is not a prime number", n);
,
-
return 0;
-
Output:
Conclusion:- In this Practical i learned to implement prime number program.
Practical No: 06
Title : Write Program To Find GCD Of Given Number.
Aim : To Implement Program To Find GCD Of Given Number.
Theory:
GCD Of Two Numbers : It is the highest number that completely divides two or more
numbers. It is abbreviated for GCD. It is also known as the Greatest Common Factor (GCF)
and the Highest Common Factor (HCF). It is used to simplify the fractions. The HCF or GCD of
two integers is the largest integer that can exactly divide both numbers (without a
remainder).
How to Find the Greatest Common
Factor Write all the factors of
each number.
Select the common factors.
Select the greatest number,
as GCF.
Example: Find the GCF of 12 and 8.
Solution:
Factors of 12: 1, 2, 3, 4, 6, 12
Factors of 8: 1, 2, 4, 8
Common Factors: 1, 2, 4
Greatest Common Factor: 4
Program:-
#include
<stdio.h> int
main()
, int n1, n2,
i, gcd;
printf("En
ter two
integers:
");
scanf("%d
%d",
&n1,
&n2);
for(i=1; i <= n1 && i <= n2; ++i)
,
// Checks if i is factor of both
integers if(n1%i==0 &&
n2%i==0) gcd = i;
-
printf("G.C.D of %d and %d is %d", n1, n2, gcd);
return 0;
-
Output:
Conclusion:- In this Practical i learned to Implement Program To Find GCD Of Given Number.
Practical No: 07
Title : Write Program To Find Modulous Of Two Numbers.
Aim : To Implement Program To Find Modulous Of Two Numbers.
Theory:
Modulus Operator : The modulus operator is a symbol used in various programming languages. It
is denoted by the percentage symbol (%). It is a modulus operator that is used in the arithmetic
operator. It determines the remainder. In some cases, the remainder may be 0, it means the
number is completely divisible by the divisor.
Syntax : reminder = a % b;
In the above Syntax, a and b are two integers, and the % (Percent) symbol is a modulus operator
that divides a by b and returns the remainder.
Program:-
#include
<stdio.h> int
main() ,
int dividend, divisor, quotient,
remainder; printf("Enter dividend: ");
scanf("%d",
÷nd);
printf("Enter divisor: ");
scanf("%d", &divisor);
// Computes quotient
quotient = dividend /
divisor;
// Computes remainder
remainder = dividend %
divisor;
printf("Quotient = %d\n",
quotient); printf("Remainder =
%d", remainder); return 0;
-
Output:
Conclusion:- In this Practical i learned to Implement Program To Find Modulous Of Two Numbers.
Practical No: 08
Title: Write a program on Reverse and Add.
Aim: implement the Reverse and Add.
Theory:
C program to reverse and add a number. This program reverses and add a number entered
by a user and then print it on the screen. For example, if a user will enter 123 as input then 321
will be printed and sum the numbers and display the output.
Source code:
#include<stdio.h>
#include<conio.h>
int main()
,
int num, rev=0, n, digit;
clrscr();
printf("\n\t Enter the number: ");
scanf("%d", &num);
n = num;
while(n != 0)
, digit = n % 10;
rev = rev*10 +
digit; n = n/10;
-
printf("\n\t Reverse of entered number: %d", rev);
printf("\n\ t sum = %d", rev + num);
getch();
return 0;
-
Output:
Conclusion:-
In this Practical we learned that Program on Reverse and Add.