Frodo Baggins
BAN USERThe ring is mine .. :)
// Assumption : neg. numbers are not allowed
int MaxJump(int A[] , int startIndex){
int len=lenght_of(A);
if(startIndex>=len) return 0;
if(A[startIndex]==0) return -1;
int ret=MaxJump(A,startIndex+A[startIndex]);
return ret==-1?-1:1+ret ;
}
// If negative numbers are allowed then we can have a mark[] array to handle already visited indexes .
- Frodo Baggins August 27, 2010int count_div(int a,int b,int k){
return b/k - (a-1)/k ;
}
@ amirhossein.jabbari , It won't print 6 twice coz I have taken care of that by checking before pushing a value but off course its printing 9 before 8 .
Thanks for pointing that out .
So now , The only solution I can come up with is using min heap which will take O(n lg(n)) .
@Hinex , I don't think u can solve this problem using ur algorithm . Come up with ur exact algorithm and I will try to find a counterexample .
- Frodo Baggins August 25, 2010Try to solve this problem when only prime divisors are 2,3 and 5 .
- Frodo Baggins August 25, 2010// Here is my solution which is based on BFS , if we use our own queue DS which has functionality to return front() as well as back() element in O(1) then it will be O(n) solution .
so suppose we have our own queue<int> class , which has these 4 member functions ->
q.front() // returns front element
q.back() // returns back element
q.push(),q.pop() // same as standard queue
Now ,
fun generateSeq(int n){
queue<int > q;
q.push(1);
while(n--){
int v=q.front() ;
q.pop();
print(v);
if(v*2 != q.back()) q.push(v*2);
if(v*3 != q.back()) q.push(v*3);
}
}
@ amirhossein.jabbari
Don't u think that it will print all the numbers i.e. 0,1,2,3,4,5,6,7 .......
Even if u wrote '||' by mistake (instead of '&&') then also it will print 15 which is incorrect .
Is there any in space O(n) algo for this problem ?
- Frodo Baggins August 21, 2010fun PrintChar(string A , string B){
bool isPresentInB[128]=false ; // initialize all elements with false
for(int i=0;i<B.size();i++)isPresentInB[B[i]]=true;
bool isPresentInAbutNotInB[128]=false;
for(int i=0;i<A.size();i++)if(!isPresentInB[A[i]]) isPresentInAbutNotInB[A[i]]=true;
for(int i=0;i<128;i++)if(isPresentInAbutNotInB[i]) printf("%c\n",i);
}
*ptr will never be > 127 as it's a char pointer .
- Frodo Baggins August 17, 2010@Thiyanesh What kind of pointer is ptr1 ? If it is a char pointer then it will always read 1 byte and its value will never be > 127 .
- Frodo Baggins August 17, 2010I don't think this solution is any better than char counting solution suggested by Ashish , and also the values of total1 and total2 will be much larger that MAX_INT (depends on test case).
- Frodo Baggins August 17, 2010@guzhiwei Nice approach :)
- Frodo Baggins August 13, 2010can you please provide more information about your implementation and best and worst case runtime .
- Frodo Baggins August 13, 2010// My code
postorder(root,gparent,parent){
if(root==null)return;
root->granparent=gparent;
postorder(root->left,parent,root);
postorder(root->right,parent,root);
}
call postorder(root,null,null)
@MaYanK , I think you are assigning parent instead of grand parent here .
Every time you are calling postorder(root,gparent,count) ->
1. either gparent is null
2. or gparent->left=root or gparent->right=root
so , gparent is not the grand parent here , its parent .
One more thing , it will only set the gparent for the nodes where cout = 0 .
so , suppose we are at node current_node ,
then postorder(current_node->left,..) and postorder(current_node->right,..) will be called with count = 1 , and so the gparent for those nodes will not be assigned .
I think sorting the linked list and then returning the distinct numbers is better than maintaining a BST for that . There are 2 reason ->
1. Extra memory used to maintain the BST .
2. Worst case runtime : O(n^2)
// Java code
- Frodo Baggins June 21, 2014