1. Implement a function which gets the intersection of two sorted arrays. Assuming numbers in each array are unique.

The function must return the elements common to both arrays.
1) traverse the arrays parallely
2) move the array which has larger value
3) if values match copy to third array

#include<stdio.h>
int  intersection(int *arr1, int n1, int * arr2, int n2, int *result)
{
    int i,j,k=0;
    while(i<n1 && j<n2)
    {
        if(arr1[i]<arr2[j])
            i++;
        else if(arr1[i]>arr2[j])
            j++;
        else
           {
            result[k++]=arr1[i++];
            j++;
           }
     }
     return k;
}

void read_array(int *arr,int sz)
{
     int i;
     printf("Enter sorted array elements:");
     for(i  =0;i<sz;i++)
     { 
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]= %d    ",i,arr[i]);        
     }
     printf("\n");
}
int main()
{
    int arr1[50],arr2[50];
    int resultarr[50]; 
    int n1, n2, nres; 
    printf("Enter the size of array 1 :"); 
    scanf("%d",&n1);
    read_array(arr1,n1);
    printf("Enter the size of array 2 :"); 
    scanf("%d",&n2);
    read_array(arr2,n2);
    nres = intersection(arr1,n1,arr2,n2,resultarr);    
    printf("The intersection array is ");
    print_array(resultarr,nres);    
    return 0;
}

2. Write a function to rotate array elements by k

To rotate an array, you should move the elements to the right and wrap back.

1) move all elements to right by one place
2) copy the last element to 0th element
3) Repeat steps 1 and 2 k times

Other method which is faster but needs extra space is
copy all the elements to temp array
copy 0 to n-k-1 elements to locations k to n into temp
copy n-k to n elements to location 0 to k into temp
copy them back to original array
This has a time complexity of O(n)

void rotate_array(int *arr,int n,int k)
{
   int i,j;
   for(j=0;j<k;j++)
   {
        int temp = arr[n-1];
        for(i=n-1;i>=0;i--)
              arr[i+1]=arr[i];
        arr[0]=temp;
   }
}

second method (using temporary array)
void rotate_array(int *arr,int n,int k)
{
   int i,j;
   int temp[50];
   /*copy shifted elements to temp*/
   for(i=0;i<n-k;i++)
     temp[i+k]=arr[i];
   for(i=n-k;i<n;i++)
     temp[i+k-n]=arr[i];
  /*copy back to arr*/
   for(i=0;i<n;i++)
     arr[i]=temp[i];  
}

3. Write a program to find contigious subarray with largest sum

Kadane's algorithm for finding largest subarray is very efficient and has a time complexity of O(n)

Two structures (which store maximum sum and indices of the range i and j) are used in this method. Maxcur and max.

Initially value of Maxcur and Max are taken as 0,0 and value of 0th element.

For each element i from 1 to n-1, the previous value of Maxcur is inspected.
This will be maximum sum of elements ending at i-1.
If this sum is negative, it is discarded and range is taken as i to i and sum is taken as a[i].
If it is not negative then a[i] is added to sum and range is taken as previous lower range to i.
the sum of Maxcur is compared with sum of Max. If Maxcur is greater, then Max is set to Maxcur.

http://en.m.wikipedia.org/wiki/Maximum_subarray_problem

/*Kadane's algorithm for finding maximum sum of contiguous subarray*/
#include<stdio.h>
#include<stdlib.h>
struct maxst
{
    int sum;
    int i,j;
};
struct maxst maximum_subarray(int *arr,int n)
{
       /*maxcur is the maximum of subarrays ending at i*/
       /*max is the maximum subarray*/
       struct maxst max,maxcur;
       int i;
       struct maxst *maxptr = calloc(sizeof(struct maxst),n);
       max.i=max.j=0;
       max.sum=arr[i];
       maxcur = max;
       for(i=1;i<n;i++)
       {
          /*if prev sum is 0. Dont include it*/
	  if(maxcur.sum < 0)
          {
              maxcur.sum = arr[i];
              maxcur.i=maxcur.j=i;
          }
          else
          {
              maxcur.sum +=arr[i];
              maxcur.j=i;
          }
          if(maxcur.sum>max.sum)
              max = maxcur;
          maxptr[i]=max;
        }
        return max;//maxptr[i];
 }
void print_array(int *arr,int n)
{
   int i;
   printf("Array elements are :");
   for(i=0;i<n;i++)
     printf(" %d  ",arr[i]);
   printf("\n");
}
 int main()
{
    int arr[]={-1,2,3,4,5,6,-7,8};
    print_array(arr,8);
    struct maxst s1 = maximum_subarray(arr,8);
    printf("The maximum subarray is %d to %d and sum is %d\n",s1.i,s1.j,s1.sum);
    return 0;
}

