Wilson's Theorem

In number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if 

((n-1)!) mod n =(n-1)

That is, it asserts that the factorial (n - 1)! = 1 * 2 * 3 * ...............*(n - 1) is one less than a multiple of n exactly when n is a prime number.

for example :

for n= 4
(n-1) ! = 6
(n-1) ! mod n =2

for n= 5
(n-1) ! = 24
(n-1) ! mod n = 4

for n=6
(n-1) != 120

(n-1) ! mod n =0 

for n=11
(n-1) ! = 3628800
(n-1) ! mod n = 10

for n =12
(n-1)! = 39916800
(n-1) ! mod n = 0

Proof:
It is easy to check the result when n is 2 or 3, so let us assume n > 3. If n is composite, then its positive divisors are among the integers

1, 2, 3, 4, ... , n-1

and it is clear that gcd( (n-1)! , n) > 1, so we can not have (n-1)! = -1 (mod n).

However if n is prime, then each of the above integers are relatively prime to n. So for each of these integers a there is another b such that ab = 1 (mod n). It is important to note that this b is unique modulo n, and that since n is prime, a = b if and only if a is 1 or n-1. Now if we omit 1 and n-1, then the others can be grouped into pairs whose product is one showing

2.3.4.....(n-2) = 1 (mod n)

(or more simply (n-2)! = 1 (mod n)). Finally, multiply this equality by n-1 to complete the proof.

Note : Wilson theorem holds only for prime numbers .

Dutch Flag Problem

Q.) Given an array containing lower case and upper case alphabets and numbers, how can you sort/arrange the array in one single pass using just one variable for swapping such that the resultant array should put the input elements into 3 buckets in the following fashion - Input - aA1B23Cbc4 Output - abcABC1234 Note - ordering doesn't matter the output could be - ABC1234abc or 1234abcABC You just have to arrange the data into 3 buckets in single pass using just one temp variable for swapping. Expected runtime - O(n) and O(1) extra space.

Solution:

#include"stdio.h"
int main()
{
    int Size,i;
    scanf("%d",&Size);
    char arr[Size+1];
    scanf("%s",arr);
    int low=0,mid=1,high=Size-1;
    while(mid<=high)
    {
        if(arr[mid]>='0' && arr[mid]<='9')
        {
            arr[mid]=arr[low]+arr[mid]-(arr[low]=arr[mid]);
            low++;
            mid++;
        }
        else if(arr[mid]>='a' && arr[mid]<='z')
            mid++;
        else if(arr[mid]>='A' && arr[mid]<='Z')
        {
            arr[mid]=arr[high]+arr[mid]-(arr[high]=arr[mid]);
            high--;
        }
    }
    printf("%s",arr);
    return 0;
}

YMCA Short Coding Contest SCC040913

Question 1.)

Given two number a and b.Count how many numbers in the range a to b(including both a and b) has odd number of divisors. 

Input 
First line of input contains number of test cases T.Each of the next T lines contains two number a and b. 

Output 
For each test case output a single line containing resulting count. 

Constraints 

T<=100 
1<=a<=b<=10^12 

Sample Input 

1 
2 5 

Sample Output 

1

Explanation 

Divisors of 2:1,2 
Divisors of 3:1,3 
Divisors of 4:1,2,4 
Divisors of 5:1,5 
So only 4 has odd number of divisors which gives count as 1. 


Lets take some examples

Number                  Divisors           Number of Divisors

1                          1                   1(odd)
2                         1,2                  2(even)
3                         1,3                  2(even)
4                         1,2,4                3(odd)
5                         1,5                  2(even)
6                         1,2,3,6              4(even)
7                         1,7                  2(even)
8                         1,2,4,8              4(even)
9                         1,3,9                3(odd)
10                        1,2,5,10             4(even)
11                        1,11                 2(even)
12                        1,2,3,4,6,12         6(even)
13                        1,13                 2(even)
14                        1,2,7,14             4(even)
15                        1,3,5,15             4(even)
16                        1,2,4,8,16           5(odd)
17                        1,17                 2(even)
18                        1,2,9,18             4(even)
19                        1,19                 2(even)
20                        1,2,4,5,10,20        6(even)
21                        1,3,7,21             4(even)
22                        1,2,11,22            4(even)
23                        1,23                 2(even)
24                        1,2,3,4,6,8,12,24    8(even)
25                        1,5,25               3(odd)


See the numbers who have odd number of divisors ,
Only 1,4,9,16,25 in range(1-25) have odd number of divisors and all these numbers are perfect square numbers.
1=1*1
4=2*2
9=3*3
16=4*4
25=5*5



Solution ::

#include"stdio.h"
#include "math.h"

int main()
{
    int t;
    scanf("%d",&t); // Test cases
    while(t--)
    {
        long long int a,b,ans=0;
        scanf("%lld%lld",&a,&b);
        ans=(int)(floor(sqrt(b)))-(int)(ceil(sqrt(a)))+1;
        printf("%lld\n",ans);
    }
    return 0;

}

Question 2.)

