thiago.xth1
BAN USERMy solution has O(Nˆ2) time complexity and O(1) memory complexity for the worst case.
Furthermore this algorithm is optimized relatively to the output size. So, if a given instance have output O(N) the algorithm will works in O(N).
I think that are not a better solution then O(Nˆ2), because there are instances that the output is O(Nˆ2), like this following:
range: [1 3]
Vector: 1, 1, 1, 1, 1, 1
#include <vector>
#include <iostream>
using namespace std;
// time: O(Nˆ2)
// memory: O(1)
void find_interval(const vector<int> &v, int min_v, int max_v) {
int begin = 0;
int end = 0;
int curr_sum = 0;
for (end = 0; end < v.size(); end++) {
curr_sum += v[end];
// remove elements from beging
while (begin < end && curr_sum > max_v) {
curr_sum = v[begin];
begin++;
}
int ns = curr_sum;
int nb = begin;
while (ns >= min_v && ns <= max_v && nb <= end) {
cout<<nb<<" "<<end<<endl;
nb++;
ns = v[nb];
}
}
}

thiago.xth1
June 13, 2014 vector<int> build_wave(vector<int> v) {
sort(v.begin(), v.end());
int sz = v.size();
int num_up = sz / 2 + sz %2;
int num_down = sz / 2;
vector<int> n(sz);
// up values
for (int i = 0, k = 0; i < sz; i+= 2, k++) {
n[i] = v[k + sz/2];
}
// down values
for (int i = 1, k = 0; i < sz; i+= 2, k++) {
n[i] = v[k];
}
}

thiago.xth1
June 13, 2014 vector<int> build_wave(vector<int> v) {
sort(v.begin(), v.end());
int sz = v.size();
int num_up = sz / 2 + sz %2;
int num_down = sz / 2;
vector<int> n(sz);
// up values
for (int i = 0, k = 0; i < sz; i+= 2, k++) {
n[i] = v[k + sz/2];
}
// down values
for (int i = 1, k = 0; i < sz; i+= 2, k++) {
n[i] = v[k];
}
}

thiago.xth1
June 13, 2014 This a O(log(b)) algorithm... or O(k), where k is the number of bits necessary to represent b.
#include <stdio.h>
#define ll long long int
ll f(ll a, ll b) {
if (b == 0)
return 1;
if (b == 1)
return a;
ll ans = f(a,b/2) * f(a,b/2);
if (a%b == 1)
ans *= a;
return ans;
}

thiago.xth1
May 30, 2014 #include <stdio.h>
#define ll long long int
ll f(a,b) {
if (b == 0)
return 1;
if (b == 1)
return a;
ll ans = f(a,b/2) * f(a,b/2);
if (a%b == 1)
ans *= a;
return ans;
}

thiago.xth1
May 30, 2014 My intuitive algorithm:
vector<int> sum(vector<int> &a, vector<int> &b) {
int i, cary = 0;
int ap = a.size()  1;
int bp = b.size()  1;
int sz = 0;
//gets result size
while (ap >= 0  bp >= 0) {
int d = 0;
if (ap >= 0)
d += a[ap];
if (bp >= 0)
d += b[bp];
d += cary;
cary = d / 10;
d %= 10;
sz++;
}
//Compute the sum
vector<int> ans(sz);
while (sz > 0) {
int d = 0;
if (ap >= 0)
d += a[ap];
if (bp >= 0)
d += b[bp];
d += cary;
cary = d / 10;
d %= 10;
ans[sz] = d;
}
if (cary > 0)
ans[sz] = cary;
reverse(ans.begin(), ans.end());
return ans;
}
The time complexity: O(max(a,b))
 thiago.xth1 November 07, 2013JUST if there are knowing about end point or start point.
 thiago.xth1 November 06, 2013Another approach, If beyond source and destination info there are datetime info in tickets:
