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 ; ...
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

Jqgrid show totals in the footer plugin

This plug-in automatically calculates sum of the all numeric rows in your grid and displays it in the new "Totals" row at the bottom of the grid. jqgrid 4.3.2+ is required. (function($) { $.jgrid.extend({ showTotals: function(options) { var o = $.extend({ total: "Totals", totalRow: undefined, includeRows: [] }, options || {}) return this.each(function() { if (!this.grid) { return; } var self = this; var showTotals = function() { var totals = {}; $.each(self.p.colModel, function(index, data) { if (o.totalRow && o.totalRow == data.index) { totals[data.index] = o.total; } else { var sum = NaN; if (...
Read more