Updates from January, 2017 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 11:57 pm on January 12, 2017 Permalink | Reply
    Tags: ,   

    Problem: Fibonacci Sum 

    *Difficulty: Easy

    Given a number positive number n, find value of f0 + f1 + f2 + …. + fn where fi indicates i’th Fibonacci number. Remember that f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5, …

    Input  : n = 3
    Output : 4
    Explanation : 0 + 1 + 1 + 2  = 4
    
    Input  :  n = 4
    Output :  7
    Explanation : 0 + 1 + 1 + 2 + 3  = 7
    

    Since the answer can be very large, answer modulo 1000000007 should be printed.

    Input:
    First line contains an integer, the number of test cases ‘T’ Each test case should contain a positive integer N.
    Output:
    Print sum of fibonacci numbers.
    Constraints:
    1 <=T<= 20000
    1 <= N <=100000
    Example:
    Input:
    2
    6
    5

    Output:
    20
    12

    Implementation: Python2.7
    Sum of first nth fibo

    #code
    def sum_first_100k_fibo():
        # this will be faster than
        # calculate and return first-100k-fibo-number list
        f1, f2 = 1, 2
        fibo = [f1, f2]
        yield f1
        yield f2
        while len(fibo) < 100000:
            f1, f2 = f2, f1+f2+1
            fibo.append(f2)
            yield f2
    
    if __name__ == '__main__':
        fibo = sum_first_100k_fibo()
        fibo_dict = []
        for i in range(100000):
            fibo_dict.append(fibo.next())
        t = input()
        for _ in range(t):
            n = input()
            print fibo_dict[n-1] % 1000000007 
    
    
    Advertisements
     
  • loctv 11:29 pm on January 12, 2017 Permalink | Reply
    Tags: ,   

    Problem: 1[0]1 Pattern Count 

    *Difficulty: Eazy

    Given a string, your task is to find the number of patterns of form 1[0]1 where [0] represents any number of zeroes (minimum requirement is one 0) there should not be any other character except 0 in the [0] sequence.

     

    Input:
    The first line contains T denoting the number of testcases. Then follows description of testcases. Each case contains a string.
    Output:
    For each test case, output the number of patterns.

     

    Constraints:
    1<=T<=20
    1<=Length of String<=2000
    Example:
    Input:
    2
    100001abc101
    1001ab010abc01001

     

    Output:
    2
    2

    Implementation: Python2.7

    def pattern_count(string):
        flag_index = string.find('1') # get the first '1' in string
        count = 0 # count number of patterns
        zero_between = 0 # count number of zero between two 1
        i = flag_index # start at first '1' in string
        while i < len(string) and i != -1:
            if string[i] == '0':
                zero_between += 1
            elif string[i] == '1':
                if zero_between > 0:
                    count += 1
                    zero_between = 0
                flag_index = i
            else:
                zero_between = 0
                flag_index = string.find('1', flag_index+1)
                i = flag_index
            i += 0 if i == -1 else 1
        print count
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            string = raw_input().strip()
            pattern_count(string)
            
    
    
     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel