raunak.gupta29
BAN USERYup correct it will not work for all cases if the line(which contains max points) will go from origin in that case it will work but if i/p is like {(1,2),(1,4),(1,5),(1,7)..(3,2)}or some other in that case it wll not work .
- raunak.gupta29 November 30, 2012typedef struct node{
int data;
struct node *left;
struct node *right;
}node;
node *newnode(int x){
node *temp = malloc(sizeof(node));
temp->data = x;
temp->left=temp->right = NULL;
}
node * construst_bst(int arr[],int n){
node *head=NULL,*temp,*new;
if(sizeof(arr)/sizeof(int) != n||n<=0){
printf("Array size and given size of array have mismatch\n");
return(NULL);
}
head = newnode(arr[0]);
temp = head;
if(n==1)
return head;
for(i=1;i<n;i++){
new = newnode(arr[i]);
if(arr[i]<=temp->data){
new->right = temp;
temp->left = new;
temp = new;
}
else{
while(temp){
if(temp->right == NULL){
temp->right = new;
temp = new;
break;
}
else{
if(arr[i]>temp->right->data)
temp = temp->right;
else{
new->right = temp->right;
temp->right = new;
temp = new;
break;
}
}
}
}
}
return(head);
}
first sort all points according to there polar angle i have given code for sorting point according to polar angle
typedef struct point{
int x;
int y;
}point;
int cross_product(point a, point b){
if((a.x*b.y-a.y*b.x)>0)
return 1;
return -1;
}
int partition(arr,p,r){
point pivot = arr[r-1];
int i=p,flag,j=-1;
while(i<r-1){
flag = cross_product(pivot,arr[i]);
if(flag == 1){
if(j==-1){
j = p+1;
}
while(j<r-1){
flag = cross_product(pivot,a[j])
if(flag!=1){
swap(arr[i],arr[j]);
j=j+1;
break
}
j++;
}
if(j == r-1){
swap(arr[i+1],arr[r])
return(i+1);
break
}
}
i++;
}
swap(arr[i+1],arr[r])
return(i+1);
}
void polar_sort(point arr[],int start,int end){
int stack[end],top =-1,p,r,k;
stack[++top] = start;
stack[++top] = end;
while(isEmpty(stack)){
r = stack[top--];
p = stack[top--];
if(p<r){
k = partition(arr,p,r);
if(k+1<r){
stack[++top] = k+1;
stack[++top] = r;
}
if(p<k){
stack[++top] = p;
stack[++top] = k;
}
}
}
}
in this way u sort the point according to polar angle now just we have to trverse this sorted point array and for comparing
,is they lie on same line or not do cross product and if cross product is 0 then yup they are in same line and as array is sorted
according to polar angle, all points are in same line coming together just find max group whose cross product is 0 that u can do esily
in one traversal and for finding the line ,found two farthest point in the group and make a line with those two points
correct me if i m wrong complexity(nlogn)
as i don't know m, may be it is a big number and n is less compare to m then it is not good to store the element into array so for that we need to store data into linklist .
take two pointer one slow and one fast pointer . when fast pointer move two step then slow pointer move one step . so just insert the element into linklist (always next to the fast pointer) and modified both fast pointer and slow pointer as i mention above and at the end of the stream the slow pointer should be point to the n/2th position.
let me know if things r not good.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node
{
int data;
struct node *next;
}node;
void fun(char *str)
{
node *a[256] = {NULL},*temp = NULL,*parr = NULL,*temp1 = NULL;
int i=0,j,k;
while(i<strlen(str))
{
temp = malloc(sizeof(node));
temp->data =i;
temp ->next =NULL;
if(a[(str[i])] == NULL)
a[(str[i])] = temp;
else
{
temp1 = a[(str[i])];
while(temp1!=NULL)
{
parr = temp;
j = temp1->data;
k = i;
while(j<i)
{
if(str[j] == str[k])
{
j++;
k++;
}
else
break;
}
if(j==i)
printf("string index %d to index %d is reapeted \n",temp1->data,i-1);
temp1 = temp1->next;
}
parr->next = temp;
}
i++;
}
}
int main()
{
char *str = malloc(100);
printf("Enter the string : ");
scanf("%s",str);
fun(str);
}
also in max heap we don't need extra space.......
- raunak.gupta29 March 14, 2012@Anonymous - yes u r right..... thanks for the correction ....
@pradeep.. yes pradeep u can solve this problem in this way also .. but in some case it will give some problem... ex .. suppose there r million num is there and u have to find 150 smallest element ...
but still the complexity point of view aprx the same......... also u don't need extra space.......
@rkt -- here your code is wrong for some i/p ex-{1,2,3,4} when u iterate this i/p u find an error.....
correct code is.....
// here len of the array means no of element in that array.....
void reverse(int a[],int len){
int i,temp;
if(len%2==0)
{
len =len-1;
for(i=0;i<(len/2)+1;i++){
temp = a[i];
a[i] = a[len-i];
a[len-i] = temp;
}
}
else
{
for(i=0;i<len/2;i++){
temp = a[i];
a[i] = a[len-1-i];
a[len-1-i] = temp;
}
}
}
@Anonymous its min heap not max heap here we need million smallest element not million largest element and max heap contain million largest element
pls let me know if i m wrong ......... thanks
for solving this problem we can use min heap sort create an array of million size and iterate billion numbers and full that array and the data that are not fit into y=the array just ignore them as they are not in the set of million smallest element complexity is billionLOG(million).........
- raunak.gupta29 March 13, 2012
- raunak.gupta29 August 27, 2017