SPOJ PROBLEM 16211: BORING FACTORIALS

Problem Link: http://www.spoj.com/problems/DCEPC11B/


SUMMARY
Given two number n and p. Your task is to print answer i.e equal to n!%p

Logic
Wilson’s Theorem 

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

.

 Now from this we can write:
(p-1)!   ≡  -1 (mod p)
1*2*3*.........*(n-1)*(n)*..............*(p-1)  ≡   -1 (mod p)
n!*(n+1)*...........*(p-1)   ≡   -1 (mod p)
n!  ≡    -1*[(n+1)*...............(p-2)*(p-1)]^-1 (mod p)

let a=[(n+1)*...............(p-2)*(p-1)]

so

n!≡-1*a^-1(mod p)

From Fermat's Theorem:

a^(p-1) ≡ 1(mod p)

multiply both side by a^-1

a^(p-2)  ≡ a^-1(mod p)

now simply we have to find a^(p-2) mod p

To View My Solution:

https://github.com/shivam04/spoj/blob/master/DCEPC11B

Find The Missing Number

FIND THE MISSING NUMBER

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

Example:
I/P    [1, 2, 4, ,6, 3, 7, 8]
O/P    5

METHOD 1(Use sum formula)
Algorithm:

1. Get the sum of numbers 
       total = n*(n+1)/2
2  Subtract all the numbers from sum and
   you will get the missing number.

Code:





#include<stdio.h>



/* getMissingNo takes array and size of array as arguments*/

int getMissingNo (int a[], int n)

{

    int i, total;

    total  = (n+1)*(n+2)/2;  

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

       total -= a[i];

    return total;

}



/*program to test above function */

int main()

{

    int a[] = {1,2,4,5,6};

    int miss = getMissingNo(a,5);

    printf("%d", miss);

    getchar();

}






Time Complexity: O(n)





METHOD 2(Use XOR)
  1) XOR all the array elements, let the result of XOR be X1.
  2) XOR all numbers from 1 to n, let XOR be X2.
  3) XOR of X1 and X2 gives the missing number.

Code:






#include<stdio.h>



/* getMissingNo takes array and size of array as arguments*/

int getMissingNo(int a[], int n)

{

    int i;

    int x1 = a[0]; /* For xor of all the elemets in arary */

    int x2 = 1; /* For xor of all the elemets from 1 to n+1 */

     

    for (i = 1; i< n; i++)

        x1 = x1^a[i];

            

    for ( i = 2; i <= n+1; i++)

        x2 = x2^i;        

    

    return (x1^x2);

}



/*program to test above function */

int main()

{

    int a[] = {1, 2, 4, 5, 6};

    int miss = getMissingNo(a, 5);

    printf("%d", miss);

    getchar();

}






Time Complexity: O(n)