Last active
May 21, 2017 03:08
-
-
Save rutwick/a24106a073a1c4d7d9dd82e25b6e4a41 to your computer and use it in GitHub Desktop.
Calculate the length of the shortest array that is required to form a Binarian of an input array
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?php | |
| /** | |
| * Main function | |
| * @param {array} $A The input array | |
| * @return {int} The length of the shortest array to form the binarian | |
| */ | |
| function solution($A) { | |
| if(empty($A)) { | |
| return false; | |
| } | |
| $binarian = binarian($A); | |
| return factorize($binarian, $A); | |
| } | |
| /** | |
| * Binarian function | |
| * @param {array} $A The input array | |
| * @return {int} $binarian The binarian of the input array | |
| */ | |
| function binarian($arr) { | |
| $binarian = 0; | |
| for($i = 0; $i < count($arr); $i++) { | |
| //Raise 2 to the value | |
| $binarian += pow(2, $arr[$i]); | |
| } | |
| return $binarian; | |
| } | |
| /** | |
| * Factorize | |
| * Raises 2 to the powers decreasing from the length of the input array | |
| * @param {int} $bin The binarian of the input array | |
| * @param {int} $length The length of the input array | |
| * @return {int} $count The length of the shortest array required to calculate binarian | |
| */ | |
| function factorize($bin, $arr) { | |
| $count = 0; | |
| $length = count($arr); | |
| for($i = $length - 1; $i >= 0; $i--) { | |
| $pow = pow(2, $i); | |
| //If the binarian found, break the loop | |
| if($pow == $bin) { | |
| $count++; | |
| break; | |
| } | |
| //Calculate until value lower than binarian found | |
| //The new upper limit will be the difference between the binarian and the value of 2 raised to the index | |
| else if($pow < $bin) { | |
| $count++; | |
| $bin = $bin - $pow; | |
| } | |
| } | |
| return $count; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
You may lose the case such as [2,2,3] where the solution is 1