Largest Contiguous Sum of Sub Array

Today's Post is about finding the Largest Contiguous Sum of A sub Array.

The Approach which i will use is called KADANE'S ALGORITHM

The very simple yet intuitive and efficient Kadane's algorithm works as follows:

Keep adding all the elements of array and keep the track of two things first whether the sum we are adding is positive or not,if its negative then again initialize it to zero. Second whether the sum calculated so is the biggest/largest of all or not.

Here's the code :

#include<stdio.h>

void findsum(int arr[],int n)
{
    int i=0,max_so_far=0,max_ending_here=0;

    for(i-0;i<n;i++)
    {
     max_ending_here=max_ending_here+arr[i];
     if(max_ending_here<0)
        max_ending_here=0;
     if(max_ending_here>max_so_far)
     max_so_far=max_ending_here;

    }
    printf("%d",max_so_far);
}

int main()
{
    int arr[]= {-2, -3, 4, -1, -2, 1, 5, -3};
    int n=sizeof(arr)/sizeof(arr[0]);
    findsum(arr,n);
    return 0;
}

Viva La Raza

Sid

Finding Minimum Element In sorted Rotated Array

In Today's Post we will discuss a program whose objective is to find a minimum element in an array but what's the fun in doing that.... so the twist is that the array is rotated.

Approach:

The Approach is similar to binary search with some extra conditions to check whether the array is left rotated, right rotated or not rotated at all.

the above mentioned things can be done in O(log n) time but for handling duplicates an extra condition need to be added which extends the time complexity of the program to O(n).

Here's the code:

#include<stdio.h>

int min(int x,int y)

{

 return (x>y)? y : x ;

}

int findmin(int arr[],int low,int high)

{

    if(high<low)

    return arr[0];

    if(low==high)

        return arr[low];

    int mid=low+(high-low)/2;

    if(mid<high && arr[mid+1]<arr[mid])

        return arr[mid+1];

    if(arr[mid]==arr[low]&&arr[mid]==arr[high])

        return min(findmin(arr,low,mid-1),findmin(arr,mid+1,high));

    if(low<mid && arr[mid-1]>arr[mid])

        return arr[mid];

    if(arr[mid]<arr[high])

        return findmin(arr,low,mid-1);

    return findmin(arr,mid+1,high);

}

int main()

{

    int arr[] =  {3, 3, 3, 4, 4, 4, 4, 5, 3, 3};

    int n=sizeof(arr)/sizeof(arr[0]);

    int k=findmin(arr,0,n-1);

    printf("%d",k);

    return 0;

}

Do comment.. :)

Viva La Raza

Sid

C Program To Move All Zeros To the End Of the Array

This is a simple program so let's code it.

#include<stdio.h>

void moveToEnd(int arr[],int n)
{
 int pos=0,i=0;

 while(i<n)
 {
     if(arr[i]!=0)
     arr[pos++]=arr[i++];
     else
        i++;
 }
     while(pos<n)
        arr[pos++]=0;
}

int main()
{
    int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
    int n,i;
    n=sizeof(arr)/sizeof(arr[0]);
    moveToEnd(arr,n);
    for(i=0;i<n;i++)
        printf(" %d",arr[i]);
    return 0;
}

Count all pairs with a given difference

Today's post is sort of an extension of previous post.

Here We will discuss approaches to count all distinct pairs with a given difference k.

Example to understand the question better:

Input: arr[] = {1, 5, 3, 4, 2}, k = 3
Output: 2
There are 2 pairs with difference 3, the pairs are {1, 4} and {5, 2}

The algorithm is similar to the previous one only so, i will carry forward to the code. :)

Few points relating to aforementioned code:

1. The sorting can be done in nlog n time complexity.

2, Instead of binary search HASHING can also be used to find elements but time complexity will remain  O(n logn).

3, AVL Trees can also be used to counter this problem. Instead of sorting the elements an AVL tree can be made and maintained and for each element arr[i]+k can be searched in O(log n) time.But the overall time complexity will still remain O(n logn).

#include<stdio.h>
#include<stdlib.h>

int compare(const void* a,const void* b)
{
return (*(int*)a - *(int*)b);
}

int binarySearch(int arr[],int low,int high,int k)
{
    int mid= low+((high-low)/2);
    if(high>=low)
    {

    if(arr[mid]==k)
        return mid;
    if(arr[mid]>k)
        return binarySearch(arr,low,mid-1,k);
    if(arr[mid]<k)
        return binarySearch(arr,mid+1,high,k);
    }
    return -1;
}
void countPairs(int arr[], int n,int k)
{
    int i=0,pairs=0;
    qsort(arr,n,sizeof(int),compare); //for sorting the elements of the array
    for(i=0;i<n;i++)
       {
           if(binarySearch(arr,i+1,n-1,arr[i]+k)!=-1)
            pairs++;
       }

printf("No. of distinct pairs with difference as %d are %d",k,pairs);


}
int main()
{
    int arr[]= {1, 5, 3, 4, 2};
    int k=3;
    int n=sizeof(arr)/sizeof(arr[0]);
    countPairs(arr,n,k);
    return 0;

}

Comments and suggestions are welcome..:)

Viva La Raza

Sid

Find a Pair with a given difference k

Happy new year Everyone.. :) Lets start coding..

Today's post is all about finding a pair of numbers in a given unsorted array, which has a difference k.

The simplest approach can be to run two loops.The Outer loops picks each element one by one and run an inner loop to compare it with each element and find if the difference between them is k.
Complexity: O(n^2)

Can we improve it... Yes.

Algorithm#1:

1. The array can be first sorted.  // complexity n logn
2. Binary search can be implemented for each element to find arr[i]+k in [i+1...n-1]. //complexity n log n

Complexity: O(n logn)

can we improve further ..Yes..

The second step can be improved to O(n). Lets see the approach.

Maintain two variables i=0 and j=1, initialize them respectively  Calculate their difference, if the diff is less than k, then increment j else increment i, till we get the exact difference or we run out of numbers.... :)

Simple yet intuitive approach..
Lets code it..

#include<stdio.h>

void findPair(int arr[],int n,int k)
{
    int i=0,j=1;

    while(i<n && j<n)
    {
        if(i!=j && arr[i]-arr[j]==k || arr[j]-arr[i]==k)
        {
            printf("Pair found %d %d",arr[i],arr[j]);
            //i++;
            return;
        }

        if(arr[j]-arr[i] > k)
            i++;
        else if(arr[j]-arr[i] < k)
            j++;

    }
    printf("No pair found");
}
int main()
{
    int arr[] = {1, 8, 30, 40, 100,160};
    int k=60,n;
    n=sizeof(arr)/sizeof(arr[0]);
    findPair(arr,n,k);
    return 0;
}

Comments and suggestions are welcome.. :)

Viva La Raza

Sid