Posts

Showing posts from January, 2015

Memory efficient array permutation in PHP 5.5 using generators

Generators support was introduced in PHP 5.5. The yield keyword is a really cool thing that allows to write an elegant and memory efficient code. It was existing in another dynamic languages like python for quite a long time and now it is in PHP as well! To demonstrate generators concept, i wrote a sample function that  yields  all permutations of the given array and avoids of data copying on recursive calls: function permute( $array ) { $length = sizeof( $array ); $inner = function ( $ix = []) use ( $array , $length , & $inner ) { $yield = sizeof( $ix ) == $length - 1 ; for ( $i = 0 ; $i < $length ; $i ++) { if (in_array( $i , $ix )) { continue ; } elseif ( $yield ) { $toYield = []; foreach (array_merge( $ix , [ $i ]) as $index ) { $toYield [] = $array [ $index ]; } yield $toYield ; ...

Hackerrank "Is Fibo" challenge solution in Python 3

N is a fibonacci number if and only 5N^2 + 4 or 5N^2 – 4 is a perfect square number  http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers Solution in python 3: import math n = int(input()) for i in range(0,n): number = int(input()) if math.sqrt(5 * number ** 2 + 4).is_integer() or math.sqrt(5 * number ** 2 - 4).is_integer(): print("IsFibo") else: print("IsNotFibo") This solution has a complexity O(1) compared to simple solution by adding all numbers from 0 to N that has a O(n) complexity