4. Write a function to print all pairs of elements whose sum is x.

The easiest method would be to take ith element and compare its sum with all subsequent elements and print if sum is equal to x. But this is ineffecient.

More effecient method would be - sort the array. Then take an element - n and binary search for x-n in the array and print if there is a match.

And a third method which requires extra space is hashing. Hashmap every element of the array to its value (key = array value value = array value). Now each element arr[i] find x-arr[i]. If hash(x-arr[i]) exists then print the pair.

 
/*the array needs to be sorted before calling this*/
void pairs_with_sumx(int *arr,int n,int x)
{
   int i,j,k;
   insertion_sort(arr,n);//not shown here
   print_array(arr,n);
   for(i = 0;i<n;i++)
   {
       if(i>0 && arr[i]==arr[i-1])//duplicate??
           continue;
        int num1= arr[i]; 
        int index = binary_search(arr,i+1,n,x-num1);
        if(index!=-1  && index>i)
            printf("%d and %d\n",num1,arr[index]); 
   }           
}
 
#define MAX 10000
void pairs_with_sumx_hash(int *arr,int n,int x)
{   
    int hash[MAX]={0};
    int i;
    for(i=0;i<n;i++)
    {
       hash[arr[i]]=arr[i];
    }
    for(i=0;i<n;i++)
    {
       int j = x - arr[i] ;
       if(j>0 && hash[j]!=0 && hash[j]!=arr[i] )
       {
            printf("The pair is %d and %d\n",arr[i],hash[j]);
            hash[j]=0;//so that it is not repeated
            hash[arr[i]]=0;
       }
    }
}

5. Write a function to split an array into two parts - array of positive number and array of negative numbers

#include<stdio.h>
 
int split_array(int *arr,int n,int *posarr,int * negarr)
{
     int i,j,k;
     j = k = 0;
     for(i=0;i<n;i++)
        if(arr[i]>0)
            posarr[j++] = arr[i];
        else
           negarr[k++] = arr[i];
     return j;
}
void read_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       printf("%d   ",arr[i]);
     }
     printf("\n");
}
int main()
{
    int arr[50];
    int posarr[50],negarr[50]; 
    int sz; 
    printf("Enter the size of array:"); 
    scanf("%d",&sz);
    read_array(arr,sz);
    int sizep,sizen;
    sizep = split_array(arr,sz,posarr,negarr);
    printf("The array of positive numbers is ");
    print_array(posarr,sizep);
    printf("The array of negative numbers is ");
    print_array(negarr,sz-sizep);
    //print_array(arr,sz);
    return 0;
}

6. An array has elements in increasing order and after reaching the largest element, they are stored in decreasing order. Find the largest element of this array.

We need to find the first element which is smaller than its previous element. The element before this will be the largest element

#include<stdio.h>
 
int find_largest_index(int *arr,int n )
{ 
   int i;
   for(i=1;i<n;i++)
      if(arr[i]<arr[i-1])
      /*here elements start decreasing*/
         return i-1;
   if(i==n)
   /*no such value found*/
       return -1; 
}
void read_array(int *arr,int sz)
{
     int i;
     printf("Enter array elements:");
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       printf("%d   ",arr[i]);
     }
     printf("\n");
}
int main()
{
    int arr[50];
    int posarr[50],negarr[50]; 
    int sz,n; 
    printf("Enter the size of array:"); 
    scanf("%d",&sz);
    read_array(arr,sz);
    if( (n=find_largest_index(arr,sz))>-1)
        printf("The largest element of the array is %d\n",arr[n]);
    else
        printf("The largest element is %d\n",arr[sz-1]);
    return 0;
}

7. Write a function to merge two sorted arrays.

The function compares elements of first and second array. And copies the smaller ones to merged array and increments the counter.

At some point of time, there will be only one array elements left. They are directly copied to merged array.

This merging of sorted arrays is the basis of merge sorting algorithm.

#include<stdio.h>
 