> Sort the tickets registers by increasing datetime
> Build the trip by sorted tickets.
typedef struct {
string source;
string dest;
string date_time; // well formed format
}Ticket;
bool cmp(Ticket t1, Ticket t2) {
if (t1.date_time < t2.date_time)
return true;
return false;
}
/* Input: T, tickets set
* Output: trip, sequence of cities in the trip
*/
void build_trip(vector<Ticket> &T, vector<string> &trip) {
sort(T.begin, T.end());
trip.push_back(T[0].source);
for (int i = 0; i < T.size(); i++) {
trip.push_back(T[i].dest);
}
}

thiago.xth1
November 05, 2013 Assuming that the all the travels was made by airplanes, I think it's possible build the following solution:
> Build a graph G: where each city visited is a vertex and there a edge between each pair of cities that are in a travel ticket. Obviously G is a directed graph.
> If the graph don't have cycles then is possible reconstruct the trip by a topological sort procedure.
> Otherwise, it's impossible reconstruct the certain path.
My solution by a BFS.
void doPath( vector<string> &path, map<string,string> &M, string s) {
if(s == "")
return;
doPath(path, M, M[s]);
path.push_back(s);
}
vector<string> find(string &orig, string &dest, HashTable dic) {
queue<string> Q;
map<string,string> M;
Q.push(orig);
M[orig] = "";
bool can = false;
while(Q.empty() == false) {
string top = Q.top();
Q.pop();
if(top == dest) {
can = true;
break;
}
for (int i = 0; i < top.size(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
string ss = top;
top[i] = c;
if(M.find(ss) == M.end()) {
Q.push(ss);
M[ss] = top;
}
}
}
}
vector<string> path;
if(can == false)
return path;
return doPath(path, M, dest);
}

thiago.xth1
May 30, 2013 This is my solution, with complexity O(n).
void sort(int v[], int n) {
int begin = 0;
int end = n  1;
int i;
for ( i = 0; i <= end; i++) {
if (v[i] == 1)
swap(v[begin++], v[i]);
else if (v[i] == 3) {
while(v[end] == 3 && end > i)
end;
swap(v[i], v[end]);
}
}
}

thiago.xth1
May 29, 2013 My solution for this problem. The complexity is O(N*N).
typedef struct Node{
Node *left, *right;
int val, id;
};
void ancestor(Node * parent, Node *node, int **arr, int n) {
if (node == NULL)
return;
int n_id = node>id;
if (parent != NULL) {
int p_id = parent>id;
for (int i = 0; i < n; i++) {
arr[i][n_id] = arr[i][p_id];
}
arr[p_id][n_id] = 1;
}
ancestor(node, node>left, arr, n);
ancestor(node, node>right, arr,n);
}

thiago.xth1
May 28, 2013 My solution is a binary search. I believe the complexity of this solution is O(logn)
#include <stdio.h>
#include <vector>
using namespace std;
int first_least(vector<int> &v, int key) {
int begin,end, m;
begin = 0; end = v.size();
int f_id = 1;
while (begin <= end) {
m = (begin + end) / 2;
if (v[m] > key)
end = m  1;
else if (v[m] < key)
begin = m + 1;
else {
f_id = m;
end = m  1;
}
}
return f_id;
}

thiago.xth1
May 28, 2013 @Jay, the nodes don't have indexes but have memory address. In my solution has a Hash Table to find repeated address in the list traversal .
 thiago.xth1 May 28, 2013This is my solution. I use a implicit HashTable.
Node * find_least(Node *root) {
HashTable H;
H.insert((int)root);
while (node != NULL) {
if (H.has(node>next)) {
break;
}
node = node>next;
}
return node;
}

