869. Reordered Power of 2

[mah-shamim]

Topics: Hash Table, Math, Sorting, Counting, Enumeration, Weekly Contest 93

You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

Example 1:

• Input: n = 1
• Output: true

Example 2:

• Input: n = 10
• Output: false

Constraints:

• 1 <= n <= 109

[mah-shamim]

We need to determine if we can reorder the digits of a given integer n such that the resulting number (with no leading zeros) is a power of two. The solution involves checking all possible powers of two that have the same number of digits as n and comparing their digit frequencies with that of n. If any power of two matches the digit frequency of n, then it's possible to reorder n to form that power of two.

Approach

1. Convert the integer to a string: This allows us to easily access each digit and determine the length of the number.
2. Count digit frequencies: Create a frequency array for the digits in n to compare with potential powers of two.
3. Generate powers of two: Starting from 1 (2⁰), generate subsequent powers of two as strings. For each generated power:
   • Check the length: If the length matches the length of n, count its digit frequencies.
   • Compare frequencies: If the digit frequencies match those of n, return true.
4. Terminate early: If the generated power of two exceeds the length of n, terminate the loop since further powers will only have more digits.
5. Return result: If no matching power of two is found after checking all relevant powers, return false.

Let's implement this solution in PHP: 869. Reordered Power of 2

<?php
/**
 * @param Integer $n
 * @return Boolean
 */
function reorderedPowerOf2($n) {
    $s = (string)$n;
    $len = strlen($s);
    $freq_n = count_frequency($s);
    $p = "1";
    while (strlen($p) <= $len) {
        $current_len = strlen($p);
        if ($current_len == $len) {
            $freq_p = count_frequency($p);
            if ($freq_p == $freq_n) {
                return true;
            }
        }
        $p = multiply_by_2($p);
    }
    return false;
}

/**
 * @param $s
 * @return array
 */
function count_frequency($s) {
    $freq = array_fill(0, 10, 0);
    $length = strlen($s);
    for ($i = 0; $i < $length; $i++) {
        $digit = (int)$s[$i];
        $freq[$digit]++;
    }
    return $freq;
}

/**
 * @param $s
 * @return string
 */
function multiply_by_2($s) {
    $result = '';
    $carry = 0;
    $length = strlen($s);
    for ($i = $length - 1; $i >= 0; $i--) {
        $digit = (int)$s[$i];
        $product = $digit * 2 + $carry;
        $carry = (int)($product / 10);
        $digit_result = $product % 10;
        $result = (string)$digit_result . $result;
    }
    if ($carry) {
        $result = (string)$carry . $result;
    }
    return $result;
}

// Test cases
var_dump(reorderedPowerOf2(1));  // true
var_dump(reorderedPowerOf2(10)); // false
?>

Explanation:

1. Digit Frequency Check: The count_frequency function creates an array of size 10 (for digits 0-9) and counts occurrences of each digit in the input string.
2. Power of Two Generation: The multiply_by_2 function takes a string representation of a number and multiplies it by 2, handling carry-over to produce the result as a string.
3. Main Loop: Starting from "1" (2⁰), the loop generates each subsequent power of two. For each power:
   • If its length matches n's length, its digit frequencies are compared with n's.
   • If frequencies match, true is returned immediately.
   • The loop terminates when a power of two exceeds the length of n.
4. Result: If no matching power is found after all relevant checks, the function returns false.

This approach efficiently checks all possible powers of two with the same digit length as n by leveraging digit frequency comparison, ensuring optimal performance even for large values of n.

[topugit]

Thanks for solving the problem of "Reordered Power of 2"

[mah-shamim]

Thanks