3
\$\begingroup\$

Problem statement:

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 letter a's 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.

Function Description

Complete the repeatedString function in the editor below. It should return an integer representing the number of occurrences of a in the prefix of length n in the infinitely repeating string.

repeatedString has the following parameter(s):

s: a string to repeat
n: the number of characters to consider

Input Format The first line contains a single string, s. The second line contains an integer, n.

Output Format

Print a single integer denoting the number of letter a's in the first letters of the infinite string created by repeating infinitely many times.

Sample Input 0

aba
10

Sample Output 0

7

Explanation 0 The first letters of the infinite string are abaabaabaa. Because there are a's, we print on a new line.

Sample Input 1

a
1000000000000

Sample Output 1

1000000000000

Explanation 1 Because all of the first letters of the infinite string are a, we print on a new line.

My Solution:

def repeatedString(s: String, n: Long): Long = {

  def getCount(str: String): Int = str.groupBy(identity).get('a').map(x => x.length).getOrElse(0)

  val length= s.length
  val duplicate: Long = n / length
  val margin = n % length
  val numberOccurencesInString = getCount(s)
  val countInRepetetiveString = numberOccurencesInString * duplicate

  val numberOfOccurencesInStripedString = getCount(s.take(margin.toInt))

  countInRepetetiveString + numberOfOccurencesInStripedString
}
\$\endgroup\$
3
\$\begingroup\$

Your getCount() method is a little difficult to read, on one long line like that, and way too complicated. s.count(_ == 'a') is both concise and efficient.

It's not clear why the number of s repetitions possible in n is called duplicate. It seems an odd choice for that variable name.

Your algorithm is sound, I just find it excessively verbose, especially for a language that prides itself on being both expressive and concise.

val sLen = s.length
s.count(_ == 'a') * (n/sLen) + s.take((n%sLen).toInt).count(_ == 'a')
\$\endgroup\$
  • \$\begingroup\$ I have considered your suggestions and updated question accordingly. And thank you for the solution it is expressive(self explanatory). \$\endgroup\$ – Sandio Jul 16 at 21:38
0
\$\begingroup\$

(Disclamer: It's been quite a while that I used Scala.)

Your code is quite complicated. Scala provides the LazyList which allows to virtually repeat the string indefinitely. You then just need to "take" the n first characters, filter out the as and count them:

def repeatedString(s: String, n: Int) =
   LazyList.continually(s).flatten.take(n).filter(_ == 'a').size

(Edit: Changed n to an Int. Unfortunately this solution won't work if n is a Long.)

\$\endgroup\$
  • 1
    \$\begingroup\$ take takes Int as parameter. And we are passing Long value for Int. It is giving compiler error. Even if we use n.toInt, there is a possibility of loosing precision. Try Sample Input 1. \$\endgroup\$ – Sandio Jul 16 at 4:33
  • \$\begingroup\$ @Sandio Thanks for the info. \$\endgroup\$ – RoToRa Jul 16 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.