7

I'm doing one of the challenges in Hackerrank as below:

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. The first line contains a single string, s. The second line contains an integer, n.

I will need to print a single integer denoting the number of the letter a’s in the first N letters of the infinite string created by repeating S infinitely many times.

For example:

s is 'aba', n = 10.. The first n = 10 letters of the infinite string are 'abaabaabaa...' Because there are 7 a’s, we'll get 7 as the final answer

This is my answer. It passed first two cases but failed the rest.

function repeatedString(s, n) {
    var repeat = Math.round(n / s.length);
    var remainder = n % s.length;
    var answer = 0;
    for (var i = 0; i < s.length; i++) {
        if (s.charAt(i) == 'a') {
            answer += repeat;
            if (i < remainder)
                answer++;
        }
    }
    return answer;
}

If someone could have a look at this and suggest a better solution that would be great.

2
  • 1
    the beauty of programming is to find the solution by trial, error. and using your head. i don't even understand the problem description here.
    – GottZ
    Nov 27, 2018 at 23:19
  • 2
    I would compute remainder first. Then subtract remainder from n and divide by s.length. That way you get the accurate integer quotient, without Math.round or Math.floor. Nov 28, 2018 at 1:28

27 Answers 27

7
//From a website i found it.

 const as = s.split("").filter(c => c === "a").length;
        const times = parseInt(n / s.length);
        const rest = n % s.length;

        const totalAs = times * as
            + s.slice(0, rest).split("").filter(c => c === "a").length

        return totalAs; 
1
  • I think we can use Math.floor() instead of parseInt() as Math.floor() makes some sense Feb 11, 2021 at 11:21
5

Anyone who wants to see the original question on HackerRank can do so here (included below as well). The problem statement is:

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

There are two parts to this.

  1. s is repeated "infinitely," but we only need to check up to length n.
  2. We will need to count the number of a's in that string.

Let's start with the simple problem first: Writing a function that counts the number of times a character is included in a string.

String.prototype.countCharacter = function(char) {
    return [...this].filter(c => c === char).length;
}

console.log('aaaa'.countCharacter('a')); // 4
console.log('aabb'.countCharacter('b')); // 2

Now here is the tricky part. We could naively use String.repeat() to repeat the string until it has length greater than n, but for arbitrarily large n, this becomes impractical. In fact, HackerRank gives us an n test case that is larger than the max string length, so we will need to take a higher-level approach.

We know how many a's are in the string s, which will be repeated - if we repeat it m times, we will have m * s.countCharacter('a') a's, where m > (n/l) and l is s.length. This is not as complicated as it might seem: We will need to repeat the string until we get a string of length greater than n, and we can store the number of times we will need to repeat the string to reach (or go over) n in a variable called repeatsRequired, which is just n / l rounded up.

From there, it's easy enough to tell how many characters that string has, and we can tell how many extra characters will be on the end with charactersRequired % l. If we know how many extra characters will be on the end, we can slice off the extra part of s and count the number of a's, and the total number of a's will be:

(number of a's in s) * (repeats required - 1)
+ (number of a's in final partial repeat)

String.prototype.countCharacter = function(char) {
  return [...this].filter(c => c === char).length;
}

// Complete the repeatedString function below.
function repeatedString(s, n) {

  const l = s.length,
        repeatsRequired = Math.ceil(n / l),
        charsRequired = repeatsRequired * l,
        numCharsInLastRepeat = l - (charsRequired % n);

  const a_s = s.countCharacter('a'),
        a_r = s.slice(0, numCharsInLastRepeat).countCharacter('a');

  return a_s * (repeatsRequired - 1) + a_r;
}

console.log(repeatedString('aba', 10)); // 7
console.log(repeatedString('a', 1000000000000)); // 1000000000000

HackerRank problem description.

1
  • Why the (repeatsRequired - 1) ?
    – Akhilesh
    Nov 22, 2021 at 17:44
3
function repeatedString(s, n) {
    return (s.match(/a/g) || []).length * Math.floor(n/s.length) + (s.substring(0, n % s.length).match(/a/g) || []).length;
}
1
  • This is a really cool one-liner. Thank you
    – Curtis M
    Dec 5, 2021 at 17:36
2

The first bug is that your call to Math.round should be Math.floor. You can verify that the code isn't working right because your code says that repeatedString('cat', 2) is 2, and it should be saying 1.

You should run several more sanity checks by hand before submitting it again.

1

Check out my answer, you could do it with two small functions in order to get a better performance. ALL TESTS PASS PROPERLY. I am attaching the benchmark comparing with other methods that use .split, .replace, .filter, .match

function countAs(str, ln) {
  let count = 0;
  for (let i = 0; i < ln; i++) {
    if (str[i] === 'a') {
      count++;
    }
  }
  return count;
}

function repeatedString(s, n) {
    return (
        countAs(s, s.length) * parseInt(n / s.length, 10) +
        countAs(s, n % s.length)
    );
}
1
function repeatedString(s,n) {

    if(s.includes('a')) {
  
      const sTotal = Math.floor(n / s.length); // repeated string total 
      const aCount = s.match(/a/g).length; // 'a' character count in s
      let aTotalCount = sTotal * aCount; // total 'a' count of repeated string pattern within number limit
      const remainingChar = n % s.length;  // remaining characters after repeating string within number limit
      
     // if there are remaining characters, add them to the total 'a' count. 
      if(remainingChar !== 0 && s.substr(0,remainingChar).includes('a')) {
          aTotalCount += s.substr(0,remainingChar).match(/a/g).length;
      }
        
      aTotalCount = Math.floor(aTotalCount);
      return aTotalCount;
    } 
    return 0;
}

This is what I came up with. Verified with Hacker Rank across all 22 test cases.

1
  • Please add the problem statement in the post
    – Liquidpie
    Apr 21, 2021 at 15:15
0

this problem appears to be a string problem but actually its just a math problem. Simple calculations. First calculate how many 'a' are there in the substring. Then id the length of the substring be a perfect factor of n, then length*(n/substrlength) is the ans. Else if its not a perfect factor then find how many 'a' are there in the remainder(n%substrlength) string , just add this to the initial result. //Code in C++

long len;
long i;
long count=0,c=0;
long fact=0;
len=s.length();
string s1=s;
for(i=0;i<s.length();i++)
{
    if(s[i]=='a')
    {
        count++;
    }
}
fact=n/len;
long sum=count*fact;
if(n%len==0)
{
    return sum;
}
else
{
    for(i=0;i<n%len;i++)
    {
        if(s[i]=='a')
        c++;
    }
    return sum+c;
}

}

0

I tried iteration but runtime error comes out. So the approach to go is using little math. Here's my code in Java.

    long left = n % s.length();
    long most = s.chars().filter(c -> (char) c == 'a').count();
    long last = s.substring(0, (int) left).chars().filter(c -> (char) c == 'a').count();
    long repeated = n / s.length();

    return most * repeated + last;
0

So this is my answer for this. Passes all the tests but it is not optimized obviously.

function repeatedString(s, n) {
    if (!s) {
        return 0;
    }

    if (!n) {
      return 0;
    }
    n = Number(n);
    const numOfA = s.split("").filter((e) => e === "a").length;
    const numOfLetters = s.length;
    const subStringOccurences =
      numOfLetters > 0 ? Math.floor(n / numOfLetters) : 0;
    const remaingOfLetters = n - (subStringOccurences * numOfLetters);
    const remaingA =
      remaingOfLetters > 0
        ? s
            .slice(0, remaingOfLetters)
            .split("")
            .filter((e) => e === "a").length
        : 0;
    return subStringOccurences * numOfA + remaingA;
}
0
static long repeatedString(String s, long n) {        
        long count =0;
        for(char c : s.toCharArray())
            if(c == 'a')
            count++;

         long factor = (n/s.length());
         long rem = (n%s.length());
         count =  factor*count  ;
        for(int i=0;i<rem;i++)
            if(s.charAt(i)=='a')
                    count++;  
            return count;
        
        }
1
  • While this code may provide a solution to the question, it's better to add context as to why/how it works. This can help future users learn, and apply that knowledge to their own code. You are also likely to have positive feedback from users in the form of upvotes, when the code is explained.
    – Borja
    Sep 11, 2020 at 11:58
0

The Below does pass every test case in java 8!!

static long repeatedString(String s, long n) {
        int size = s.length();
        long total = 0;
        int count = 0;
        for(int i =0;i<size;i++){
            if(s.charAt(i)=='a'){
                total++;
                if(i<(n % size))
                count++;
            }
        }
        long repeat = (long)n/size; 
        total = total*repeat;
        return total+count;

    }
0

Here's a brute force and non brute force approach

console.log(repeatedString('abab',1000))
console.log(repeatedStringBruteForce('abab',1000))

function repeatedStringBruteForce(s, n) {
    var stringLength = s.length;
    var charIndex = 0;
    for (var i = stringLength; i < n; i++) {
        s += s[charIndex];
        charIndex++;
    }

    return s.split('a').length - 1
}

function repeatedString(s, n) {
    // Get number of A's in original given string
    var aNum = s.split('a').length - 1;
    // Calculate number of given strings that fit into n
    var numOfStrings = Math.floor(n / s.length);
    // Get Total Number A's by multiplying the number of strings that fit by the number of A's in original string
    var totalAs = aNum * numOfStrings;
    // Now get the remainder string that couldnt fit
    var remainder = (n % s.length)/s.length;
    var leftOverStringLength = Math.floor(remainder * s.length);
    // Get the left over substring 
    var leftOverString = s.substring(0, leftOverStringLength);
    // Add any left over A's to our total A's
    totalAs += leftOverString.split('a').length - 1;

    return totalAs
}

0
const repeatedString = (s, n) => {
   const lengthOfS = s.length;
   const numberOfAInS = s.split('').filter(item => item === 'a').length;
   let aInRest = 0;
   if (n % lengthOfS !== 0) {
   aInRest = s
     .slice(0, n % lengthOfS)
     .split('')
     .filter(item => item === 'a').length;
   }
   return parseInt(n / lengthOfS) * numberOfAInS + aInRest;
};
0

I have recently taken this challenge solved it by first filtering out the pattern occurrence in the given string and multiplying it by the occurrence of the string. Step 2 is to check if string occurrences are completing and find the pattern in the substring if not completing:

function repeatedString(s, n) {
let count = s.split('').filter(el => el === 'a').length;
count *= Math.floor(n/s.length);

if ((n % s.length) !== 0) {
    const subStr = s.slice(0, n % s.length );
    const patterStr = subStr.split('').filter(el => el === 'a');
    count += patterStr.length;
}

return count;
}
0

``javascript`:

function repeatedString(s, n) {

        if (s.includes("a") && n > 0)
        {
            var m = (n / s.Length);
          
             let matchCnt = 0;


            matchCnt =  (s.match(/a/g) || []).length;
                

            
            if (s.Length == matchCnt)
            {
                return n;
            }
            else
            {
                if (n == s.Length)
                {
                    return matchCnt;
                }
                else if (n < s.length)
                {
                    var newStr = s.Remove(Convert.ToInt32(n));
                    var newStr = s.substring(n)
                    newStr = s.replace(newStr, "");
                    matchCnt =  (newStr.match(/a/g) || []).length;
                
                    return matchCnt;
                }
                else
                {
                    if (n % s.length == 0)
                    {
                        return matchCnt * n;
                    }
                    else if (n % s.length != 0)
                    {
                        var extra = n % s.length;

                          if (extra > 1)
                        {
                            return  (n / s.length) * matchCnt;
                        }
                        else
                        {
                            return extra + (n / s.length) * matchCnt;
                        }
                    }
                }
            }
        }
        return 0;
}

c # : public static long repeatedString(string s, long n) { char str = 'a';

        if (s.Contains("a") && n > 0)
        {
            var m = (Convert.ToDouble(n) / s.Length);
            var matchCnt = s.Count(x => x == str);
            if (s.Length == matchCnt)
            {
                return n;
            }
            else
            {
                if (n == s.Length)
                {
                    return matchCnt;
                }
                else if (n < s.Length)
                {
                    var newStr = s.Remove(Convert.ToInt32(n));
                    matchCnt = newStr.Count(x => x == str);
                    return matchCnt;
                }
                else
                {
                    if (n % s.Length == 0)
                    {
                        return matchCnt * n;
                    }
                    else if (n % s.Length != 0)
                    {
                        var extra = n % s.Length;

                          if (extra > 1)
                        {
                            return  (n / s.Length) * matchCnt;
                        }
                        else
                        {
                            return extra + (n / s.Length) * matchCnt;
                        }
                    }
                }
            }
        }
        return 0;
}
0

// O(n) simple javascript solution.

function repeatedString(s, n) {
    // Write your code here
    let remainStrLen = n%s.length;
    let countA =0;//in remaining String
    let numberA=0;//in the original
    for (let i=0;i<s.length;i++) {
        if (s[i]=='a') numberA++;
        if (s[i]=='a' && i<remainStrLen) countA++;
    }
    return Math.trunc(n/s.length)*numberA+countA;
}
0

function countCharacter(str, regex) {
  return str.length - str.replace(regex, '').length
}

function repeatedString(s, n) {
  const char = 'a'
  const regex = /a/g
  const len = s.length

  if (!n) {
    return 0
  }
  if (len === 1) {
    return s === char ? n : 0
  }

  const repeatCount = parseInt(n / len, 10) // will give a number of repeatation of string
  const remainingCharCount = s.substr(0, n % len) // get the left over string
  const strLen = countCharacter(s, regex) * repeatCount + countCharacter(remainingCharCount, regex)

  return strLen
}

repeatedString('aax', 10)

0

const findMultipleOfA = (str, num) => {
    const basic = str.match(/[a]/g).length;
    const multipleOf = Math.floor(num/str.length);
    let remainingAs = str.slice(0, num % str.length).match(/[a]/g);
    remainingAs = remainingAs ? remainingAs.length : 0;
    return basic * multipleOf + remainingAs;
}

function repeatedString(s, n) {
    let strVar = '';

    if(s.length === 1 && s === 'a') {
        return n
    }
    if(!s.includes('a')) return 0

    return findMultipleOfA(s, n)
}

-1
   long repeateCount=0;
int length =s.length();
long remainder=n%length;
int repeateCountForRemainder=0;

for(int i =0;i<length;i++){
    if(s.charAt(i)=='a'){
        repeateCount++;
    }
}

if(remainder !=0 && remainder>length){
    remainder=length;
}
for(int i =0;i< remainder;i++){

    if(s.charAt(i)=='a'){
        repeateCountForRemainder++;
    }
}

repeateCount = ((n-remainder)*repeateCount/length)+ repeateCountForRemainder;
-1
function repeatedString(s, n) {
  var noOfa = s.length - s.replace(/a/g, "").length;
  var r = n % (s.length);
  var remaining = (s.substring(0, r)).length - (s.substring(0, r)).replace(/a/g, "").length;

  return noOfa * (Math.floor(n / (s.length))) + remaining;
}
1
  • 6
    While this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value.
    – Vasilisa
    Feb 20, 2019 at 7:35
-1
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char s[101];
cin>>s;
long long n;
cin>>n;
int count=0;
for(int i=0;i<strlen(s);i++)
{
    if(s[i]=='a')
    count++;
}
long long d = (n/strlen(s))*count;
long long m = n%strlen(s);
for(int i=0;i<m;i++)
{
    if(s[i]=='a')
    d++;
}
cout<<d;
}
//Correctly working solution
1
  • 1
    Welcome to stackoverflow. Please add some text describing why your code snippet solves the OP's problem. For more info, check here: How to Answer
    – Djensen
    Jun 14, 2019 at 7:22
-1
let finalCounter;

if (s.length === 1 && s==='a') {
  return n;
} else if (s.length === 1 && s !=='a') {
  return 0;
}

const aCounter = (s.match(/a/g)||[]).length;
if (aCounter === 0) {
  return 0;
}
const times = Math.floor(n/s.length);
const counterExact = aCounter * times;
const remainCount = n%s.length;
const substr = s.substring(0, remainCount);
const extraCounter = (substr.match(/a/g)||[]).length;
finalCounter = counterExact+extraCounter;
return finalCounter;
-1
const computeNumOfReapitedA = (s) => {

    return s.split('').filter(character => {
        return character === 'a';
    });
};

const computeNumOfOccurrences = (s, numOfChars) => {

    let quotient = Math.floor(numOfChars/s.length);
    let remainder = numOfChars % s.length;

    return computeNumOfReapitedA(s).length * quotient + computeNumOfReapitedA(s.substr(0, 
           remainder)).length;  
};
-1

The below code worked for 5 test cases.

For the rest it failed throwing runtime error.

static long repeatedString(string s, long n)
{
    int count = 0, k = 0;
    do {
        n--;
        if (s[k] == 'a') {
            count++;
        }
        if (k==s.Length-1) {
            k = -1;   
        }
        k++;
    } while (n>=0);
        return count;
    }
}
-1
def repeatedString(s, n):

  aois = s.count('a')
  soq = math.floor(n/len(s))
  sol = n-(soq*len(s))
  sl= s[0:int(sol)]
  aoisl = sl.count('a')
  return int(((aois*soq)+aoisl))
1
  • Although this may be a better algorithm, unfortunately it's no JavaScript as OP asked for Jul 5, 2020 at 18:55
-2
    int l=s.length();
    String ne="";
    long value=0;
    if(l==1&&s.charAt(0)=='a')
    {
        value=n;
    }

    else
    {
        value=0;
        for(int i=0;i<=(n/l)+1;i++)
        {
            ne=ne+s;
        }
        for(int i=0;i<n;i++)
        {
            if(ne.charAt(i)=='a')
            {
                value++;
            }
        }
    }
    return value;
1
  • Please add some explanations Apr 6, 2019 at 3:58
-2
// Complete the repeatedString function below.
static long repeatedString(String s, long n) {
    long stringLength = s.length();
    char[] charArray = s.toCharArray();
    int count=0;
    if(s.equals("a")){
        return n;
    }
    for(char character : charArray){
        if(character == 'a'){
            count++;
        }
    }
    int rem = (int)(n % stringLength);
    count *= (n/stringLength);
    if(rem != 0){
        char[] subString = s.substring(0,rem).toCharArray();
        for(char character : subString){
            if(character == 'a'){
                count++;
            }
        }
    }
    return count;
}
2
  • Can you please add explanation how this resolves the issue? May 12, 2019 at 5:55
  • Problem is need to show count of a in repeated infinite string, it means u can take count of a in one string and u can multiply with number of repetitions In this there are two possibles where n is number of characters need to be repeat 1) n might be equals to 0 means n % stringLength = 0 2) n might not be equals to 0 then your solution should be count of characters contains in a string * n/stringLength + characters contains in remainder String length
    – techMan
    May 12, 2019 at 14:06

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