Given An Unsorted with lot of duplicates & having Special property with it that every concecutive pair has maximum difference of 1 & also given the 1st last element in array , WAP to Search An Element X Efficiently?

Example
1 2 1 2 3 2 3 4 5 4 6 7 6 7 8 ....10000
Given for all in i we have to search an element x(say 3) & return any index of it.


Data Structure Used: Array

Algorithm:(Done Will Post Soon)


Working Code:


Time Complexity O(logn) yes its logn ??
Space Complexity O(1)
Run Here

Knapsack Problem (Unbounded & 0/1)

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

In the following, we have n kinds of items, 1 through n. Each kind of item i has a value vi and a weight wi. We usually assume that all values and weights are nonnegative. To simplify the representation, we can also assume that the items are listed in increasing order of weight. The maximum weight that we can carry in the bag is W.
The most common formulation of the problem is the 0-1 knapsack problem, which restricts the number xi of copies of each kind of item to zero or one. Mathematically the 0-1-knapsack problem can be formulated as:

maximize sum(vi,xi) for i=0 to n

such that sum(wi*xi)<=W & x(0,1) The unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item. Of particular interest is the special case of the problem with these properties: it is a decision problem, it is a 0-1 problem, for each kind of item, the weight equals the value: wi = vi. Notice that in this special case, the problem is equivalent to this: given a set of nonnegative integers, does any subset of it add up to exactly W? Or, if negative weights are allowed and W is chosen to be zero, the problem is: given a set of integers, does any nonempty subset add up to exactly 0? This special case is called the subset sum problem. In the field of cryptography the term knapsack problem is often used to refer specifically to the subset sum problem.\ Dynamic Programming Solution: Unbounded knapsack problem If all weights () are nonnegative integers, the knapsack problem can be solved in pseudo-polynomial time using dynamic programming. The following describes a dynamic programming solution for the unbounded knapsack problem. To simplify things, assume all weights are strictly positive (wi > 0). We wish to maximize total value subject to the constraint that total weight is less than or equal to W. Then for each w ≤ W, define m[w] to be the maximum value that can be attained with total weight less than or equal to w. m[W] then is the solution to the problem.
Observe that m[w] has the following properties:

m[0]=0 (the sum of zero items, i.e., the summation of the empty set)
m[i]=max(m[w-1],vi+m[w-wi]) where wi<=w where vi is the value of the i-th kind of item. Here the maximum of the empty set is taken to be zero. Tabulating the results from m[0] up through m[W] gives the solution. Since the calculation of each m[w] involves examining n items, and there are W values of m[w] to calculate, the running time of the dynamic programming solution is O(nW). Dividing by their greatest common divisor is an obvious way to improve the running time. Working Code: import java.io.*; class knapsack10 { public static void main(String args[]) throws IOException { int capacity,n; BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println ("\n Enter the number of items u want to enter:"); n= Integer.parseInt(br.readLine()); float p[]=new float[n+1]; float x[]=new float[n+1]; int i,j,k,w; int WEIGHT[]=new int[n+1],PROFIT[]=new int[n+1]; WEIGHT[0]=0; PROFIT[0]=0; for(i=1;i<=n;i++) { System.out.println ("\n Enter the weight and profit of "+i+" : item "); WEIGHT[i]= Integer.parseInt(br.readLine()); PROFIT[i]= Integer.parseInt(br.readLine()); p[i]=0; x[i]=0; } System.out.println ("\n Enter the capacity of the knapsack : "); capacity = Integer.parseInt(br.readLine()); float c[][]=new float [n+1][capacity+1]; for(i=0;i<=n;i++) for(j=0;j<=capacity;j++) c[i][j] = 0; for(i=1;i<=n;i++) for(w=1;w<=capacity;w++) if(WEIGHT[i]<=w){ if ((PROFIT[i]+c[i-1][w-WEIGHT[i]])>c[i-1][w])
{
c[i][w] = PROFIT[i] + c[i-1][w-WEIGHT[i]];
p[i] = 1;
}
else
{
c[i][w]=c[i-1][w];
p[i] = 0;
}}
else
{
c[i][w]=c[i-1][w];
p[i] = 0;
}

float temp=0;
int t=0;
for(j=1;j<=capacity;j++)
{
temp = c[n-1][j]-c[n-1][j-1];
for(i=1;i if(temp==PROFIT[i])
t=i;
x[t] = 1;


}
for(j=0;j<=n;j++)
System.out.println (j+" "+x[j] );
System.out.println ("The profit obtained is "+c[n][capacity]);
}
}

The O(nW) complexity does not contradict the fact that the knapsack problem is NP-complete, since W, unlike n, is not polynomial in the length of the input to the problem. The length of the W input to the problem is proportional to the number of bits in W, logW, not to W itself.

Time Complexity O(NlogN) W<=logW
Space Complexity (N^2)

More Info.
www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf

2nd Knapsack 0/1 Problem(In Progress)

Constructing a Binary Search Tree from Post Order traversal Efficiently.

Data Structure: Array,Binary Search Tree


Algorithm & Approach
1.As we have given Postorder Traversal we know last value will be root insert it in BST as Root.
2.While Iterating Over Array for each element (from as last position Obvious) compare root value
from next value in array so if
a. it is greater then root then insert it into right subtree of root Avg (logn),Worst O(N)
b. if next value is less then root then insert it into left subtree of root
3.End


Working Code:

#include
#include

typedef struct Tnode {
int data;
struct Tnode *left;
struct Tnode *right;
} Tnode;

#include
#include


/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
Tnode * newNode(int data)
{
Tnode * node = (Tnode *)
malloc(sizeof(Tnode ));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}


Tnode *constructBSTfrompostorder(Tnode *root,int a[],int n)
{
int i=0;
Tnode *t=NULL;
for(i=n-1;i>=0;i--)
{
t=root;
if(root==NULL)
{
root=newNode(a[i]);
continue;
}
while(root!=NULL)
{
if(a[i]>root->data)
{
if(root->right==NULL)
{
root->right=newNode(a[i]);
break;
}
root=root->right;
}
else
{
if(root->left==NULL)
{
root->left=newNode(a[i]);
break;
}
root=root->left;
}
}
root=t;
}
return root;
}

void postorder(Tnode *root)
{
if(root==NULL)
return;
postorder(root->left);
postorder(root->right);
printf("%d,",root->data);
}

int main(int argc, char** argv) {

Tnode *root=NULL;

/*root = createtreenode(15);

root->left = createtreenode(7);
root->right = createtreenode(25);

root->left->left = createtreenode(3);
root->left->right = createtreenode(10);

root->right->left = NULL;
root->right->right = createtreenode(50);

root->left->right->left = createtreenode(8);
root->left->right->right = createtreenode(12);

root->left->right->left->left = NULL;
root->left->right->left->right = createtreenode(9);

root->left->right->right->left = createtreenode(11);
root->left->right->right->right = createtreenode(14);

root->right->right->left = createtreenode(30);
root->right->right->right = createtreenode(55);

root->right->right->right->left = createtreenode(52);
root->right->right->right->right = NULL;*/

//postorder(root);

int a[]={3,9,8,11,14,12,10,7,30,52,55,50,25,15};
root=constructBSTfrompostorder(root,a,14);
postorder(root);
return (EXIT_SUCCESS);
}


Time Complexity O(NlogN) but in worst case it will take o(N^2) Time if we have given postorder
of right skewed tree
Space Complexity O(1)
Run Here http://ideone.com/3KMy7

Longest Repeated SubString e.g. Maximum Length SubString

For instance, the longest repeated string in ``Ask not what your
country can do for you, but what you can do for your country'' is `` can do for you'', with `` your country'' a close
second place.

Suppose, though, that you had a chance to preprocess the body of text before performing searches. You could make a hash table (or search tree) to index every distinct word of the document, and store a list of every occurrence of
each word. Such an ``inverted index'' allows a program to look up a given word quickly. One can look up phrases by intersecting the lists of the words they contain, but this is subtle to implement and potentially slow. (Some web
search engines do, however, take exactly this approach.) We'll turn now to a powerful data structure and apply it to a small problem: given an input file of text, find the longest duplicated substring of characters in it. For instance, the longest repeated string in ``Ask not what your country can do for you, but what you can do for your country'' is `` can do for you'', with `` your country'' a close
second place. How would you write a program to solve this problem?

Data Structure :Suffix Array

Algorithm

This problem is reminiscent of the anagram problem that we saw in Section 2.4. If the input string is stored in c[0..n-1], then we could start by comparing every pair of substrings using pseudocode like this

maxlen = -1
for i = [0, n)
for j = (i, n)
if (thislen = comlen(&c[i], &c[j])) > maxlen
maxlen = thislen
maxi = i
maxj = j

The comlen function returns the length that its two parameter strings have in common, starting with their first
characters:

int comlen(char *p, char *q)
i = 0
while *p && (*p++ == *q++)
i++
return i

Because this algorithm looks at all pairs of substrings, it takes time proportional to n2, at least. We might be able to
speed it up by using a hash table to search for words in the phrases, but we'll instead take an entirely new approach.

Our program will process at most MAXN characters, which it stores in the array c:

#define MAXN 5000000
char c[MAXN], *a[MAXN];

We'll use a simple data structure known as a ``suffix array''; the structure has been used at least since the 1970's,
though the term was introduced in the 1990's. The structure is an array a of pointers to characters. As we read the
input, we initialize a so that each element points to the corresponding character in the input string:

while (ch = getchar()) != EOF
a[n] = &c[n]
c[n++] = ch
c[n] = 0

The final element of c contains a null character, which terminates all strings.
The element a[0] points to the entire string; the next element points to the suffix of the array beginning with the
second character, and so on. On the input string ``banana'', the array will represent these suffixes:

a[0]: banana
a[1]: anana
a[2]: nana
a[3]: ana
a[4]: na
a[5]: a

The pointers in the array a together point to every suffix in the string, hence the name ``suffix array''.If a long string occurs twice in the array c, it appears in two different suffixes. We will therefore sort the array to bring together equal suffixes (just as sorting brought together anagrams in Section 2.4). The ``banana'' array sorts to

a[0]: a
a[1]: ana
a[2]: anana
a[3]: banana
a[4]: na
a[5]: nana

We can then scan through this array comparing adjacent elements to find the longest repeated string, which in this case is ``ana''. We'll sort the suffix array with the qsort function: qsort(a, n, sizeof(char *), pstrcmp) The pstrcmp comparison function adds one level of indirection to the library strcmp function. This scan through the array uses the comlen function to count the number of letters that two adjacent words have in common:

for i = [0, n)
if comlen(a[i], a[i+1]) > maxlen
maxlen = comlen(a[i], a[i+1])
maxi = i
printf("%.*s\n", maxlen, a[maxi])
The printf statement uses the ``*'' precision to print maxlen characters of the string.

I ran the resulting program to find the longest repeated string in the 807,503 characters in Samuel Butler's
translation of Homer's Iliad. The program took 4.8 seconds to locate this string:
whose sake so many of the Achaeans have died at Troy, far from their homes? Go about at once among the
host, and speak fairly to them, man by man, that they draw not their ships into the sea.
The text first occurs when Juno suggests it to Minerva as an argument that might keep the Greeks (Achaeans) from
departing from Troy; it occurs shortly thereafter when Minerva repeats the argument verbatim to

Working Code:

#include
#include
#include
int pstrcmp(char **p, char **q)
{ return strcmp(*p, *q); }
int comlen(char *p, char *q)
{ int i = 0;
while (*p && (*p++ == *q++))
i++;
return i;
}
#define M 1
#define MAXN 5000000
char c[MAXN]="banana", *a[MAXN];
int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
while ((ch = getchar()) != EOF) {
a[n] = &c[n];
c[n++] = ch;
}
c[n] = 0;
qsort(a, n, sizeof(char *), pstrcmp);
for (i = 0; i < n-M; i++) if (comlen(a[i], a[i+M]) > maxlen) {
maxlen = comlen(a[i], a[i+M]);
maxi = i;
}
printf("%.*s\n", maxlen, a[maxi]);
return 0;
}