Given a string as input you have to remove the duplicates characters from the string .
String contains only small letters a-z (lowercase) .
Input 
First line of input contains number of test cases T.Each of the next T lines contains a single string . 

Output 

For each test case output a single string with no any duplicates characters.

Constraints 

1<=T<=10
1<=length(string)<=200

Sample Input 

2
ymca
manan

Sample Output 

ymca
man

Solution ::

#include"stdio.h"

#include"string.h"

int main()

{

    char str[205];

    scanf("%s",str); //read the string.

    int string_length=strlen(str),i;

    int hash[26]={0};

    for(i=0;i< string_length; i++)

    {

        int hash_position=str[i]-'a';

        if(hash[hash_position]==0)

        {

            printf("%c",str[i]);

            hash[hash_position]=1;

        }

    }

    printf("\n");

    return 0;

}

SQUARE ROOT OF A NUMBER

SQUARE ROOT OF A NUMBER

#include
float squareRoot(float n)
{
/*We are using n itself as initial approximation
This can definitely be improved */
float x = n;
float y = 1;
float e = 0.000001; /* e decides the accuracy level*/
while(x - y > e)
{
x = (x + y)/2;
y = n/x;
}
return x;
}

/* Driver program to test above function*/
int main()
{
int n;
scanf("%d",&n);
printf ("Square root of %d is %f", n, squareRoot(n));
getchar();
}

SPOJ :: IS IT TREE

Q.) given an unweighted and undirected graph write a program to check is it a tree or not.
input:
In first line contain n (numbers of nodes) and m (number of edges)
then m lines contain m egdes of grapg (two integer u and v)
1<=N<=10000 ,1<=M<=20000
output:
print YES if it is a tree else print NO.

Just we have to check the graph is connected and have no cycle then it will be tree else no.
----------------------------------------------------------------

#include
#include
#include
#include
using namespace std;

// This class represents a directed graph using adjacency list representation
class Graph
{
    int V;    // No. of vertices
    list *adj;    // Pointer to an array containing adjacency lists
    bool isCyclicUtil(int v, bool visited[], bool *rs);
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w); // function to add an edge to graph
    bool BFS(int s);  // prints BFS traversal from a given source s
    bool isCyclic();    // returns true if there is a cycle in this graph
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