thiago.xth1
May 28, 2013 I believe the complexity of my solution is O(N). In this code is used a hash function to avoid compare strings.
#include <string.h>
#include <stdio.h>
#include <ctype.h>
int val(char c) {
return tolower(c)  'a';
}
/* Compute hash of a string of size n
* Use base B and modulo M
*/
int hash(char *s, int n, int B, int M) {
int h = 0;
int p = 1;
for (int i = n  1; i >=0 ; i) {
int v = val(s[i]);
h += (v * p) % M; // v * B ^ (n  i  1)
h %= M;
p *= B; // p = B ^ (n  i  1) % M
p %= M;
}
return h;
}
/* Check if two strings are equal */
bool check(char *a, char *b, int m) {
for (int i = 0; i < m; i++)
if(a[i] != b[i])
return false;
return true;
}
/* This algorithm searches for a text substring that is equals
* a given pattern. This algorithm uses strings hash to avoid
* string comparations (This idea is similar a RabinKarp algorithm).
* For calculate the hash is necessary a base B (number of symbols in
* the alphabet) and a number M (preferably a prime number) to get
* modulo by M.
* Expected complexity of this algorithm is O(N).
*/
int _find(char *text, char *pattern, int B, int M) {
int i;
int m = strlen(pattern);
int n = strlen(text);
int hp = hash(pattern, m, B, M);
int ht = hash(text, m, B, M);
// bm = B^(m  1) % M
int bm = 1;
for (i = 0; i < m  1; i++) {
bm *= B;
bm %= M;
}
// Check if strings are equal, First case
if(hp == ht && check(text, pattern, m)) {
return 0;
}
for ( i = 1; i <= n  m; i++) {
/* Update the hash in constant time
* H(i) =(B *(H(i1)  text_(i1) * B^(m1))  text_(i + m 1) ) %M
*/
ht = B * (ht  (val(text[i  1]) * bm) % M) + val(text[i + m  1]);
ht %= M;
ht = (ht + M) % M;
// If hash's are equal, do check
if(hp == ht && check(text + i, pattern, m)) {
return i;
}
}
//Don't find pattern in text
return 1;
}
int find(char *t, char *p) {
return _find(t, p, 26, 2111);
}
int main() {
char t[100], p[100];
scanf("%s %s", t, p);
int r = find(t, p);
printf("Position of pattern in text : %d\n", r);
}

thiago.xth1
May 21, 2013 this is my solution:
void remove( char s[] ) {
int c = 0;
for (int i = 0; s[i]; i++) {
if(s[i] == 'b')
c++;
else if (s[i] == 'c' && i > 0 && s[i1] == 'a')
c+=2;
else
s[i  c] = s[i];
}
}

thiago.xth1
May 21, 2013 This is My solution. I believe this code works for both cases. For first case is necessary to use l = 0.
bool duplicate(vector<int> v, int k, int l) {
for (int i = 0; i < v.size(); i++) {
int lower = v[i+k]  l;
int upper = v[i+k] + l;
if (v[i] >= lower && v[i] <= upper) {
return true;
}
}
return false;
}

thiago.xth1
May 21, 2013 Unfortunately, your code doesn't work in many cases. For example:
1 2 3 4 5
For this case, your code don't make some subsets like {1,2,5}.
O(M*E), where M is sum of the sizes of all words and E is the number of differents letters. In general, E is constant (for english E = 26), so the complexity is O(M).
 thiago.xth1 March 14, 2013Create a vector V[], where V[e] contains the number of ocorrences letter e in the given set.
For each word s, compute a vector Ws[], where Ws[e] contains the number of repetitions of letter e in the word (compute size of the word too).
return the max size word s such that Ws[e] <= V[e], for all letters e.
Open Chat in New Window
Do this in 3 parts:
print the left outline (without the leaf element)
print the leafs
print the right outline
Complexity time and memory:
 thiago.xth1 June 18, 2014Let the number of node in the tree be N:
print_left: O(logn), Memory for recursive stack: O(logn)
print_right: O(logn), Memory for recursive stack: O(logn)
print_deafs: O(n), Memory for recursive stack: O(logn)
... then the general time and memory complexity is:
print_outline: O(n) and O(logn)