Time Complexity O(NLogN)
Space Comple4xity O(1)
Auxillary Space O(N)
Run Here https://ideone.com/IQK8g

Source Jhon Bentely Programming Pearls
http://www.cs.pitt.edu/~kirk/cs1501/Pruhs/Fall2006/Assignments/repeatedstrings/index.html


Follow Up:
How would you modify the program for finding duplicated strings to find the longest string that occurs more than M times?

#include
#include
#include
int pstrcmp(char **p, char **q)
{ return strcmp(*p, *q); }
int comlen(char *p, char *q)
{ int i = 0;
while (*p && (*p++ == *q++))
i++;
return i;
}
#define M 1
#define MAXN 5000000
char c[MAXN], *a[MAXN];
int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
while ((ch = getchar()) != EOF) {
a[n] = &c[n];
c[n++] = ch;
}
c[n] = 0;
qsort(a, n, sizeof(char *), pstrcmp);
for (i = 0; i < n-M; i++) if (comlen(a[i], a[i+M]) > maxlen) {
maxlen = comlen(a[i], a[i+M]);
maxi = i;
}
printf("%.*s\n", maxlen, a[maxi]);
return 0;
}

Here is good lecture on suffix tree http://www.youtube.com/watch?v=jXAHLqQthKw
Here you can try some of applications of suffix tree http://algs4.cs.princeton.edu/63suffix/

Largest Sum Contiguous Subarray

Problem Statement:Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Data Structure Used:Array

O(N^3) Algorithm

#include
#include
#include

#define MAXN 10000000
int n;
float x[MAXN];

void sprinkle() /* Fill x[n] with reals uniform on [-1,1] */
{ int i;
for (i = 0; i < n; i++) x[i] = 1 - 2*( (float) rand()/RAND_MAX); } float alg1() { int i, j, k; float sum, maxsofar = 0; for (i = 0; i < n; i++) for (j = i; j < n; j++) { sum = 0; for (k = i; k <= j; k++) sum += x[k]; if (sum > maxsofar)
maxsofar = sum;
}
return maxsofar;
}

O(N^2) Algorithm

float alg2()
{ int i, j;
float sum, maxsofar = 0;
for (i = 0; i < n; i++) { sum = 0; for (j = i; j < n; j++) { sum += x[j]; if (sum > maxsofar)
maxsofar = sum;
}
}
return maxsofar;
}

float cumvec[MAXN+1];

float alg2b()
{ int i, j;
float *cumarr, sum, maxsofar = 0;
cumarr = cumvec+1; /* to access cumarr[-1] */
cumarr[-1] = 0;
for (i = 0; i < n; i++) cumarr[i] = cumarr[i-1] + x[i]; for (i = 0; i < n; i++) { for (j = i; j < n; j++) { sum = cumarr[j] - cumarr[i-1]; if (sum > maxsofar)
maxsofar = sum;
}
}
return maxsofar;
}

/* MS VC++ has a max macro, and therefore a perf bug */

#ifdef max
#undef max
#endif


#define maxmac(a, b) ((a) > (b) ? (a) : (b) )

float maxfun(float a, float b)
{ return a > b ? a : b;
}

#define max(a, b) maxfun(a, b)

float recmax(int l, int u)
{ int i, m;
float lmax, rmax, sum;
if (l > u) /* zero elements */
return 0;
if (l == u) /* one element */
return max(0, x[l]);
m = (l+u) / 2;
/* find max crossing to left */
lmax = sum = 0;
for (i = m; i >= l; i--) {
sum += x[i];
if (sum > lmax)
lmax = sum;
}
/* find max crossing to right */
rmax = sum = 0;
for (i = m+1; i <= u; i++) { sum += x[i]; if (sum > rmax)
rmax = sum;
}
return max(lmax + rmax,
max(recmax(l, m), recmax(m+1, u)));
}

float alg3()
{ return recmax(0, n-1);
}

O(N) Algorihtm

Kadane’s Algorithm:

Initialize:
max_so_far = 0
max_ending_here = 0

Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far

Explanation:
Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far


float alg4()
{ int i;
float maxsofar = 0, maxendinghere = 0;
for (i = 0; i < n; i++) {
maxendinghere += x[i];
if (maxendinghere < 0)
maxendinghere = 0;
if (maxsofar < maxendinghere)
maxsofar = maxendinghere;
}
return maxsofar;
}

float alg4b()
{ int i;
float maxsofar = 0, maxendinghere = 0;
for (i = 0; i < n; i++) {
maxendinghere += x[i];
maxendinghere = maxmac(maxendinghere, 0);
maxsofar = maxmac(maxsofar, maxendinghere);
}
return maxsofar;
}

float alg4c()
{ int i;
float maxsofar = 0, maxendinghere = 0;
for (i = 0; i < n; i++) {
maxendinghere += x[i];
maxendinghere = maxfun(maxendinghere, 0);
maxsofar = maxfun(maxsofar, maxendinghere);
}
return maxsofar;
}

int main()
{ int algnum, start, clicks;
float thisans;

while (scanf("%d %d", &algnum, &n) != EOF) {
sprinkle();
start = clock();
thisans = -1;
switch (algnum) {
case 1: thisans = alg1(); break;
case 2: thisans = alg2(); break;
case 22: thisans = alg2b(); break;
case 3: thisans = alg3(); break;
case 4: thisans = alg4(); break;
case 42: thisans = alg4b(); break;
case 43: thisans = alg4c(); break;
default: break;
}
clicks = clock()-start;
printf("%d\t%d\t%f\t%d\t%f\n", algnum, n, thisans,
clicks, clicks / (float) CLOCKS_PER_SEC);
if (alg4() != thisans)
printf(" maxsum error: mismatch with alg4: %f\n", alg4());
}
return 0;
}

To print the sub array run here 
Time Complexity O(n)
Space Complexity O(1)
http://ideone.com/9yyf6J

Source Jon Bently Programming Pearls

Find the longest arithmetic series that can be formed by choosing a sub-collection (possibly the entire collection)..TC problem

An arithmetic series consists of a sequence of terms such that each term minus its immediate predecessor gives the same result. For example, the sequence 3,7,11,15 is the terms of the arithmetic series 3+7+11+15; each term minus its predecessor equals 4. (Of course there is no requirement on the first term since it has no predecessor.)

Given a collection of integers, we want to find the longest arithmetic series that can be formed by choosing a sub-collection (possibly the entire collection). Create a class ASeries that contains a method longest that is given a int[] values and returns the length of the longest arithmetic series that can be formed from values.

Definition

Class: ASeries
Method: longest
Parameters: int[]
Returns: int
Method signature:int longest(int[] values) (be sure your method is public)

Constraints
- values will contain between 2 and 50 elements inclusive.
- Each element of values will be between -1,000,000 and 1,000,000 inclusive.

Examples
0)



{3,8,4,5,6,2,2}

Returns: 5

No arithmetic series using these values is longer than 2,3,4,5,6.
1)



{-1,-5,1,3}

Returns: 3

-1, 1, 3 is an arithmetic series (so is 3,-1,-5).
2)



{-10,-20,-10,-10}

Returns: 3

-10,-10,-10 is an arithmetic series.

I Took The Problem From My Friend Rizwan's Blog (he is Kind oF Computer Geek) :)
he told that success rate of this problem is about 52% so that makes me crazy to,solve it.

first let me try myself thinking how i can approach

Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it

i.e find a sequence i1 < i2 < … < ik, such that
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible.
The sequence S1, S2, …, Sk is called an arithmetic progression if
Sj+1 – Sj is a constant

http://theory.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf

Given an array and find two numbers in the array having difference equal to given number

Data Structure:Array

Algorithm:
1.start using two pointer p1 & p2 which pints 1st & next element repectively
2.initialize p1=0 & p2=1;
3.loop down over array
a.check if their difference a[p2]-a[p1]==num if yes the print then & increment
both p1 & p2;
b.else if their difference a[p2]-a[p1]>num is less then number then increment j
only.
c.else if their difference a[p2]-a[p1]

int main()
{
int arr[9]={10, 14, 17, 22, 23, 25, 26, 27, 45};
int i = 0;
int j = 1;
int num = 2;
while(j<9) { if(arr[j] - arr[i] == num) { printf("two numbers whose difference is equal to num are %d %d",arr[i],arr[j]); i++;j++; } else if((arr[j]-arr[i])>num)
i++;
else if((arr[j]-arr[i]) j++;
}
}

Suggested by Rajcools
Time Complexity O(N)
Space complexity O(1)
Run Here https://ideone.com/zbdDh

Wap to Count Number of Set Bits in Hexadecimal Number

class Solution { public int hex_bitcount(String S); }

that given a string S containing big-endian hexadecimal representation of a non-negative integer N returns the number of bits set to 1 in binary representation of N.

Assume that the length of the string does not exceed 100,000. Assume that the string contains only characters '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'.

For example the function should return 5 when given S = "2F". The string "2F" represents the number 47. The binary representation of 47 is 101111 and it contains 5 bits set to 1.

Algorithm Used: Brian Kernighan’s Algorithm:
Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.
Beauty of the this solution is number of times it loops is equal to the number of set bits in a given integer.

1 Initialize count: = 0
2 If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
3 Else return count


class Solution
{
int hex_bitcount ( String S )
{
int n=0,count=0;
if(S.length()<=100000)
{
n=Integer.parseInt(S,16);

while (n!=0)
{
n &= (n-1) ;
count++;
}
return count;
}
return -1;
}
public static void main(String a[])
{
Solution obj= new Solution();
System.out.println(obj.hex_bitcount("2F"));

}
}

Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/9vZ4V

implement Bit operation for setting & re-setting the bit in range & at ith position

Operations are
Set(i) sets the ith bit O(1)
Unset(j) unsets the jth bit Set(i,j) O(1)
sets the bits b/w i and j Unset(i,j) o(logn)..??
unsets the bits b/w i and j O(logn) ???
Design a data structure for this problem with minimum time and space complexity.

#include
int set(int N,int i){
N = N | (1<=j;k--){
N = set(N,k);
}
return N;
}

int main(){

int N=7;
int i=3,j=2;
N=set(N,i);
printf("%d\n",N);

N=unset(N,j);
printf("%d\n",N);
N=set_range(0,3,1);
printf("%d\n",N);
/*unset(N,i,j);*/
return 0;
}

Time Complexity O(n)
Space Complexity O(1)

Optmization O(logn)
Yes we can use RMQ mechenism to do this , Segment Tree is Awesome Option to set upper bound for set(i,j,) & unset(i,j) will be O(logn)