fork download 
  1. /*
  2. given an array of size n...
  3. create an array of size n such that ai where ai is the element in the
  4. new array at index location i is equal to sum of all elements in
  5. original array which are smaller than element at posn i...
  6. e.g
  7. ar[]={3,5,1,6,7,8};
  8. ar1[]={0,3,0,9,15,22};
  9. */
  10. #include<stdio.h>
  11. #include<stdlib.h>
  12. struct node{
  13. int data;
  14. struct node *left,*right;
  15. int lcount;
  16. int k;
  17. };
  18. struct node* newnode(int data,int d)
  19. {
  20. struct node *node=(struct node*)malloc(sizeof(struct node));
  21. node->data=data;
  22. node->left=node->right=NULL;
  23. node->lcount=d;
  24. node->k=0;
  25. return node;
  26. }
  27. struct node* insert(struct node *root,int data,int *d)
  28. {
  29. if(root==NULL)
  30. {
  31. root=newnode(data,*d);
  32. return root;
  33. }
  34. if(root->data>data)
  35. {
  36. root->k +=data;
  37. //left subtree
  38. root->left=insert(root->left,data,d);
  39. }
  40. else if(root->data < data)
  41.       {
  42.        // right case
  43.        *d=*d+root->data+root->k;        
  44.        root->right=insert(root->right,data,d);
  45.        }
  46. return root;
  47. }
  48. void inorder(struct node *root)
  49. {
  50. if(root!=NULL)
  51. {
  52. inorder(root->left);
  53. printf(" value->%d ,lcount ->%d\n",root->data,root->lcount);
  54. inorder(root->right);
  55. }
  56. }
  57. int main()
  58. {
  59. int a[]={3,5,1,6,7,2};
  60. struct node *root=NULL;
  61. for(int i=0;i<6;i++)
  62. {int d=0;
  63. root=insert(root,a[i],&d);
  64. printf("value-> %d.... sum %d\n",a[i],d);
  65. }
  66. //inorder(root);
  67. return 0;
  68. }
  69.  
  70.  
Success #stdin #stdout 0.02s 2856KB
comments (?)
stdin 
Standard input is empty
stdout 
value-> 3.... sum 0
value-> 5.... sum 3
value-> 1.... sum 0
value-> 6.... sum 9
value-> 7.... sum 15
value-> 2.... sum 1
https://ideone.com/CH7VW
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!