Example: Reduce to Common Base Value in C

// Reduce to Common Base Value
#include <stdio.h>
#include <stdbool.h> // For boolean type

// Function to normalize a number by repeatedly dividing by 2 and 3
int normalize(int num) {
    // Step 1: Handle non-positive numbers if necessary, here 0 remains 0.
    if (num == 0) return 0;

    // Step 2: Repeatedly divide by 2 until it's no longer divisible
    while (num > 0 && num % 2 == 0) {
        num /= 2;
    }
    // Step 3: Repeatedly divide by 3 until it's no longer divisible
    while (num > 0 && num % 3 == 0) {
        num /= 3;
    }
    return num; // Return the normalized base value
}

// Function to check if all array elements can be made equal
// by normalizing them to a common base value
bool canBeMadeEqualByNormalization(int arr[], int n) {
    // Step 1: Handle empty or single-element arrays
    if (n <= 1) {
        return true;
    }

    // Step 2: Normalize the first element to get the target base value
    int targetBaseValue = normalize(arr[0]);

    // Step 3: Iterate through the rest of the array and normalize each element
    for (int i = 1; i < n; i++) {
        if (normalize(arr[i]) != targetBaseValue) {
            return false; // Found an element that normalizes to a different base
        }
    }

    // Step 4: All elements normalize to the same base value
    return true;
}

int main() {
    // Example 1: Can be made equal
    int arr1[] = {12, 18, 72};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);

    printf("Array: [");
    for (int i = 0; i < n1; i++) {
        printf("%d%s", arr1[i], (i == n1 - 1) ? "" : ", ");
    }
    printf("]\n");
    if (canBeMadeEqualByNormalization(arr1, n1)) {
        printf("Result: All numbers can be made equal by reducing factors of 2 and 3.\n\n");
    } else {
        printf("Result: Not all numbers can be made equal by reducing factors of 2 and 3.\n\n");
    }

    // Example 2: Cannot be made equal
    int arr2[] = {12, 15, 72};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    printf("Array: [");
    for (int i = 0; i < n2; i++) {
        printf("%d%s", arr2[i], (i == n2 - 1) ? "" : ", ");
    }
    printf("]\n");
    if (canBeMadeEqualByNormalization(arr2, n2)) {
        printf("Result: All numbers can be made equal by reducing factors of 2 and 3.\n\n");
    } else {
        printf("Result: Not all numbers can be made equal by reducing factors of 2 and 3.\n\n");
    }

    // Example 3: Already equal
    int arr3[] = {6, 6, 6};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);

    printf("Array: [");
    for (int i = 0; i < n3; i++) {
        printf("%d%s", arr3[i], (i == n3 - 1) ? "" : ", ");
    }
    printf("]\n");
    if (canBeMadeEqualByNormalization(arr3, n3)) {
        printf("Result: All numbers can be made equal by reducing factors of 2 and 3.\n\n");
    } else {
        printf("Result: Not all numbers can be made equal by reducing factors of 2 and 3.\n\n");
    }

    // Example 4: Contains zero
    int arr4[] = {0, 12, 18};
    int n4 = sizeof(arr4) / sizeof(arr4[0]);

    printf("Array: [");
    for (int i = 0; i < n4; i++) {
        printf("%d%s", arr4[i], (i == n4 - 1) ? "" : ", ");
    }
    printf("]\n");
    if (canBeMadeEqualByNormalization(arr4, n4)) {
        printf("Result: All numbers can be made equal by reducing factors of 2 and 3.\n\n");
    } else {
        printf("Result: Not all numbers can be made equal by reducing factors of 2 and 3.\n\n");
    }

    return 0;
}