SPOJ PROBLEM 21079. THE RESISTANCE

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

SUMMARY:
In this problem, we are constructing a long network of resistors composed of N blocks. Every block has two 1 ohm resistors, shown below by the upper-left figure. We would like for you to measure the net resistance across the two leftmost terminals in a circuit with N blocks. If the circuit has one block (N=1), then the net resistance across the leftmost terminals is 1 ohm, because the horizontal resistor is not in a path connecting the leftmost terminals. Similarly, for a circuit with two blocks (N=2), the net resistance is 2/3 ohms. The figures below illustrate this.

Logic:
ans = (fibo(2n-1)%m)/(fibo(2n)%m)

To View My Solution:

https://github.com/shivam04/spoj/blob/master/RESSTNCE.cpp

SPOJ PROBLEM 8001. FIBONACCI SUM

Problem Link: http://www.spoj.com/SPOJ/problems/FIBOSUM/

SUMMARY:

The fibonacci sequence is defined by the following relation:

F(0) = 0

F(1) = 1

F(N) = F(N - 1) + F(N - 2), N >= 2

Your task is very simple. Given two non-negative integers N and M, you have to calculate the sum (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.

Logic:

What I have done is that I used matrix powers a nice way to find F[n] (nth term of Fibonacci Series) 

you can calculate this using fast matrix exponentiation i.e nth power of the matrix above at L.H.S gives you the value of (n+1)th Fibonacci number as the element at row and column (1,1) in the resultant matrix. 

at first try to write the first few Fibonacci numbers:
0  1  1  2  3  5  8  13  21  34  55

now write the sum of Fibonacci numbers from 0 to i:
0  1  2  4  7  12  20  33  54

looking the pattern given above we found that

Sum(N) = F(N+2) ---------> (1)

where sum(N) is sum up to Nth term of Fibonacci series

and the simple way to calculate the sum of all the numbers b/w "N" and "M" is: sum(M)-sum(N-1)

so (F(N) + F(N + 1) + ... + F(M)) mod 1000000007 = (sum(M)-sum(N-1)) mod 1000000007

from (1)

sum(M) = F(M+2) and

sum(N-1) = F(N+1)

now the final results become:

(F(N) + F(N + 1) + ... + F(M)) mod 1000000007 = (F(M+2)-F(N+1))mod 1000000007

To View My Solution:

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

SPOJ PROBLEM 21332. PIGEONHOLE TOWER

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

SUMMARY:

Pigeon SSNA want to build a tower with some wood walls. Let's describe the tower they want to make:

1. A Tower can consist of different number of level.
2. If a tower contain L levels then 1^st level must contain L  holes , 2^nd level L-1 , 3^rd level L-2 ….. L level contain 1 hole .
3. Each room contain 3 wood walls.

See the picture below:

                                                     

                                           3 Level Tower                                      4 Level tower

Now pigeon SSNA has n wood walls. What is maximum number of level he can made. 

Logic:

It's a simple mathematics based on n*(n+2) gives you the required solution so we have to find only the value of n.  

To View My Solution:

https://github.com/shivam04/spoj/blob/master/PHT.cpp

SPOJ PROBLEM 10575. THE YELLOW BRICKS ROAD

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

SUMMARY:
Each test case is given using several lines. The first line contains an integer N representing the number of different suppliers of yellow stone (2 ≤ N ≤ 1000). For simplicity, we assume that the engineers will buy exactly one stone from each supplier. Each of the next N lines contains three integers Ai, Bi, Ci (0 < Ai, Bi, Ci ≤ 1000, 1 ≤ i ≤ N) that describe, respectively, the width, height and depth of each stone provided by the i-th supplier. The last test case is followed by a line containing one zero.

For each test case, print one line containing the minimum number of identical cubes that can be cut from the given stones.

Logic

Cubes could be formed when all sides of individual cuboids are divisible by same no. or the volume is perfect cube.

So we have to maximize the volume with minimum number of cubes. So we must divide all sides with a number (a smallest number that divides all the sides).

To View My Solution:

https://github.com/shivam04/spoj/blob/master/YELBRICK.cpp

SPOJ PROBLEM 74. DIVISOR SUMMATION

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

SUMMARY:

Given a natural number n (1 <= n <= 500000), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.
e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Logic
The logic for solving this question is that divisors always exist in pairs. So, for a number ‘t’, if ‘i’ is a divisor then ‘t/i’ is also a divisor.
And the smaller number of any divisor pair is always less than or equal to the square root of the number.


To View My Solution:
https://github.com/shivam04/spoj/blob/master/DIVSUM.cpp

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)