bool Graph::BFS(int s)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;

    // Create a queue for BFS
    list queue;

    // Mark the current node as visited and enqueue it
    visited[s] = true;
    queue.push_back(s);

    // 'i' will be used to get all adjacent vertices of a vertex
    list::iterator i;

    while(!queue.empty())
    {
        // Dequeue a vertex from queue and print it
        s = queue.front();
       // cout << s << " ";
        queue.pop_front();

        // Get all adjacent vertices of the dequeued vertex s
        // If a adjacent has not been visited, then mark it visited
        // and enqueue it
        for(i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            if(!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
    for(int k=0;k
    {
if(visited[k]==false)
return false;
    }
    return true;
}
bool Graph::isCyclicUtil(int v, bool visit[], bool *recStack)
{
    if(visit[v] == false)
    {
        // Mark the current node as visited and part of recursion stack
        visit[v] = true;
        recStack[v] = true;

        // Recur for all the vertices adjacent to this vertex
        list::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
        {
            if ( !visit[*i] && isCyclicUtil(*i, visit, recStack) )
                return true;
            else if (recStack[*i])
                return true;
        }

    }
    recStack[v] = false;  // remove the vertex from recursion stack
    return false;
}

// Returns true if the graph contains a cycle, else false.

bool Graph::isCyclic()
{
    // Mark all the vertices as not visited and not part of recursion
    // stack
    bool *visit = new bool[V];
    bool *recStack = new bool[V];
    for(int i = 0; i < V; i++)
    {
        visit[i] = false;
        recStack[i] = false;
    }

    // Call the recursive helper function to detect cycle in different
    // DFS trees
    for(int i = 0; i < V; i++)
        if (isCyclicUtil(i, visit, recStack))
            return true;

    return false;
}
int main()
{
int j,n,m,a,b;
scanf("%d %d",&n,&m);
Graph g(n);
for(j=0;j
{
scanf("%d %d",&a,&b);
g.addEdge(a-1,b-1);
}
if(g.BFS(0))
{
if(g.isCyclic())
         cout << "NO"<
     else
         cout << "YES"<
}
else
printf("NO\n");
return 0;
}

HOW MANY GAMES (SPOJ)

PROBLEM CODE :GAMES
12448. HOW MANY GAMES
Write the average score x as a reduced fraction x=pq. This means that p and q are integers, that q is positive and that q is minimal (or, equivalently, that p and q have no nontrivial common factor). Then the player can have played any multiple of q games hence the minimum number of games the player should have played is q.

When x=−30.25, note that −30.25=−1214 and −121 and 4 have no common factors except +1 and −1, hence the minimum number of games is indeed 4.

SOLUTION//


#include"stdio.h"
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        gcd(b,a%b);
}
int main()
{
int t,num,count,i,j,len,pow,flag;
char s[50];
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
len=strlen(s);
count=0,flag=1;
for(j=len-1;j>=0;j--)
{
if(s[j]=='.'){
flag=0;
break;
}
else
count++;
}
num=0;
for(j=0;j
{
if(s[j]!='.')
num=10*num+(s[j]-'0');
}
pow=1;
if(flag==0){
for(i=0;i
{
pow=pow*10;
}
}
//printf("%d %d",num,pow);
printf("%d\n",pow/gcd(num,pow));
}
return 0;
}

MICROSOFT INTERVIEW QUESTION

/* QUESTION--
//http://www.careercup.com/question?id=16392679
The problem is given a string s1= "ABCDBCCDABCD". and a pattern "BC". we have to replace this pattern with other string ("UVW" or "U"or "uv"). Do this without creating new string.
Take the case to replace "BC" with following
a) "uvw" s1=AUVWDUVWCDAUVWD .
b) "U" s1=AUDUCDAUD .
c) "UV" s1=AUVDUVCDAUVD .

*/
/*Explaination
USING THE KMP algo the times of occurence and position of given pattern in the text then stored the position of the pattern  in two arrays (array a and array b ) 
for e.g text="Chandan"
pat="an";
replace="QQQ";
then a[0]=2,a[1]=5 and b[0]=3,b[1]=6
array containing the position of starting index postion of pattern and array b contain the ending position of the pattern .
now if using the KMP algo count the number of occurence of pattern in text.
and resize the string 
if(len_pattern
new_length=len_txt+count*(len_pattern-len_replace)
else there is no need to resize the string .
*/


#include//stdio.h
#include//string.h
#include//stdlib.h
int a[400];//ARRAYS TO STORE THE POSITION OF THE PATTERN IN THE STRING
int b[400];
int q=0,p=0;
void computeLPSArray(char *pat, int M, int *lps);

int KMPSearch(char *pat, char *txt)
{
 int count=0;
    int M = strlen(pat);
    int N = strlen(txt);

    // create lps[] that will hold the longest prefix suffix values for pattern
    int *lps = (int *)malloc(sizeof(int)*M);
    int j  = 0;  // index for pat[]

    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);

    int i = 0;  // index for txt[]
    while(i < N)
    {
      if(pat[j] == txt[i])
      {
        j++;
        i++;
      }

      if (j == M)
      {
  count++;
        //printf("%d\n", i-j);
        a[q]=i-j;
        b[p]=(i-j+M-1);
        //printf("%d %d\n",a[q],b[p]);
        q++,p++;

        j = lps[j-1];
      }

      // mismatch after j matches
      else if(pat[j] != txt[i])
      {
        // Do not match lps[0..lps[j-1]] characters,
        // they will match anyway
        if(j != 0)
         j = lps[j-1];
        else
         i = i+1;
      }
    }
 return count;
    //free(lps); // to avoid memory leak
}

void computeLPSArray(char *pat, int M, int *lps)
{
    int len = 0;  // lenght of the previous longest prefix suffix
    int i;

    lps[0] = 0; // lps[0] is always 0
    i = 1;

    // the loop calculates lps[i] for i = 1 to M-1
    while(i < M)
    {
       if(pat[i] == pat[len])
       {
         len++;
         lps[i] = len;
         i++;
       }
       else // (pat[i] != pat[len])
       {
         if( len != 0 )
         {
      // This is tricky. Consider the example AAACAAAA and i =7.
           len = lps[len-1];

           // Also, note that we do not increment i here
         }
         else // if (len == 0)
         {
           lps[i] = 0;
           i++;
         }
       }
    }
}
int main()
{
    char txt[500],pat[500],replace[100];
    scanf("%s",txt);
    scanf("%s",pat);
    scanf("%s",replace);
    int len_txt=strlen(txt);
    int len_pat=strlen(pat);
    int len_replace=strlen(replace);
    int count=KMPSearch(pat, txt);

    int i,j,k,new_length;
    if(len_replace>=len_pat)
    {
        int increase_size=(len_replace*count)-(count*len_pat);
         new_length=len_txt+increase_size;
        txt[new_length];
        
        p=p-1;
       
        j=new_length-1;
        for(i=len_txt-1;i>=0;i--)
        {
            if(p>=0&&b[p]==i)
            {
                    k=len_replace-1;
                    while(k>=0)
                    {
                        txt[j]=replace[k];
                        k--;
                        j--;
                    }
                    p--;
                    i=i-len_pat+1;
            }
            else
            {
                txt[j]=txt[i];
                j--;
            }
        }
        printf("%s",txt);
    }
    else
    {
        int size=q-1;
        int decrease_size=(count*len_pat)-(count*len_replace);
        new_length=len_txt-decrease_size;
        j=0;
        q=0;
        for(i=0;i
        {
            if(q<=size&&a[q]==i)
            {
                k=0;
                while(k
                {
                    txt[j]=replace[k];
                    k++;
                    j++;
                }
                q++;
                i=i+len_pat-1;
            }
            else
            {
                txt[j]=txt[i];
                j++;
            }
        }
     txt[j]='\0';
        printf("%s",txt);
    }
    return 0;
}