#include <stdio.h>
#include <math.h>

// Division Method
int divisionMethod(int key, int tableSize) {
    return key % tableSize;
}

// Multiplication Method
int multiplicationMethod(int key, int tableSize) {
    float A = 0.618033;
    float temp = key * A;
    float fractional = temp - (int)temp;
    return (int)(tableSize * fractional);
}

// Mid-square Method
int midSquareMethod(int key, int tableSize) {
    long long square = (long long)key * key;

    int digits = 0;
    long long temp = square;
    while (temp > 0) {
        digits++;
        temp /= 10;
    }

    int extract = (int)(square / pow(10, digits/4)) % (int)pow(10, digits/2);

    return extract % tableSize;
}

// Folding Method
int foldingMethod(int key, int tableSize) {
    int sum = 0;

    while (key > 0) {
        sum += key % 100;  // split into 2-digit parts
        key /= 100;
    }
    return sum % tableSize;
}

// Driver code
int main() {
    int keys[5], tableSize, choice;
    static int table[15];

    printf("Enter 5 numbers:\n");
    for (int i = 0; i < 5; i++) {
        scanf("%d", &keys[i]);
    }

    printf("Enter hash table size (<15): ");
    scanf("%d", &tableSize);

    printf("\nChoose Hash Method:\n");
    printf("1. Division Method\n");
    printf("2. Multiplication Method\n");
    printf("3. Mid-square Method\n");
    printf("4. Folding Method\n");
    printf("Enter choice: ");
    scanf("%d", &choice);

    printf("\nHash values:\n");

    for (int i = 0; i < 5; i++) {
        int hash;

        switch (choice) {
            case 1:
                hash = divisionMethod(keys[i], tableSize);
                break;
            case 2:
                hash = multiplicationMethod(keys[i], tableSize);
                break;
            case 3:
                hash = midSquareMethod(keys[i], tableSize);
                break;
            case 4:
                hash = foldingMethod(keys[i], tableSize);
                break;
            default:
                printf("Invalid choice!\n");
                return 0;
        }
        table[hash]=keys[i];
    }
    
    for (int i=0;i<tableSize;i++)
     printf("%d\t",table[i]);

    return 0;
}