atuljangra66
BAN USERI guess the normal recursion, with two variable for allowed min and max would be sufficient for this question.
Following is the fully working code for the same.
#include <iostream>
#define INT_MAX 100000
#define INT_MIN -1
using namespace std;
class Node {
public:
int val;
Node * left;
Node * right;
Node() {val = -1; left = right = NULL; }
Node(int x) {val = x; left = right = NULL; }
~Node() {
delete left; delete right;
}
};
bool isBST(Node * root, int max, int min) {
if(root == NULL) {
// cout << "null, returning true \n";
return true;
}
cout << "At " << root ->val << endl;
bool condition = (root -> left)? (root -> left -> val < root -> val) : true;
condition = condition && ((root -> right) ? (root -> right -> val > root -> val): true);
condition = condition && (root -> val < max && root -> val > min);
if(condition == false) {
// cout << "condition not met at " << root -> val << endl;
return false;
}
return condition &&
(isBST(root -> left, root -> val, min)) &&
(isBST(root -> right, max, root -> val));
}
int main () {
// Construction a Binary tree;
Node * a = new Node(10);
Node * b = new Node(5);
Node * c = new Node(20);
Node * d = new Node(1);
Node * e = new Node(9);
Node * f = new Node(15);
Node * g = new Node(12);
Node * h = new Node(17);
Node * i = new Node(25);
a -> left = b;
a -> right = c;
b -> left = d;
b -> right = e;
c -> left = f;
f -> left = g;
f -> right = h;
c -> right = i;
cout << isBST(a, INT_MAX, INT_MIN) << "\n";
delete a;
return 0;
}
Won't the following be good?
for(i=0;i<n;i++)
{
Complement=K-a[i];
HashTable[a[i]]=i;
Index = SearchHashTable(Complement);
if(Index!=-1 && Index != i)
cout<<"Indices:\t"<<HashTable[Complement]<<"\t"<<i<<endl;
}
Change
if(!dekha[*i])
getAllPaths(*i, dest, level + 1);
to
if(!visited[*i])
getAllPaths(*i, dest, level + 1);
Since we need to consider all the simple paths, I propose the following algorithm:
Do a normal dfs(or bfs) rooted at the src node. We keep a visited array to track that we do not run into loops. When we have found the destination at some point in the traversal, we return from that search branch. At the end of the recursive call, we mark the node as un-visited, so that we can explore other paths which may emerge from this node. Also to track the uniqueness of the nodes visited, we add all the nodes on a particular path in a set(set have the property of storing only unique elements).
I think that we can do better in space complexity.
Sample code is as follows, I've tested it for small inputs:
// A private member of Graph class
set <int> uniqueVisited;
// Method of Class
void Graph::AddPath(int l) {
for(int i = 0; i < l; ++i) {
cout << path[i] << " ";
uniqueVisited.insert(path[i]);
}
cout << endl;
}
void Graph::getAllPaths(int s, int dest, int level) {
path[level] = s;
if (s == dest) {
AddPath(level + 1);
return;
}
visited[s] = true;
list <int> :: iterator i;
for (i = adj[s].begin(); i != adj[s].end(); ++i) {
if(!dekha[*i])
getAllPaths(*i, dest, level + 1);
}
visited[s] = false;
}
// Method to print the set
void Graph::printSet()
{
set<int>::iterator it;
cout << "Set is";
for (it = uniqueVisited.begin(); it != uniqueVisited.end(); ++it)
cout << " " << *it;
cout << endl;
}
Ignore the redundant 3 variables at the top.
- atuljangra66 September 23, 2013Simple binary search, with slight change will work.
See the code below.
// Aim is to find a element k in a rotated sorted array.
#include <iostream>
using namespace std;
int findKElement(int find, int array[], int length)
{
int start = array[0];
int end = array[length -1];
int mid = array[length/2];
int left = 0;
int right = length - 1;
while (left <= right) {
int middle = left + (right-left)/2;
if (array[middle] == find) return middle;
if (array[left] <= array[middle]) {
if (find >= array[left] && find < array[middle])
right = middle - 1;
else
left = middle + 1;
}
else {
if (find > array[middle] && find <= array[right])
left = middle + 1;
else
right = middle - 1;
}
}
return -1;
}
int main ()
{
int length;
cin >> length;
int array[length];
int toFind;
cin >> toFind;
for (int i = 0; i < length; i++)
cin >> array[i];
cout << "index is " << findKElement(toFind, array, length) << endl;
return 0;
}
@gudujarlson, You cannot convert
1,-1
1,2
into two arrays with same average. That's what Erasmus is saying.
This is a standard DP problem. Trick is to keep track of min and max of the subarray ending at i in the array indices 0 to i. While calculating the min or max, we also need to examine max or min respetively.
I'll post the code in a couple of hours.
Algorithm will be O(n)
You can see kadane's algorithm for the case of Sum. Product is just more refined problem, which uses the same algorithm.
a = {1,2,3,6,2,8}
{{ F[2] = 1 * 2 }} You made a mistake at this step.
B[2] = 6 * 2 * 8
b[2] = 1 * 2 * 6 * 2 * 8
192 = 192
Plus the complexity is O(num_of_nodes).
- atuljangra66 October 29, 2013