Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- struct Elem{
- struct Elem *next;
- int key , value;
- };
- struct Elem *Lookup(int index ,struct Elem *HashTable){
- for (struct Elem* list = HashTable; list != NULL; list=list->next){
- if(list->key == index)
- return list;
- }
- return 0;
- }
- struct Elem *Insert(int index ,int value , struct Elem *HashTable){
- struct Elem *list = (struct Elem*)malloc(sizeof(struct Elem));
- list->next = HashTable;
- list->key = index;
- list->value = value;
- HashTable = list;
- return HashTable;
- }
- struct Elem** InitTable(struct Elem** HashTable, int n){
- HashTable = (struct Elem**)malloc(n * sizeof(struct Elem*));
- for(int i = 0 ; i < n ; i++) HashTable[i] = NULL;
- return HashTable;
- }
- int Clear(struct Elem* list, int answer){
- struct Elem* tmp;
- while(list != NULL){
- tmp = list;
- list = tmp->next;
- answer += tmp->value;
- free(tmp);
- }
- return answer;
- }
- int main(){
- int n, answer = 0;
- scanf("%d" , &n);
- int num, zero = 0; // in case of error change to long int here and %d -> &li in 38 line
- struct Elem **HashTable;
- HashTable = InitTable(HashTable, n);
- for(int i = 0 ; i < n ; i++) HashTable[i] = NULL;
- HashTable[0] = Insert(0 , 0 , HashTable[0]);
- struct Elem *elem = NULL;
- for(int i = 0 ; i < n ; i++){
- scanf("%d" , &num);
- zero = zero ^ num;
- // long int key = zero % n excess variable
- elem = Lookup(zero, HashTable[zero % n]);
- if(elem != NULL){
- answer += elem->value;
- elem->value+=1;
- }
- else HashTable[zero % n] = Insert(zero , 0 , HashTable[key]);
- }
- for(int i = 0; i < n; i++){
- answer = Clear(HashTable[i], answer);
- }
- free(HashTable);
- printf("%d\n" , answer);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement