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

Comments

Post a Comment

Popular posts from this blog

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 ; } el
Read more

How to dump http request headers with PHP under CGI/FastCGI SAPI

Good old days of PHP installation exclusively as an Apache module are gone. Most of the modern PHP installations interact with a web server via FastCGI protocol. For instance nginx webserver and php-fpm daemon. This means that certain apache SAPI functions are not available anymore. One of this functions is apache_request_headers() to dump http headers sent by client. From CGI specification rfc3875, section 4.1.18: Meta-variables with names beginning with "HTTP_" contain values read from the client request header fields, if the protocol used is HTTP. The HTTP header field name is converted to upper case, has all occurrences of "-" replaced with "_" and has "HTTP_" prepended to give the meta-variable name. According to the specification above i wrote a piece of the PHP code that dumps all headers sent by client under any PHP SAPI: foreach ($_SERVER as $key => $value) { if (strpos($key, 'HTTP_') === 0) { $chunks = e
Read more

Zend Framework 2 AJAX: return JSON response from controller action. The proper way.

There is a lot of solutions over the web on how to return data on AJAX request in your Zend Framework 2 application. But none of them seems to be aware of the "right way" described in Zend Framework 2 manual - http://framework.zend.com/manual/2.0/en/modules/zend.mvc.examples.html#returning-early Implementation example: <?php namespace <YOUR_MODULE>\Controller; use Zend\Mvc\Controller\AbstractActionController; use Zend\Json\Json; class AjaxController extends AbstractActionController { public function testAction() { $data = array( 'result' => true, 'data' => array() ) return $this->getResponse()->setContent(Json::encode($data)); } }
Read more