Check If All Array Elements Can Be Made Equal (Multiply by 2 or 3)

Problem Statement

Given an array of positive integers, determine whether all elements can be made equal. The only allowed operation: multiply any element by 2 or by 3, any number of times.

Constraints

• Array length: 1 <= n <= 10^5
• Element values: 1 <= arr[i] <= 10^9
• Operations can be applied to any element, any number of times

Examples

• Input: [50, 75, 100] — Output: YES (each can reach 300)
• Input: [10, 14] — Output: NO
• Input: [12, 18, 8] — Output: YES (each can reach 72)

Approach and Intuition

Multiplying by 2 or 3 only adds factors of 2 and 3. It never introduces a new prime factor into the number. So two numbers can reach the same target value only if they differ exclusively in their powers of 2 and 3. Any other prime factor present in one but absent in the other makes equalisation impossible.

The reduction works backwards. Instead of asking “what common target can they reach?”, strip away the parts that multiplication can adjust. Divide each element by 2 (repeatedly) and by 3 (repeatedly) until neither divides it. The leftover is the element’s core.

If every element has the same core, you can always find a common multiple built from appropriate powers of 2 and 3. If any two cores differ, no amount of multiplying will bridge the gap.

This is a direct consequence of the fundamental theorem of arithmetic: every integer has a unique prime factorisation, and multiplying by 2 or 3 only modifies the exponents of those two primes.

Worked Examples

Example 1: [50, 75, 100]

• 50: divide by 2 once to get 25. 25 is not divisible by 2 or 3. Core = 25.
• 75: divide by 3 once to get 25. Core = 25.
• 100: divide by 2 twice (100 to 50 to 25). Core = 25.
• All cores equal 25. Answer: YES.
• Verification: 50 * 2 * 3 = 300, 75 * 2 * 2 = 300, 100 * 3 = 300.

Example 2: [10, 14]

• 10: divide by 2 once to get 5. Core = 5.
• 14: divide by 2 once to get 7. Core = 7.
• Cores differ (5 vs 7). Answer: NO.

Example 3: [12, 18, 8]

• 12: divide by 2 twice (12 to 6 to 3), then by 3 once (3 to 1). Core = 1.
• 18: divide by 2 once (18 to 9), then by 3 twice (9 to 3 to 1). Core = 1.
• 8: divide by 2 three times (8 to 4 to 2 to 1). Core = 1.
• All cores equal 1. Answer: YES.
• Verification: 12 * 2 * 3 = 72, 18 * 2 * 2 = 72, 8 * 3 * 3 = 72.

Example 4: [6, 10]

• 6: divide by 2 (to 3), then by 3 (to 1). Core = 1.
• 10: divide by 2 (to 5). Core = 5.
• Cores differ (1 vs 5). Answer: NO.

Implementation

Python

def reduce_element(x):
    while x % 2 == 0:
        x //= 2
    while x % 3 == 0:
        x //= 3
    return x

def can_be_made_equal(arr):
    core = reduce_element(arr[0])
    for i in range(1, len(arr)):
        if reduce_element(arr[i]) != core:
            return False
    return True

# Test
print(can_be_made_equal([50, 75, 100]))  # True
print(can_be_made_equal([10, 14]))        # False
print(can_be_made_equal([12, 18, 8]))     # True

C++

#include <iostream>
#include <vector>
using namespace std;

int reduceElement(int x) {
    while (x % 2 == 0) x /= 2;
    while (x % 3 == 0) x /= 3;
    return x;
}

bool canBeMadeEqual(vector<int>& arr) {
    int core = reduceElement(arr[0]);
    for (int i = 1; i < arr.size(); i++) {
        if (reduceElement(arr[i]) != core)
            return false;
    }
    return true;
}

int main() {
    vector<int> arr1 = {50, 75, 100};
    vector<int> arr2 = {10, 14};
    cout << (canBeMadeEqual(arr1) ? "YES" : "NO") << endl;  // YES
    cout << (canBeMadeEqual(arr2) ? "YES" : "NO") << endl;  // NO
    return 0;
}

Java

public class MakeArrayEqual {
    static int reduceElement(int x) {
        while (x % 2 == 0) x /= 2;
        while (x % 3 == 0) x /= 3;
        return x;
    }

    static boolean canBeMadeEqual(int[] arr) {
        int core = reduceElement(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            if (reduceElement(arr[i]) != core)
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(canBeMadeEqual(new int[]{50, 75, 100}));  // true
        System.out.println(canBeMadeEqual(new int[]{10, 14}));        // false
    }
}

Complexity Analysis

• Time: O(n × log(max_element)). For each of the n elements, we divide by 2 at most log2(V) times and by 3 at most log3(V) times. Combined: O(log V) per element.
• Space: O(1) extra. We store only the first element’s core and compare others against it. No auxiliary arrays needed.

For a deeper breakdown of how space complexity is analysed across different data structures, see the space complexity guide.

Related Array Problems

This reduction technique, where you normalise each element and compare, appears in several other array problems:

• Finding symmetric pairs in an array uses a similar element-by-element comparison after transformation.
• Finding the equilibrium index also requires a single-pass O(n) traversal with O(1) state.

The common thread: reduce each element to a canonical form, then check for uniformity or a target property. Once you internalise this pattern, variants like “make all elements equal by adding/subtracting K” or “minimum operations to equalise” become straightforward extensions of the same idea.

From Factor Reduction to Pattern Recognition

The divide-and-check pattern here (strip irrelevant factors, compare cores) shows up in number-theoretic interview problems across service and product companies hiring in India. Recognising that “multiply by 2 or 3” means “only the exponents of 2 and 3 are free variables” is the insight that separates a 5-minute solve from 30 minutes of brute-force attempts. The problem has appeared in PayPal and Amazon coding rounds, typically as a warm-up before harder graph or DP questions.

Stripping factors of 2 and 3 to compare cores took four lines of code here. The next step is spotting which reduction applies to a new problem you haven’t seen before. TinkerLLM (₹299) lets you feed an unfamiliar array problem to an LLM, walk through the factorisation logic interactively, and verify your edge cases before the interview clock starts.