WAP to SUM the Fibonnaci Series

#include
#include
long int fib(long int);
int main()
{
long int sum=0;
long int k;
int i,n;
printf("\nEnter the number of element in the series : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
k=fib(i);
sum=sum+k;
}
printf("sum of %ld",sum);
return (0);
}
long int fib(long int n)
{
if(n<=1)
{
return n;
}
else
{
return fib(n-1)+fib(n-2);
}
}

Hash Table Implementation Using Quadratic probing

import java.io.*;
class hash_quadratic{
public static void main(String args[]) throws Exception{
int n=11,i,k,j,flag;
int a[]=new int[11];
int hash[]=new int[11];
BufferedReader cin= new BufferedReader (new InputStreamReader(System.in));
System.out.println("enter the elements to be sorted");
for(i=0;i a[i]= Integer.parseInt(cin.readLine());
hash[i]=0;
}
for(i=0;i flag=0;
j=0;
while(flag!=1){
k=((2*a[i]+5)%11+j*j)%11;
if(hash[k]==0){
hash[k]=a[i];
flag=1;}
else{
j++;
}

}
}
System.out.println("hash table is");
for(i=0;i System.out.print(i+"\t");
System.out.println(hash[i]);
}
}
}

Run Here https://ideone.com/7CsuT

Hash Table Implementation Using Linear Probing

