Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.

Algorithm
1)This approach is similar to the problem “checking whether a pair exists in an array
with specific sum S”.
This is what we are going to do.Have a start and end pointer which intially points to
arr[0] and a variable currentSum=arr[0]
2)Now increase end pointer such that currentSum>S .Now we can try finding a subarray having
sum=S within this subarray ending with end pointer.
3)Now to adjust currentSum to S we need to increase the start pointer which in turn reduces
currentSum’s value.If currentSum becomes smaller than S you have to go back to step 2.
4)At one point of time currentSum might become S.if theres no subarray with such sum then
start will be eventually equal to end.
5)Now start your quest from new starting point start+1 and ending point end+1
Time complexity- O(n)

[gist https://gist.github.com/vishnujayvel/5869743 ]

 

Maximum sum in an contiguous subarray of given array

Provided an array containing positive and negative numbers our task is to find the sum of the maimum subarray

[gist https://gist.github.com/vishnujayvel/5866941]

sorting array of 1’s and 0’s in O(n)

keep left and right pointer.

increment left till you encounter 1 as you move along left pointer.(left to right)

Similarly decrement right till you encounter 0 as you move along right pointer.(right to left)

if left < right

swap the elements

and continue from the top if left pointer < right pointer

[gist https://gist.github.com/vishnujayvel/ad165150acce269c4690 ]

Removing duplicate elements in a string

This programs removes dulplicate elements in a string without using an additional array
//Time complexity O(n^2)
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
void removeDuplicate(char* str){
if(str==”)
return;
int pivot=1;
int len=strlen(str);
//i runs from 2nd element to last element because j runs from first element to pivot
//element and we need not compare same elements so i and j neve have same value at same time
for(int i=1;i<len;i++){
int j;
//make all elements before the pivot as unique

for(j=0;j<pivot;j++)
if(str[j]==str[i])
break;
if(j==pivot){
//if j==pivot (str to str+pivot) is a unique subarray where str[pivot]=str[i]

str[pivot]=str[i];
pivot++;
}

}
str[pivot]=”;

}
int main(){
char str[]=”asddfffafffafffafaffafaf”;
removeDuplicate(str);
cout<<str;

}