Short Problem Definition:
Lilah has a string, s, of lowercase English letters that she repeated infinitely many times. Given an integer, n, find and print the number of letters a
in the first n letters of Lilah’s infinite string.
For example, if the string s = ‘abcac’ and n = 10, the substring we consider is abcacabcac, the first 10 characters of her infinite string. There are 4 occurrences of a
in the substring.
Link
Complexity:
time complexity is O(N)
space complexity is O(1)
Execution:
As with most simple problems, there are many ways to write the code that can achieve the correct result. I picked the one that seems the simplest and most Pythonesque.
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#!/bin/python import math import os import random import re import sys # Complete the repeatedString function below. def repeatedString(s, n): n_per_string = s.count( 'a' ) n_per_substring = s[ 0 :n % len (s)].count( 'a' ) return n_per_string * (n / len (s)) + n_per_substring if __name__ = = '__main__' : fptr = open (os.environ[ 'OUTPUT_PATH' ], 'w' ) s = raw_input () n = int ( raw_input ()) result = repeatedString(s, n) fptr.write( str (result) + 'n' ) fptr.close() |