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];
}
}
}
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];
}
}
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];
}
}
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;
}
#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;
}
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 date-time info in tickets:
-> Sort the tickets registers by increasing date-time
-> 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);
}
}
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);
}
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]);
}
}
}
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);
}
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;
}
@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;
}
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 Rabin-Karp 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(i-1) - text_(i-1) * B^(m-1)) - 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);
}
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[i-1] == 'a')
c+=2;
else
s[i - c] = s[i];
}
}
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;
}
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.
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)