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.
s
is repeated "infinitely," but we only need to check up to length n
.
- 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

remainder
first. Then subtractremainder
fromn
and divide bys.length
. That way you get the accurate integer quotient, withoutMath.round
orMath.floor
.