import java.io.*;
class hash
{
public static void main(String args[]) throws Exception
{
int n=11,l,i,k,flag;
int a[]=new int[11];
int hash[]=new int[11];
BufferedReader cin= new BufferedReader (new InputStreamReader(System.in));
System.out.println("Enter the elements ");
for(i=0;i {
a[i]= Integer.parseInt(cin.readLine());
hash[i]=0;
}
for(i=0;i {
k=(2*a[i]+5)%11;
flag=0;
while(flag!=1){
if(hash[k]==0){
hash[k]=a[i];
flag=1;
}
else
k=(k+1)%11;//linear probing
}
}
System.out.println("hash table is");
for(i=0;i System.out.print(i+"\t");
System.out.println(hash[i]);
}
}
}


TC O(n)
Sc O(n)
Rune https://ideone.com/xdpXr

class hanoi
{
public static void main (String args[])
{
Integer N = new Integer(3);
H_dohanoi(N.intValue(), 1,3, 2);
System.exit(0);
}

static void H_dohanoi(int n, int from, int to, int via)
{
if (n > 0) {
H_dohanoi(n-1, from, via, to);
H_moveit(from, to);
H_dohanoi(n-1, via, to, from);
}
}

static void H_moveit(int from, int to)
{
System.out.print("move ");
System.out.print(from);
System.out.print(" --> ");
System.out.println(to);
}
}
Run Here https://ideone.com/Qy5nh

WAP to Find Maximum sum such that no two elements are adjacent

Question: Given an array all of whose elements are positive numbers, find the maximum sum of a sub-sequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Algorithm:
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.

Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).

At the end of the loop return max of incl and excl.

Example:

arr[] = {5, 5, 10, 40, 50, 35}

inc = 5
exc = 0

For i = 1 (current element is 5)
incl = (excl + arr[i]) = 5
excl = max(5, 0) = 5

For i = 2 (current element is 10)
incl = (excl + arr[i]) = 15
excl = max(5, 5) = 5

For i = 3 (current element is 40)
incl = (excl + arr[i]) = 45
excl = max(5, 15) = 15

For i = 4 (current element is 50)
incl = (excl + arr[i]) = 65
excl = max(45, 15) = 45

For i = 5 (current element is 35)
incl = (excl + arr[i]) = 80
excl = max(5, 15) = 65

And 35 is the last element. So, answer is max(incl, excl) = 80


Implementation:
?
#include

/*Function to return max sum such that no two elements
are adjacent */
int FindMaxSum(int arr[], int n)
{
int incl = arr[0];
int excl = 0;
int excl_new;
int i;

for (i = 1; i < n; i++) { /* current max excluding i */ excl_new = (incl > excl)? incl: excl;

/* current max including i */
incl = excl + arr[i];
excl = excl_new;
}

/* return max of incl and excl */
return ((incl > excl)? incl : excl);
}

/* Driver program to test above function */
int main()
{
int arr[] = {5, 5, 10, 100, 10, 5};
printf("%d \n", FindMaxSum(arr, 6));
getchar();
return 0;
}

Time Complexity: O(n)

A DP Approach

1. Make an array S equal to the length of the given array where
S[0] = a[0] and S[1] = max(a[0],a[1])

2. for i:2 to n-1
S[i] = max(S[i-2]+a[i], S[i-1])

3. return S[n-1]


Time Complexity: O(n)
Space Complexity: O(n)

Find Maximum in Partially Increasing & Partially Decresing Array

There is an integer array. The array represent a graph which increases till one point and then start decreasing. WAP to find the maximum number in that array. Write production quality code which handles all the scenarios. He also checked various combinations of number with my code.


#include
#include

/* Standard Binary Search function*/
//binarySearch(arr, 0,7)

int binarySearch(int arr[], int low, int high)
{

if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/

if(arr[mid-1]arr[mid+1])
return arr[mid];
if(arr[mid-1] return binarySearch(arr, (mid + 1), high);
else if(arr[mid-1]>arr[mid] && arr[mid]>arr[mid+1])
return binarySearch(arr, low, (mid -1));
}
/*Return -1 if element is not found*/
return -1;
}

/* Driver program to check above functions */
int main()
{
int arr[] = {3, 4, 5, 6,7,1, 2};
printf("Maximum Element in Array is %d", binarySearch(arr, 0,5));
getchar();
return 0;
}


Run Here https://ideone.com/JOzXP

WAP to Convert Decimal to BInary Without An Extra Memory

#include

void showbits ( int n )
{
int i, k, andmask ;
for ( i = 8 ; i >= 0 ; i-- )
{
andmask = 1 << i ;
k = n & andmask ;
k == 0 ? printf ( "0" ) : printf ( "1" ) ;
}
}

int main()
{
showbits(10);


}

WAP to Sort 2D Array/Matrix

// --Sorting Program--
// -------------------
// Example Program to sort
// 2D array using linear
// representation of the array
#include

#define MAX 3

int main(void)
{
int arr[MAX][MAX]={{8,9,7},{3,2,1},{5,4,6}} ;
int i,j,temp;
int *arr_ptr;



// we have taken a pointer
// to the 2D array to
// represent it linearly

// C-style type cast
// is necessary here
arr_ptr=(int*)arr;

// sorting is done here.
// selection sort method of
// sorting is employed here
// you can use whichever
// method you like

// here MAX*MAX is used
// because the no. of elements
// in the linear representation
// of the 2D array has that
// many elements
for(i=0;i<((MAX*MAX)-1);i++)
for(j=i+1;j<(MAX*MAX);j++)
if(*(arr_ptr+i)>*(arr_ptr+j))
{
temp=*(arr_ptr+i);
*(arr_ptr+i)=*(arr_ptr+j);
*(arr_ptr+j)=temp;
}
// sorting is done till here



for(i=0;i {
for(j=0;j printf(" %d ",arr[i][j]);
printf(" \n");
}
}

WAP to Calculate The Factorial of BIG NUmber(Obvious Integer,Long) That Can't Fit In Memory at a time

In order to learn this big number arithmetic lets take an example of calculating factorial of big numbers

24 = 4!
120 = 5! 8-bit unsigned int
720 = 6!
5040 = 7!
40320 = 8! 16-bit unsigned int(not exactly)
362880 = 9!
39916800 = 11!

479001600 = 12! 32-bit unsigned (this is the maximum number that can fit in the integer of size of 32 bit) =2147483647

87178291200 = 14!
6402373705728000 = 18!
121645100408832000 = 19!
2432902008176640000 = 20! 64-bit unsigned
51090942171709440000 = 21!
8222838654177922817725562880000000 = 31!
263130836933693530167218012160000000 = 32
295232799039604140847618609643520000000 = 34! 128-bit unsigned

Now if we have to calculate something like 100! then it not possible to do with inbuilt int(4 byte) long long int (8 byte)Now, the maximum number that we can store in an unsigned 32 bit integer is 2 ^ 32 - 1 and in an unsigned 64 bit integer is 2 ^ 64 - 1. Something like 100!('!' is the notation for factorial) has over 150 decimal digits. The data types mentioned earlier can store numbers having at most 9 and 19 decimal digits respectively. So, we need to find a way to store the 150+ digits that we will get as the answer. The simplest data structure that we can use is an integer array of size of about 200 to be on the safe side.
#include
#include
void factorial(int n)
{
int digit[160];
int m, carry,d,i,last;
for(i=0;i<160;i++) digit[i]=0; digit[0]=1; last=0; for(m=1;m<=n;m++) { carry=0; for(i=0;i<=last;i++) {d=digit[i]*m+carry; digit[i]=d%10; carry=d/10; } while(carry>0)
{
last=last + 1;
digit[last]=carry%10;
carry=carry/10;
}
}

for(i=last;i>=0;i--)
printf("%d",digit[i]);
printf("\n");

}
int main()
{
factorial(100);
int n=pow(2,32)-1;
printf(" %d ", n);

}

Factorial of 100 =93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Run Here https://ideone.com/fgaSP

C++ Code Recursive Version

#include
#include

int max = 5000;

void display(int arr[]){
int ctr = 0;
for (int i=0; i<=0; --i){
arr[i] = (arr[i] * n) + carry;
carry = arr[i]/10;
arr[i] %= 10;
}
factorial(arr,n-1);
}

int main(){
int *arr = new int[max];
std::memset(arr,0,max*sizeof(int));
arr[max-1] = 1;
int num=100;
std::cout<<"Enter the number: ";

std::cout<<"factorial of "<<<"is :\n";
factorial(arr,num);
display(arr);
delete[] arr;
return 0;
}

Run Here https://ideone.com/R7Q0F

I suggest you people to go through this article http://www.codeproject.com/KB/recipes/factorial.aspx 
5 Fast Way to Computer Big Factorial https://www.luschny.de/math/factorial/FastFactorialFunctions.htm

we have an array of 2n elements like "a1 a2...an b1 b2...bn". WAP to rearrange the array as "a1 b1 a2 b2...an bn" time complexity is O(n) no extra RAM

#include
#define SWAP(a,b) a^=b^=a^=b

int string[100];
int m;

void Replace(int n,int start){
int i,j;
for(i=start,j=0;j {
SWAP(string[i],string[n+i]);
}
n=n-1;
if(n>0)
Replace(n,start+1);
}

main()
{
int i;
printf("Enter no of elements (max 100): ");
scanf("%d",&m);
if(m%2){
printf("odd nos\n");
}
else{
printf("Enter numbers: ");
for(i=0;i scanf("%d",&string[i]);
for(i=0;i printf("%d\t",string[i]);
printf("\n");

Replace(m/2-1,1);
for(i=0;i printf("%d\t",string[i]);
printf("\n");
}
}