Advertisement
Guest User

Untitled

a guest
Feb 27th, 2020
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.88 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct Elem{
  5. struct Elem *next;
  6. int key , value;
  7. };
  8.  
  9. struct Elem *Lookup(int index ,struct Elem *HashTable){
  10. for (struct Elem* list = HashTable; list != NULL; list=list->next){
  11. if(list->key == index)
  12. return list;
  13. }
  14. return 0;
  15. }
  16.  
  17. struct Elem *Insert(int index ,int value , struct Elem *HashTable){
  18. struct Elem *list = (struct Elem*)malloc(sizeof(struct Elem));
  19. list->next = HashTable;
  20. list->key = index;
  21. list->value = value;
  22. HashTable = list;
  23. return HashTable;
  24. }
  25.  
  26. struct Elem** InitTable(struct Elem** HashTable, int n){
  27. HashTable = (struct Elem**)malloc(n * sizeof(struct Elem*));
  28. for(int i = 0 ; i < n ; i++) HashTable[i] = NULL;
  29. return HashTable;
  30. }
  31.  
  32. int Clear(struct Elem* list, int answer){
  33. struct Elem* tmp;
  34. while(list != NULL){
  35. tmp = list;
  36. list = tmp->next;
  37. answer += tmp->value;
  38. free(tmp);
  39. }
  40. return answer;
  41. }
  42.  
  43. int main(){
  44. int n, answer = 0;
  45. scanf("%d" , &n);
  46. int num, zero = 0; // in case of error change to long int here and %d -> &li in 38 line
  47. struct Elem **HashTable;
  48. HashTable = InitTable(HashTable, n);
  49. for(int i = 0 ; i < n ; i++) HashTable[i] = NULL;
  50. HashTable[0] = Insert(0 , 0 , HashTable[0]);
  51. struct Elem *elem = NULL;
  52. for(int i = 0 ; i < n ; i++){
  53. scanf("%d" , &num);
  54. zero = zero ^ num;
  55. // long int key = zero % n excess variable
  56. elem = Lookup(zero, HashTable[zero % n]);
  57. if(elem != NULL){
  58. answer += elem->value;
  59. elem->value+=1;
  60. }
  61. else HashTable[zero % n] = Insert(zero , 0 , HashTable[key]);
  62. }
  63. for(int i = 0; i < n; i++){
  64. answer = Clear(HashTable[i], answer);
  65. }
  66. free(HashTable);
  67. printf("%d\n" , answer);
  68. return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement