CODEWITHSUNDEEP
javascriptalgorithm
rory-h
rory-h

Reputation: 680

JS: Repeated string (Hackerrank Challenge)

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.

Upvotes: 7

Views: 17359

Answers (27)

Ibraheem Adeyemo
Ibraheem Adeyemo

Reputation: 62

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)
}

Upvotes: 0

ShriP
ShriP

Reputation: 128

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)

Upvotes: 0

Sam
Sam

Reputation: 11

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.

Upvotes: 1

Aashish tyagi
Aashish tyagi

Reputation: 26

// 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;
}

Upvotes: 0

divya bhavsar
divya bhavsar

Reputation: 64

``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;
}

Upvotes: 0

Apoorva Chikara
Apoorva Chikara

Reputation: 8773

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

Upvotes: 0

Mahfuz Ahmed
Mahfuz Ahmed

Reputation: 11

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

Upvotes: 0

Nathan Rawson
Nathan Rawson

Reputation: 1

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
}

Upvotes: 0

VMaz
VMaz

Reputation: 49

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;

    }

Upvotes: 0

am-sysout
am-sysout

Reputation: 37

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

Upvotes: 0

nikenson midi
nikenson midi

Reputation: 1

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

Upvotes: 0

Victor Barzana
Victor Barzana

Reputation: 11

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)
    );
}

Upvotes: 1

Guillermo Abbona
Guillermo Abbona

Reputation: 43

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;

Upvotes: 0

Lewis
Lewis

Reputation: 4595

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.

Upvotes: 5

Nabanita
Nabanita

Reputation: 1

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

}

Upvotes: 0

Aastha Sakshi
Aastha Sakshi

Reputation: 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))

Upvotes: -1

Tara Kant
Tara Kant

Reputation: 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;
    }
}

Upvotes: -1

JayK
JayK

Reputation: 181

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

Upvotes: 3

Reza
Reza

Reputation: 543

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

Upvotes: -1

Loay
Loay

Reputation: 226

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;

Upvotes: -1

jai
jai

Reputation: 547

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

Upvotes: 7

Vash S
Vash S

Reputation: 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

Upvotes: -1

techMan
techMan

Reputation: 1

// 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;
}

Upvotes: -2

Himanshu Rawat
Himanshu Rawat

Reputation: 1

    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;

Upvotes: -2

Narasingh
Narasingh

Reputation: 7

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

Upvotes: -1

Sankalp Pandya
Sankalp Pandya

Reputation: 187

   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;

Upvotes: -1

btilly
btilly

Reputation: 46409

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.

Upvotes: 2

Related Questions