alexander
BAN USER@eugene If you make all the constructors of the base class protected then you can only call those constructors for base class initialization when calling derived class constructor using this pointer, There's no way for you to create its object, so also you can't copy.
I think it is better than making private.
Since by making private you will make derived classes uncopyable too, which is not what we want
Let us take the extreme case that one word of the file is too big that it can't fit into the Memory, then we can take pointer(PTR1) to the first character of that word(stored in some block 'x' of hard disk ) and pointer(PTR2) to the last character of that word(stored in some block 'y' of hard disk ) and keep on swapping and incrementing PTR1 and decrementing PTR2 till the end of the blocks.
Then again we will do this for the rest part of the word.
Until and unless PTR1 becomes equal to the PTR2.
If (PTR1==PTR2)
Means the whole word is reversed.
Like this can be done to reverse all the words in the first file.
After that we can read the maximum part of the first file which can fit into the memory and then copy it into the second file.
Can be solved in O(n^2) time and O(n) space.
1. Store all the values of c array in a hashmap with value as index - O(n) space
2. Then get the sum of all the pairs of elements of array a and array b and check whether they are present in hashmap.
3. If present then print the values.
@eugene You mean to say that the mobile numbers are stored somewhere else as strings and the those mobile numbers are stored in the trie in sorted way.
And since every mobile number is 10 digits we can have the pointer to the string (actual mobile no.) in the last node itself.
This works fine based on DP and it takes
Time-O(S*D), where S is the sum and D are the number of different denominations
Space-O(S*D)
#include<stdio.h>
int min(int a,int b )
{
if(a==-1)
return (b);
else if(b==0)
return a;
else
return a<b?a:b;
}
int getdenominations(int den[],int n,int sum)
{
int i;
int arr[n+1][sum+1];
for(i=0;i<=sum;i++)
arr[0][i]=0;
for(i=1;i<=n;i++)
arr[i][0]=0;
for(i=1;i<=sum;i++)
{if(i%den[0]==0)
arr[1][i]=i/den[0];
else
arr[1][i]=-1;
}
int j;
for(i=2;i<=n;i++)
{
for(j=1;j<=sum;j++) //j is the sum
{
if(j<den[i-1])
arr[i][j]=arr[i-1][j];
else if(j%den[i-1]==0)
arr[i][j]=j/den[i-1]; //this will be the minimum for this case
else
{
arr[i][j]=min(arr[i-1][j], arr[i][j-den[i-1]]+1);
}
}
}
return arr[n][sum];
}
int main()
{
int den[]={2,3};
int sum=25;
int len=sizeof(den)/sizeof(den[0]);
printf("%d ",getdenominations(den,len,sum) );
return 0;
}
Remove the node which you want to make the root of new BST and make its parent pointer 's that child point to NULL.
After then remove one by one element from the Original BST starting from the leaves and insert them into your new BST.
Time Complexity - O(nlogn)
I think we can
(i) store the occurence of every element using maps in C++
(ii) build a Max-heap in linear time of the occurences(or frequence) of element and then extract upto the N-th element,
Each extraction takes log(n) time to heapify.
(iii) we will get the frequency of the N-th most frequent number
(iv) then we can linear search through the hash to find the element having this frequency.
Time - O(NlogN)
Space - O(N)
If the search word is banana and the array is
- alexander October 08, 2015[aanana, canana, danana, eanana ....... zanana]
then in this case using your trie method would have a time complexity of O(NK) to find all such strings where N is number of strings in array and K is the max length of any string.
Please correct me if I am wrong.