void merge_sorted_arrays(int *arr1,int n1,int *arr2,int n2, int *arr3,int *n3)
{
    int i,j,k;
    i = j = k=0;
    while(i<n1 && j<n2)
    {
       /*copy smaller element*/
       if(arr1[i]<arr2[j])
          arr3[k++] = arr1[i++];
       else
          arr3[k++] = arr2[j++];
    }
    /*only one array elements are remaining*/
    while(i<n1)
       arr3[k++] = arr1[i++];
    while(j<n2)
       arr3[k++] = arr2[j++];
    *n3 = k;
}
void read_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       printf("%d   ",arr[i]);
     }
     printf("\n");
}
int main()
{
    int arr1[50],arr2[50],arr3[100];
    int sz1,sz2,sz3; 
    printf("Enter the size of first array:"); 
    scanf("%d",&sz1);
    printf("Enter the sorted array elements:");
    read_array(arr1,sz1);
    printf("Enter the size of second array:"); 
    scanf("%d",&sz2);
    printf("Enter the sorted array elements:");
    read_array(arr2,sz2);
    merge_sorted_arrays(arr1,sz1,arr2,sz2,arr3,&sz3);     
    printf("The merged array is ");
    print_array(arr3,sz3);
    return 0;
}

8. Write a function to delete an element from an array.

To delete an array element, to move all subsequent elements to the left by one place and then reduce the size of the array by 1.

e.g. To delete 3rd element of the array
move a[4] to a[3]
move a[5] to a[4] ... and so on.

#include<stdio.h>
void delete_element(int *arr,int *n,int de)
{
    int i;
    /*search*/
    for(i=0;i<*n && arr[i]!=de;i++)
       ;
    if(i==*n)
    {  printf("This element is not present");
      return;
    }
    /*pack*/
    for(;i<*n-1;i++)
      arr[i]=arr[i+1];
   (*n)--;
}
void read_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       printf("%d   ",arr[i]);
     }
     printf("\n");
}

int main()
{
    int arr[50];
    int de;
    int sz; 
    printf("Enter the size of array:"); 
    scanf("%d",&sz);
    read_array(arr,sz); 
    printf("Enter element to be deleted:");
    scanf("%d",&de);
    delete_element(arr,&sz,de);    
    print_array(arr,sz);
    return 0;
}

9. Write a function to insert an element to an array

To insert an element into an array at index i, we need to make room for that element. This is done by moving all elements from index i to the right by one place.

We are assuming that the array size is sufficient to hold this new item

#include<stdio.h>
void insert_element(int *arr,int *n,int newval, int index)
{
    int i;
    for(i= (*n);i>index;i--)
       arr[i]=arr[i-1];
    arr[i] = newval;
    (*n)++;    
}  
void read_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       printf("%d   ",arr[i]);
     }
     printf("\n");
}

int main()
{
    int arr[50];
    int newval,index; 
    int sz; 
    printf("Enter the size of array:"); 
    scanf("%d",&sz);
    read_array(arr,sz); 
    printf("Enter element to be inserted:");
    scanf("%d",&newval);
    printf("Enter the index of new element:");
    scanf("%d",&index);
    insert_element(arr,&sz,newval,index);    
    print_array(arr,sz);
    return 0;
}

10. Write a function to find the largest product of two elements of an array.

The simple but expensive method would be to take each element and multiply it by every other element and find the largest product.

A better way is, we can find two largest elements n1 and n2. And their product will certainly be largest product.

But what if there are two negative numbers whose prodcut is larger than the above product? Remember that product of two negative numbers is positive.

So let us also find two smallest numbers, and two largest numbers and find their products. Larger of maxproduct and minproduct is our required answer.

Using this method, array is traversed 4 times and time complexity is O(n) not O(n2)

#include<stdio.h>
int largest_product(int min1,int min2,int max1,int max2)
{
    if(min1*min2 >max1*max2)
        return min1*min2;
    else
        return max1*max2;
}
 void find_minimums(int *arr,int n,int *min,int *second_min)
{
    *min = arr[0];
    int i;
    for(i=0;i<n;i++)
        if(arr[i]<*min)
            *min = arr[i];

    *second_min = arr[0];
    for(i=0;i<n;i++)
        if(arr[i]>*second_min && arr[i]<*min)
           *second_min= arr[i];
}
void find_maximums(int *arr,int n,int *max,int *second_max)
{
    *max = arr[0];
    int i;
    for(i=0;i<n;i++)
        if(arr[i]>*max)
            *max = arr[i];

    *second_max = arr[0];
    for(i=0;i<n;i++)
        if(arr[i]>*second_max && arr[i]<*max)
           *second_max = arr[i];
}
void read_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       printf("%d   ",arr[i]);
     }
     printf("\n");
}
int main()
{
    int arr[50];
    int sz,k; 
    int max1,max2;
    int min1,min2;
    printf("Enter the size of array:"); 
    scanf("%d",&sz);
    read_array(arr,sz);
    find_maximums(arr, sz, &max1,&max2);
    find_minimums(arr, sz,&min1,&min2);
    int prod1 = largest_product(min1,min2,max1,max2);
    printf("Largest product of the array is %d\n",prod1);    
    return 0;
}

