ninhnnsoc
BAN USER
I forget to mention that, push/pop from left/right of deque are O(1) time operations, thus the algorithm is O(N) time.
The idea of deque is just an abstraction, we can implement it in different ways. For example, it can be implemented as a doubly linked list.
For java ArrayList:
If RemoveAt(0) is O(K) time, then it's not good. Imagine the case when K = N/2, and numbers are sorted in decreasing order. This case will take O(N.K), which is O(N^2) time.
@zr.roman: Thanks for looking into it!
If we look more carefully with the while loop, we will see that it's not always run in O(K) time.
Analyse by this way will give a tighter bound O(N):
Each element of the array is scanned once. It is added into the deque at most once. And it is removed at most once. So, altogether, the algorithms will take O(N) time.
This is amortized/aggregate analysis.
Here is the working code in python:
A = [8, 5, 10, 7, 9, 4, 15, 12, 90, 13]
A = [9,8,7,6,5,4,3,2,1,0]
N = len(A)
K = 4
from collections import deque
DQ = deque() # store the index of numbers within the window of size K
RES = []
for i in xrange(N):
print i, A[i], DQ, RES
while len(DQ)>0 and A[DQ[-1]] <= A[i]: # Once a new max is encountered, all previous max are useless, thus need to remove
DQ.pop()
while len(DQ)>0 and DQ[0] <= i-K: # Remove index outside the K-window
DQ.popleft()
DQ.append(i)
if i>=K-1:
RES.append(A[DQ[0]])
print RES
#[10, 10, 10, 15, 15, 90, 90]
This runs in O(N) time because each element is added and removed from the deque at most once.
EDITED: fixed the bug, after zr.roman's comment.
Using Deque can solve this problem in O(N) time
deque is a queue that can be pushed/popped from both ends. We use a deque DQ to store the elements for the sliding K-window. The trick is that, we only store the elements that are potentially be the maximum of future K-windows. So, if we see a number x that is greater than all elements in the current deque, we know for sure that x now will be the max, and all those elements in current deque will never be the max again. Thus, they must be removed, replacing by x.
Example:
A = [8, 5, 10, 7,9, 4, 1, 1, 1…]
We see 8: nothing to compare
When we see 5: we know that when 8 is out of the future K-window, 5 can potentially be the max of that window. We need to store 5
When we see 10: we know that 8, 5 can never be the max for future K-window. Thus, 8,5 should be removed. The deque now contains only 10
When we see 7: 7 can potentially be the max when 10 is out. Store 7, deque becomes [10, 7]
When we see 9: 7 won’t be the max anymore, remove 7. Store 9, deque becomes [10,9]
And so on..
EDITED: I explained it here:
capacode. com/?p=1042
Be careful if the array doesn't have majority element.
If it doesn't guarantee to have the majority element (>n/2 time), we need to check more positions: k*n/4, k=0..4, to make sure the majority segment cross 2 of our land-marks.
If it guarantees to have majority element, just check middle element is enough.
The key point that makes O(1) time& space possible is that the array is sorted.
The idea is, if the element that repeated >n/2 time (half-major element), they must be next to each other in the array. And they must cross some "land-mark", that is the middle of the array.
So, checking the middle element A[n/2], comparing it with A[0] and/or A[n] can tell whether it's major element. EDITED: A[n/2] must be the answer given if half-majority exists.
For the case of majority > n/4 (quarter-majority): Same idea, however we need more "land-marks". I believe checking position k*n/8 for k = 0..8 will sufficient to check for the majority element.
For the case array is NOT sorted, I think O(1) time is not possible. However, O(n) time, O(1) space algorithm exists. Check this post about majority elements: capacode. com/array/major-element-in-array/ Thanks!
EDITED for the case n/4-majority:
- Check if there is a repeated segment S crosses at least 2 landmarks.
- If S crosses 3 landmarks or more: length of S must be >n/4, found S, done.
- If S crosses only 2 landmarks u and u+1:
Reduce the problem into the case "half-majority" with array from landmark u-1 to landmark u+2.
Suppose we need to build a balanced binary search tree T for the elements in sorted array A, from index "lo" to "hi".
build(A, lo, hi):
The root of T must be the middle element: T.root = A[mid], where mid = (lo+hi)/2
The left subtree of T must be built from A[lo, mid), recursively:
T.left = build(A, lo, mid-1)
The right subtree of T must be built from A[mid+1, hi), recursively:
T.right = build(A, mid+1, hi)
Remember the basecase is when hi-lo <=1.
Complexity:
Since each element of the array A is accessed once, the complexity is O(N), N = length of array A.
(k+1)*a + k(k+1)/2 = N
N = (k+1)(a + k/2)
2N = (k+1)(2a+k)
Then, for N not-too-big, we can use integer factorization to find all pairs (a,k).
Just find all pairs (u,v) that u*v = 2N, considering all positive and negative divisors, then k = u-1, a = (v-k)/2. Of course, v-k must be even, otherwise ignore them.
If a, k are integers, then N must be integer.
If N real, a must be real. But then for any k we can find a. Thus there's not finite #solutions.
Answer: 3,614,000,181,007,876
This C++ code will run in few seconds to get the answer (3 seconds on my i7 PC):
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
//Shortcuts for laziness:
#define FOR(i,s,e) for(int (i) = (s); (i) < (e); ++(i))
#define REP(i,n) FOR(i,0,n)
#define lli long long int
const int MILLION = 1000010;
bool Sieve[MILLION];
vector<int> Primes; // list of primes less than 1M;
int N; // number of primes less than 1M;
void sieve(){
int n = sqrt(MILLION) +1 ;
REP(i, MILLION) Sieve[i] = true;
Sieve[0] = Sieve[1] = false;
FOR(i,2,n) if (Sieve[i])
for(int j = i*i; j< MILLION; j+=i)
Sieve[j] = false;
FOR(i,2,MILLION)
if (Sieve[i]) Primes.push_back(i);
N = Primes.size();
//FOR(i,2, 100) cout <<Primes[i] % 6<< " "; cout<<endl;
return;
};
bool is_Prime(lli x){
REP(i, N) if (x % Primes[i] == 0) return false;
return true;
}
int main()
{
sieve();
lli sum = 0;
lli LO = 1000000000000;
lli HI = 1000000100000;
lli k0 = LO/6;
lli x = 6*k0+1;
while(x<HI-6){
if (is_Prime(x)) sum+= x;
x+=4;
if (is_Prime(x)) sum+= x;
x+=2;
}
cout <<sum<<endl;
return 0;
}
Great solution!
I have same idea.
Below is my implementation in C++, using doubly linked list.
Interesting Java has LinkedHashSet data structure. I don't know whether C++ has the alternative or not.
#include <iostream>
#include <map> // use unordered_map for hashing in O(1)
using namespace std;
struct Node{
char item;
Node * next;
Node * prev;
};
class List{ // doubly linked list
private:
Node * _head;
Node * _tail;
public:
List(){
_head = NULL;
_tail = NULL;
};
~List(){};
//insert a new node to the tail of the list:
Node * insert(char newItem){
Node *x = new Node;
x->item = newItem;
x->next = NULL;
x->prev = NULL;
//first element:
if (NULL == _head){
_head = x;
_tail = x;
return _head;
};
//not first:
_tail->next = x;
x->prev = _tail;
_tail = _tail->next;
return x;
};
//remove a node pointed by x. Precondition: x must be in the list!
void remove (Node *x){
if (x == _head){
if (x == _tail){
_head = NULL;
_tail = NULL;
delete x; x = NULL;
return;
};
_head = x -> next;
_head -> prev = NULL;
x->next = NULL; x->prev = NULL;
delete x; x = NULL;
return;
};
if (x == _tail){ // x != _head
_tail = x -> prev;
_tail->next = NULL;
x->next = NULL; x->prev = NULL;
delete x; x = NULL;
return;
};
// x in the middle:
x->prev->next = x->next;
x->next->prev = x->prev;
x->next = NULL; x->prev = NULL;
delete x; x = NULL;
return;
};
char getHead(){
if (_head) return _head->item;
else return 0;
};
void clear(){
_head = NULL;
_tail = NULL;
};
};
List myDLL;
map<char, Node *> myHash;
map<char, int> Counter;
int main()
{
myDLL.clear();
string S = "gaabfcacbdegdfehhoto";
for(int i = 0; i<S.length(); i++){
if (Counter.count(S[i]) < 1){ // not in the Counter
Node *x = myDLL.insert(S[i]);
myHash[S[i]] = x;
}else
if (Counter[S[i]] ==1){
Node *x = myHash[S[i]];
myDLL.remove(x);
myHash[S[i]] = NULL;
};
Counter[S[i]]++;
};
char c = myDLL.getHead();
cout <<"First unique character is: ";
if (c and (Counter[c]==1)) cout <<c<<endl;
else cout <<" No unique char!"<<endl;
return 0;
}
This problem is hard for big N. For small N, it can be fast.
Statistics of my simple program:
N = 14: 5.180 ways
N = 15: 32.516 ways
N = 16: 202.900 ways
N = 17: 1.330.622 ways (26 seconds without printing)
N = 18: 8.924.976 ways (190 seconds without printing)
EDIT: Brief explanation:
- Always place the k-th queen at the k-th column;
- If you put a queen at k-th column and i-th row: mark row[i] not-safe, mark the 2 diagonals crossed at square (k,i) not-safe.
- In k-th column: try all "safe" positions. Position i is safe if: row[i], diag1[k+i], diag2[k-i] are safe, and square (k,i) is not knight-move reachable from (k-1)th and (k-2)th already-placed queens.
Note that queens (k-3)th and k-th are never knight-move reachable, since the column distance is 3 already.
My program is a simple backtrack:
#include <iostream>
#include <cmath> //abs()
using namespace std;
const int Nmax = 20;
bool row[Nmax], col[Nmax], diag1[2*Nmax], diag2[2*Nmax];
int N;
long long nSolutions = 0;
int Queens[Nmax];
void init(){
for(int i=0; i < Nmax; i++) row[i] = col[i] = true;
for(int i=0; i < Nmax;i++)
for(int j=0; j < Nmax;j++)
diag1[i+j] = diag2[Nmax+i-j] = true;
}
void putAQueen(int k){ // always put k-th queen at column[k];
if (k >= N){
nSolutions++;
// /* // Printing queens' placement:
cout <<"Way #"<<nSolutions<<endl;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(j!=Queens[i]) cout <<"+";
else cout<<"Q";
};
cout<<endl;
}
cout<<endl;
//*/
}
else{
for(int i=0; i < N;i++)
if (row[i] and diag1[i+k] and diag2[Nmax + i-k]) // normal queen
if (k==0 or (k==1 and abs(Queens[k-1]-i) !=2 ) or
(k>=2 and (abs(Queens[k-1]-i) !=2) and (abs(Queens[k-2]-i) !=1))){ // knight move check
row[i] = false;
diag1[i+k] = false;
diag2[Nmax+i-k] = false;
Queens[k] = i;
putAQueen(k+1);
row[i] = true;
diag1[i+k] = true;
diag2[Nmax+i-k] = true;
}
}
};
int main()
{
init();
N = 16; // N =15: 32.516 ways; N=14: 5.180; N =16: 202.900
N = 17; // N =17: 1.330.622 ways (26 seconds without printing)
N = 18; // N =18: 8.924.976 ways (190 seconds without printing)
N = 10;
putAQueen(0);
cout << nSolutions << endl;
return 0;
}
For explanation of how it works,
you can check this post: capacode.com/?p=682
@demo: N can be big, but the frequency is less than N.
Use hash to compute frequency first. Then use counting sort on frequency.
Counting sort sorts the frequencies of the items, not the value of items. Thus, it takes O(N+maxFreq) time and space.
Note: we can't do better than linear time O(N), since we need to check for each and every item.
Let minBefore(i) = minimum number in the range from [0, i-1].
This array can be computed in O(N) time.
The answer is maxDiff = max(A[i] - minBefore[i]), which can be computed in O(N) time.
This algorithm can be implemented with O(1) space, and use 1 array scanning.
My one is backtracking algorithm. It should work very fast.
N 23412367188, result: 13272317
N=93512378880, result: 23452182
N=615954598560, result: 13579246
N=559999999440, result: 12345679
#include <iostream>
#include <set>
using namespace std;
set<int> Result;
set<int>::iterator it;
long long N;
void init(){
Result.clear();
};
bool check(long long N, long long P){
long long myP = 1;
while(N > 0){
myP *= N%10;
N = N/10;
};
return (P == myP);
}
void findSeed(long long N, long long P){
//basecases:
if (P > N) return;
if (check(N,P)){
Result.insert(N);
return;
}
//recursive:
for(int d = 9; d >= 2 ; d--)
if (0==N%d){
findSeed(N/d, P*d);
};
}
int main()
{
N = 23412367188; // result: 13272317
init();
if (N<10) cout <<N<<endl;
else findSeed(N,1);
if (Result.size()){
cout <<N<<": ";
for(it= Result.begin(); it!= Result.end(); ++it)
cout <<*it<<" ";
cout <<endl;
}
return 0;
}
Hi guys:
When you have a list of pairs <item, freq>, the freq is an integer with value at most N.
So, you can sort the list based on freq, using counting sort, with time complexity of O(N+max Frequency).
Pseudo code for sorting the list of pairs <item, freq> is following:
Input: List[]
//counting/distributing:
for i = 1..N
f = List[i].freq;
maxF = max(maxF, f);
Counter[f].push_back(i); // put the index i into the counter f
//collecting:
for f = 1..maxF // for each freq f in increasing order from 1 to maxF
S = Counter[f].size()
for j = 0..S-1
index = Counter[f][j];
NewList.push_back(List[index]); // collect back the items in increasing order of freq
return NewList; //Note: this counting sort is not stable. To make it stable, one more array is needed.
//Complexity: O(N) space, O(N+maxF) time
Radix sort works almost the same, except that it works on each digit/character separately, from the least significant position to the most significant position.
(Each iteration of radix sort is a counting sort)
--ninhnn
Use a hash to count frequency of each unique number, store them in pairs like (unique_num, frequency).
Then sort the item-frequency pair list, in order of decreasing the frequency, using counting sort.
Complexity:
O(N) time for hashing + O(N+ maxFrequency) time for sorting. Note maxFrequency is <= N.
O(N) space for hashing and storing the frequency pair list.
Thus, overall is O(N) time, O(N) space.
Alternatively, we can consider this problem is to find K most frequent items. It can be done in O(N) as well, see this post for detailed discussion: capacode.com/?p=598
Not sure whether I understand the problem correctly. Following is my idea:
Let Mx be the maximum length of consecutive number sequence (CNS) that ends at node x.
Then for each child c of x, the Mc - maximum length of CNS that ends at c, is calculated as following:
If the value of c (e.g. 4) is consecutive number after value of x (e.g. 3), then Mc = Mx +1
otherwise, start new sequence at c: Mc = 1.
Time complexity: O(N), N = number of nodes in the tree.
Pseudo C++ code (Recursion):
struct TreeNode{
int val;
int maxLen; // Mx -- max length of consecutive number sequence that ends at this node.
TreeNode* V[]; // all childs
}
void findMaxLength(TreeNode x, TreeNode parent){
if (x.val == parent.val +1 ) x.maxLen = parent.maxLen + 1;
else x.maxLen = 1;
if (x.maxLen > globalMax) globalMax = x.maxLen;
for each child c of x do
findMaxLength(c, x);
};
main(){
root.maxLen = 1;
globalMax = 0;
for each child v of root
findMaxLength(v,root);
cout <<globalMax<<endl;
}
The best algorithm to find shortest path in this case is BFS.
Start from (1,1), do BFS until reaching the goal.
C++ code (with bugs):
int minStep(int m, int n){
pair<int,int> Que[MMAX*NMAX];
int Dist[MMAX*NMAX];
bool Visited[MMAX][NMAX] = {false}; //bugs
Que[0] = make_pair(1,1);
Dist[0] = 0;
Visited[1][1] = true;
top = 0; last = 0;
while(top <= last){
pair<int,int> u = Que[top];
int x = u.first, y = u.second;
if (x==m and y==n) return Dist[top];
//right:
if (x+y<=m)
if (! Visited[x+y][y]){
last++;
Que[last] = make_pair(x+y,y);
Dist[last] = Dist[top]+1;
Visited[x+y][y] = true;
};
//down:
if (x+y<=n)
if (! Visited[x][x+y]){
last++;
Que[last] = make_pair(x,x+y);
Dist[last] = Dist[top]+1;
Visited[x][x+y] = true;
};
top++;
};
Return INFINITY; // Can't reach to the goal?
};
@Scott: m is the size of a column.
Imagine you have m arrays (each of size n), sorted already. You want to merge them into 1 single list.
The heap/priority queue is to store the m front elements of m arrays, initially.
Each time, the minimum element x in the heap is extracted, and put into the final list. Suppose x was come from the array k. Then, the next element of k-th array is inserted into the heap. This process continues until all elements are inserted/extracted to/from the heap.
Each insert/extract_min operation takes O(log m) for the heap of size m. Thus, overall time is: mn O(logm) = O(mn logm).
This algorithm takes O(m) space. In implementation, it takes 3m space for the heap: 1 int for the value, 1 int for the number k (for k-th array), 1 int for the index of next element in k-th array.
In C++ we can use pair of pairs, like pair<int val, pair<int k, int id> > to represent element of heap. This way will work without user-defined comparison function.
Rep
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
RepLoler, Employee at Google
RepNelson Perez, Software Engineer
Repaliciagreene771, Vashikaran mantra for get my love back at None
Hello! How are you,My name is Alicia Greene I am from London (UK). I am a Business English, Math ...
RepNoahTaylor, abc at A9
Accomplished software developer with many years of experience in development of applications. Excels in every stage of the life cycle ...
RepEarned praise for analyzing acne for the government. Earned praised for my work implementing mantra to get desired husband in ...
Replamisobbeya45, Student at None
Hello there, My name is Lamis Obbeya I am from Brooklyn, New York . I am 29 years of age. I ...
RepAugment is a mobile app that lets you and your customers visualize your 3D models in Augmented Reality. If you ...
RepNellieWheeler212, None at Service Now
Hey Everyone! My name is Nellie Wheeler and I live in the constantly radiant and wonderful San Francisco, CA, and ...
RepA real dynamo when it comes to buying and selling carnival rides in Fort Lauderdale, FL. Spend several years working ...
Repmorganweiler771, Employee at None
Hello Everyone, I am Morgan Weiler I am from Mumbai, (India).I enjoy Watching TV, playing guitar, Yoga and reading ...
RepAre you looking a solution for marry your love? Islamic dua to marry someone you love is the effective solution ...
RepPandit Ji is the best vashikaran expert for vashikaran mantra for girlfriend in Mumbai.It is the strongest method to ...
RepAre you looking for strong dua for husband love?Astrology is the perfect way to get your lost love back ...
RepAmber Van is registered and fully insured cheap removal company in Bristol.Our featured services includes domestic moves,commercial moves ...
Rep
RepAre you wasting time for to search a professional astrologer and specialist to get rid of black magic?Black Magic ...
Repaalvinbrowne, Android Engineer at ASAPInfosystemsPvtLtd
Working as an Agricultural laborer at Mars Music I maintain yields like natural products, vegetables, grains, and nuts, or take ...
RepLeonaDWilliams, Analyst at CCN
At the moment I'm building banjos in Deltona, FL. Once had a dream of analyzing easy-bake-ovens in Fort Walton ...
RepDo you want to marry with your desired person? The Islamic dua for marriage with a loved one has great ...
RepCeliaParker, teacher at Illinoisstate
Experienced teacher with a background in education who is looking to complement graduate studies with the opportunity to teach at ...
This problem can be solved in O(N) time, using a data structure call Deque, which is a queue that can be pushed/popped from both ends, in O(1) time.
- ninhnnsoc September 25, 2016The idea is: to maintain a sliding window of size K using deque. Once we push in from the right-end a number x, we need to pop out from the left-end all the numbers that are bigger than x, because these numbers cannot be a minimum of any future k-window.
I explained in details with code at this post:
capacode /array/finding-maximums-for-all-k-windows-in-linear-time/