11. Given an array, arrange the elements in such a way that every alternate element is larger than its neighbors

Compare the element with its next element a[i] and a[i+1]

If the element is even and it is larger than next, swap the elements

Similarly if the element is odd and it is smaller than next element, swap the elements.

Repeat this from i =0 to n

 #include<stdio.h>
void swap(int *p1,int *p2)
{
   int temp = *p1;
   *p1 = *p2;
   *p2 = temp;
}
void rearrange(int *arr,int n)
{
    int i;
    for(i=0;i<n-1;i++)
    {
        if( (i%2 && arr[i]<arr[i+1])   ||
              (i%2==0 && arr[i]>arr[i+1]) )
               swap(&arr[i],&arr[i+1]);
    }
}
    
void print_arr(int *arr,int n)
{
   int i;
   for(i=0;i<n;i++)
      printf("%d  ",arr[i]);
}

int main()
{
   int arr[10];
   int i,j;
   for(i=0;i<10;i++)
     scanf("%d",&arr[i]);
   rearrange(arr,10);
   print_arr(arr,10);
}

12. Write a function to move all zeroes to the end of the array

Each 0 is pushed to the end of the array and the rest of elements are moved to left.

This process is repeated for all 0s.

We need to use a variable last which indicates the position of end of array excluding 0s. When a 0 is moved to end, last must be decremented so that loop is repeated from 0 to last

#include<stdio.h>  
void move_zeroes(int *arr,int n)
{
   int i;
   int last = n-1;
   i =last;/* last 0 in array*/
   while(i>=0)
   {
       if(arr[i]==0)
       { 
          int j;
          for(j=i+1;j<=last;j++)
              arr[j-1]=arr[j];
          arr[last--]=0;
       }
       i--;
   }
}
void read_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       printf("%d   ",arr[i]);
     }
     printf("\n");
}
int main()
{
    int arr[40];
    int n;
    printf("Enter size of array:");
    scanf("%d",&n);
    read_array(arr,n);
    move_zeroes(arr,n);
    printf("Now the array is ");
    print_array(arr,n);
}

13. Write a program to print all pythogorean triplets in a given array. A pythogorean triplet is a three number set so that sum of squares of two numbers is equal to square of third number. e.g. 3,4,5 12,5,13 6,8,10

This solution is from internet. Like most others are. :)

The array is first sorted. Now from last element, ith element at a time is taken and is set as c in the equation a2+b2=c2. Two indices l and r are taken as 0 and i-1. Now lth element and rth element are tested for pythogorean equation. If there is a match, loop is terminated.

If not, if arr[l]2 + arr[r]2 is larger than c2, r is decremented because sum is too large. If not (that is sum of squares is smaller than c squared), then l is incremented. This process is repeated as long as there l <r.

#include<stdio.h>  
 
void pythTriplets(int *arr,int n)
{
    int i=n-1;
    for(;i>=2;i--)
    {
       int a = arr[i];
       int l=0,r=i-1;
       int found = 0;
       while(l<r)
       {
            if(arr[l]*arr[l]+arr[r]*arr[r]==a*a)
            {
               found = 1;break;
            }
            if(arr[l]*arr[l]+arr[r]*arr[r] >a*a)
                   r--;
            else
                   l++;
       }
       if(found) 
           printf("%d %d %d \n",a,arr[l],arr[r]);
  }
}
void insSort(int *arr,int n)
{
   int j;
   for(j=1;j<n-1;j++)
      {
         int temp = arr[j];
         int i;
         for(i=j-1;i>=0 && arr[i]>temp;i--)
             arr[i+1]=arr[i];
         arr[i+1]=temp;
       }
}
void read_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       printf("%d   ",arr[i]);
     }
     printf("\n");
}
int main()
{
    int arr[40];
    int n;
    printf("Enter size of array:");
    scanf("%d",&n);
    read_array(arr,n);
    insSort(arr,n);
    pythTriplets(arr,n);    
}

14. What is an array? Describe its features.

An array is a data structure where values of same type are stored in consecutive memory locations.
Each array element has an index.
Indices start from 0.

Definition:
Array definition should specify type of elements and size of array.
e.g.
int arr[10];
char arr2[30];

It can also specify optional initialization.
int m[3] = {1,22,34};

Once defined size of an array can not be changed.

Because of consecutive storage, array elements can be represented using pointers.

int *ptr = arr;/*ptr points to arr[0]*/
ptr++;/* now ptr points to arr[1]*/

Advantage of array :
1) compact storage
2) random access
3) simple

Disadvantages
1) size can not be changed at run time
2) Removal or insertion of elements in the middle is difficult

Array Questions