Facebook Interview Question Software Development Managers
Country: United States
def count_abc(n, nb, nc):
if n == 1:
return 1 + (1 if nb else 0) + (1 if nc else 0)
ret = count_abc(n-1, nb, nc)
if nb > 0:
c2 = count_abc(n-1, nb-1, nc)
ret += c2
if nc > 0:
c3 = count_abc(n-1, nb, nc-1)
ret += c3
return ret
if __name__ == '__main__':
print(count_abc(1, 1, 2))
print(count_abc(2, 1, 2))
print(count_abc(3, 1, 2))
print(count_abc(4, 1, 2))
print(count_abc(5, 1, 2))
print(count_abc(6, 1, 2))
print(count_abc(7, 1, 2))
print(count_abc(100, 1, 2))
```
#include <iostream>
using namespace std;
int helper(int n, int nb, int nc) {
if (n == 0)
return 1;
int result = helper(n-1, nb, nc);
if (nb > 0)
result += helper(n-1, nb-1, nc);
if (nc > 0)
result += helper(n-1, nb, nc-1);
return result;
}
int main () {
int n = 5;
int nb = 1;
int nc = 2;
cout << "Number of possible strings: " << helper(n, nb, nc) << "\n";
return 0;
}
```
I think this is a mathematical problem, what we need to do is to calculate all the number of possibilities, remove from it the occurrences of the not allowed doubles and triples.
Here is a simple Javascript code that may fix the problem.
The complexity of it is O(1)
Test cases were covered, n=1, n=2, n=3, n=4
n=1 => the output is 3
n=2 => the output is 8
n=3 => the output is 19
n=4 => the output is 39
let n = 4;
const buildingBlocksArray = ['a', 'b', 'c'];
let countTheNumberOfStrings = (wordsLength, buildingBlocksLength) => {
if(wordsLength === 1){
return buildingBlocksLength;
}
let getCountOfAllPoss = (wordsLength) => {
const countOfAll = Math.pow(buildingBlocksLength, wordsLength);
return countOfAll;
}
let countOfAll = getCountOfAllPoss(wordsLength);
let countOfDoubles = getCountOfAllPoss(wordsLength - 1) * (wordsLength - 1);
let countOfTriples = getCountOfAllPoss(wordsLength - 2) * (wordsLength - 2);
let notAllowedDoubles = countOfDoubles / 3;
let allowedTriples = countOfTriples / 3;
console.log('countOfAll =', countOfAll);
console.log('countOfDoubles =', countOfDoubles);
console.log('countOfTriples =', countOfTriples);
console.log('notAllowedDoubles =', notAllowedDoubles);
console.log('allowedTriples =', allowedTriples);
let finalResults = (countOfAll - notAllowedDoubles - countOfTriples) + allowedTriples;
if(wordsLength <= buildingBlocksLength){
return finalResults;
} else {
return finalResults - (buildingBlocksLength * (wordsLength - buildingBlocksLength))
}
}
console.log('finalResults =', countTheNumberOfStrings(n, buildingBlocksArray.length));
A straightforward DP problem
N = 10
dp = [[[1] * (N+1) for _ in [0,1]] for _ in [0,1,2]]
for l in range(1,N+1):
dp[2][1][l] = dp[2][1][l-1] + dp[2][0][l-1] + dp[1][1][l-1]
dp[1][1][l] = dp[1][1][l-1] + dp[1][0][l-1] + dp[0][1][l-1]
dp[0][1][l] = dp[0][1][l-1] + dp[0][0][l-1]
dp[2][0][l] = dp[2][0][l-1] + dp[1][0][l-1]
dp[1][0][l] = dp[1][0][l-1] + dp[0][0][l-1]
print (dp[2][1][N])
I think this can just be calculated (O(1)) (in code need to handle correctly cases of n < 3)
1+n+n+(n choose 2) + n*(n-1) + n*(n -1 choose 2)
1 - case of all As
n - case of all As and B
n - case of all As and C
(n choose 2) - case of all As and 2Cs
n*(n-1) - case of All As and B and C
n*(n -1 choose 2)- case of All As and B and 2 Cs
The problem is to output the total count of the strings that fit the criteria (length = n, bCount <= 1, cCount <=2)
Algorithm:
- Find all the possible combinations of aCount, bCount, cCount to form the string of length n;
Ex: n = 3 : aCount = 3, bCount = 0, cCount = 0; meaning there are 3 'a's, 0 'b' and 0 'c'in that string
aCount = 2, bCount = 1, cCount = 0;
aCount = 1, bCount = 1, cCount = 1;
.....
- Eliminate combinations that don't meet the criteria which is bCount <= 1 and cCount <= 2;
- For each combinations, calculate the number of distinct permutations
Ex: n = 4 : aCount = 2, bCount = 0, cCount = 2 ----> totalPermutations = n! / (aCount!*bCount!*cCount!) (This is a formulas for finding number of distict permutations)
In this case it would be 4!/(2!*0!*2!) = 6
- Add them all up to get the answer
Code:
public static int n = 4;
static void Main(string[] args)
{
string str = "";
int aCount = 0;
int bCount = 0;
int cCount = 0;
int answer = 0;
for (int a = 0; a <= n; a++)
{
aCount = a;
for (int b = 0; b <= n - aCount; b++)
{
bCount = b;
if (bCount > 1)
continue;
cCount = n - (aCount + bCount);
if (cCount > 2)
continue;
Console.WriteLine(aCount +" "+bCount+" "+cCount);
answer = answer + (Factorial(n) / (Factorial(aCount) * Factorial(bCount) * Factorial(cCount)));
}
}
Console.WriteLine(answer);
}
static int Factorial(int n)
{
int result = 1;
for (int i = 1; i <=n; i++)
{
result = result * i;
}
return result;
}
Output:
n = 1. Output: 3;
n = 2. Output: 8;
n = 3. Output: 19;
n = 4. Output: 39;
.
.
.
How about recursion, where the initial call is GetNumCombinations(n, empty string, allowedLetters) where allowedLetters is a hashmap in which the keys represent the allowed input letters, e.g. {a,b,c}, and their respective values the number of times they're allowed to be used, where -1 is unlimited, e.g. {-1,1,2}.
(Excuse my blend of code and pseudo-code)
int GetNumCombinations(int n, string s, hashmap[char,int] allowedLetters)
int totalCombinations = 0;
if size of s == n then
return 1;
else
for each allowedLetter in allowedLetters keys:
create copy of allowedLettershashmap: tempAllowedLetters
lookup allowedLetter in tempAllowedLetters:
if value == 1 then
remove mapping from tempAllowedLetters
else
subtract 1 from value in mapping
totalCombinations += GetTotalCombinations(n, s append allowedLetter, tempAllowedLetters);
return totalCombinations
How about recursion, where the initial call is GetNumCombinations(n, empty string, allowedLetters) where allowedLetters is a hashmap in which the keys represent the allowed input letters, e.g. [a,b,c], and their respective values the number of times they're allowed to be used, where -1 is unlimited, e.g. [-1,1,2].
int GetNumCombinations(int n, string s, hashmap[char,int] allowedLetters)
int totalCombinations = 0;
if size of s == n then
totalCombinations = 1;
else
for each allowedLetter in allowedLetters keys:
create copy of allowedLetters: tempAllowedLetters
lookup allowedLetter in tempAllowedLetters:
if value == 1 then
remove mapping from tempAllowedLetters
else
subtract 1 from value in mapping
totalCombinations += GetTotalCombinations(n, s append allowedLetter, tempAllowedLetters);
return totalCombinations;
How about recursion, where the initial call is GetNumCombinations(n, empty string, allowedLetters) where allowedLetters is a hashmap in which the keys represent the allowed input letters, e.g. {a,b,c}, and their respective values the number of times they're allowed to be used, where -1 is unlimited, e.g. {-1,1,2}.
int GetNumCombinations(int n, string s, hashmap[char,int] allowedLetters)
int totalCombinations = 0;
if size of s == n then
totalCombinations = 1;
else
for each allowedLetter in allowedLetters keys:
create copy of allowedLetters: tempAllowedLetters
lookup allowedLetter in tempAllowedLetters:
if value == 1 then
remove mapping from tempAllowedLetters
else
subtract 1 from value in mapping
totalCombinations += GetTotalCombinations(n, s append allowedLetter, tempAllowedLetters);
return totalCombinations;
function nStrings (n) {
var count = 0;
var possiblities = ['a', 'b', 'c'];
// / | \
// a b c
// /|\ /|\ \
// abc abc a
var recurse = function (stringSoFar, bs, cs) {
if(stringSoFar.length > n || bs > 1 || cs > 2) {
return;
} else if (stringSoFar.length === n) {
count ++;
return;
} else {
for(var i = 0; i < possiblities.length; i++) {
var b = 0;
var c = 0;
if(possiblities[i] === 'b') {
b = 1;
} else if (possiblities[i] === 'c') {
c = 1;
}
recurse(stringSoFar + possiblities[i], bs + b, cs + c);
}
}
};
recurse('', 0, 0);
return count;
}
// time O(n^n)
// space O(n^n)
#include <iostream>
using namespace std;
int helper(int n, int nb, int nc) {
if (n == 0)
return 1;
int result = helper(n-1, nb, nc);
if (nb > 0)
result += helper(n-1, nb-1, nc);
if (nc > 0)
result += helper(n-1, nb, nc-1);
return result;
}
int main () {
int n = 5;
int nb = 1;
int nc = 2;
cout << "Number of possible strings: " << helper(n, nb, nc) << "\n";
return 0;
}
here is the "generic solution". or at least, one version of it
static int big_o = 0;
static List<string> szOutStrings = new List<string>( );
static int helper( int n, int b, int [] LimitPerDigit, string szHeader )
{
// n == 0 === nothing. never gets here
// if we're the last digit (lenth 1), result is simply "are there still allowable #'s or not"
//
if ( n == 1 )
{
int resultZero = 0;
for ( int digit = 0 ; digit < b ; digit++ )
{
big_o++;
if ( LimitPerDigit [digit] > 0 )
{
resultZero++;
string szThis = ((char) ('a' + digit )).ToString( );
szOutStrings.Add( szHeader + szThis );
}
}
return resultZero;
}
// for each digit, if the digit is allowed, count up how many SUB-combinations are
// under that digit and add to total
int result = 0;
for ( int digit2 = 0 ; digit2 < b ; digit2++ )
{
if ( LimitPerDigit [digit2] > 0 )
{
// dock 1 for the limits per digit for this sub-inspection
LimitPerDigit [digit2]--;
string szThis = ((char) ('a' + digit2 )).ToString( );
result += helper( n - 1, b, LimitPerDigit, szHeader + szThis );
// then afterwards, bump it back up again
LimitPerDigit [digit2]++;
}
}
return result;
}
static void Main( string [] args )
{
int n = 10; // how many numbers
int b = 3; // what is the base
int [] LimitPerDigit = new int[b];
LimitPerDigit [1] = 1; // how many of each # can there be
LimitPerDigit [2] = 2;
LimitPerDigit [0] = n;
int result = helper( n, b, LimitPerDigit, "" );
Console.WriteLine( "total = " + result + ", big_o = " + big_o );
}
here's the solution showing each string as well
static int big_o = 0;
static List<string> szOutStrings = new List<string>( );
static int helper( int n, int b, int [] LimitPerDigit, string szHeader )
{
// n == 0 === nothing. never gets here
// if we're the last digit (lenth 1), result is simply "are there still allowable #'s or not"
//
if ( n == 1 )
{
int resultZero = 0;
for ( int digit = 0 ; digit < b ; digit++ )
{
big_o++;
if ( LimitPerDigit [digit] > 0 )
{
resultZero++;
string szThis = ((char) ('a' + digit )).ToString( );
szOutStrings.Add( szHeader + szThis );
}
}
return resultZero;
}
// for each digit, if the digit is allowed, count up how many SUB-combinations are
// under that digit and add to total
int result = 0;
for ( int digit2 = 0 ; digit2 < b ; digit2++ )
{
if ( LimitPerDigit [digit2] > 0 )
{
// dock 1 for the limits per digit for this sub-inspection
LimitPerDigit [digit2]--;
string szThis = ((char) ('a' + digit2 )).ToString( );
result += helper( n - 1, b, LimitPerDigit, szHeader + szThis );
// then afterwards, bump it back up again
LimitPerDigit [digit2]++;
}
}
return result;
}
static void Main( string [] args )
{
int n = 10; // how many numbers
int b = 3; // what is the base
int [] LimitPerDigit = new int[b];
LimitPerDigit [1] = 1; // how many of each # can there be
LimitPerDigit [2] = 2;
LimitPerDigit [0] = n;
int result = helper( n, b, LimitPerDigit, "" );
Console.WriteLine( "total = " + result + ", big_o = " + big_o );
}
int f(int l, int b, int c){
if(b<0 || c<0 || l<=0)
return 0;
if(l == 1){
if(b==0 && c==0)
return 1;
else if(b>0 && c >0)
return 3;
else
return 2;
}
else return f(l-1, b, c) + f(l-1, b-1, c) + f(l-1, b, c-1);
}
int main(){
cout<< f(n, 1, 2);
}
m = f(n, 1, 2)
1. first character is a
f(n-1, 1, 2)
2. first character is b
f(n-1, 0 2)
3. first character is c
f(n-1, 1, 1)
f(n, x, y) = f(n-1, x, y) + f(n-1, x-1, y) + f(n-1, x, y-1)
x=-1 or y=-1 -> f = 0
f(1, 0, 0) = 1
f(1, 1, 0) = 2
f(1, 0, 1) = 2
f(1, 0, 2) = 2
f(1, 1, 1) = 3
f(1, 1, 2) = 3
f(2, 1, 2) = f(1, 1, 2) + f(1, 0, 2) + f(1, 1, 1) = 3 + 2 + 3 = 8
f(2, 0, 2) = f(1, 0, 2) + f(1, -1, 2) + f(1, 1, 1) = 2 + 0 + 3 = 5
f(2, 1, 1) = f(1, 1, 1) + f(1, 0, 1) + f(1, 1, 0) = 3 + 2 + 2 = 7
f(3, 1, 2) = f(2, 1, 2) + f(2, 0, 2) + f(2, 1, 1) = 8 + 5 + 7 = 20
int f(int l, int b, int c){
if(b<0 || c<0 || l<=0)
return 0;
if(l == 1){
if(b==0 && c==0)
return 1;
else if(b>0 && c >0)
return 3;
else
return 2;
}
else return f(l-1, b, c) + f(l-1, b-1, c) + f(l-1, b, c-1);
}
int main(){
cout<< f(n, 1, 2);
}
m = f(n, 1, 2)
1. first character is a
f(n-1, 1, 2)
2. first character is b
f(n-1, 0 2)
3. first character is c
f(n-1, 1, 1)
f(n, x, y) = f(n-1, x, y) + f(n-1, x-1, y) + f(n-1, x, y-1)
x=-1 or y=-1 -> f = 0
f(1, 0, 0) = 1
f(1, 1, 0) = 2
f(1, 0, 1) = 2
f(1, 0, 2) = 2
f(1, 1, 1) = 3
f(1, 1, 2) = 3
f(2, 1, 2) = f(1, 1, 2) + f(1, 0, 2) + f(1, 1, 1) = 3 + 2 + 3 = 8
f(2, 0, 2) = f(1, 0, 2) + f(1, -1, 2) + f(1, 1, 1) = 2 + 0 + 3 = 5
f(2, 1, 1) = f(1, 1, 1) + f(1, 0, 1) + f(1, 1, 0) = 3 + 2 + 2 = 7
f(3, 1, 2) = f(2, 1, 2) + f(2, 0, 2) + f(2, 1, 1) = 8 + 5 + 7 = 20
## Given a length n, count the number of strings of length n that can be made
## using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.
s1 = "abbccabaabbccabaabbccaba"
n = 5
s2 = "abcbabcbcbaacbcbbacbacbc"
def count_str(s, n):
if n > len(s):
return -1
count = 0
my_dict = dict.fromkeys(list('abc'), 0)
for ch in s[:n]:
my_dict[ch] += 1
for index in range(len(s) - (n - 1)):
if my_dict['b'] <= 1 and my_dict['c'] <= 2:
count += 1
my_dict[s[index]] -= 1
if index + n < len(s):
my_dict[s[index + n]] += 1
return count
print(count_str(s1, n)) # 5
print(count_str(s2, n)) # 3
## Given a length n, count the number of strings of length n that can be made
## using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.
s1 = "abbccabaabbccabaabbccaba"
n = 5
s2 = "abcbabcbcbaacbcbbacbacbc"
def count_str(s, n):
if n > len(s):
return -1
count = 0
my_dict = dict.fromkeys(list('abc'), 0)
for ch in s[:n]:
my_dict[ch] += 1
for index in range(len(s) - (n - 1)):
if my_dict['b'] <= 1 and my_dict['c'] <= 2:
count += 1
my_dict[s[index]] -= 1
if index + n < len(s):
my_dict[s[index + n]] += 1
return count
print(count_str(s1, n)) # 5
print(count_str(s2, n)) # 3
class Solution {
public static void main(String[] args) {
int n = 6;
Map<String, Integer> alphabet = new HashMap<>();
alphabet.put("a", n);
alphabet.put("b", 1);
alphabet.put("c", 2);
List<String> allWords = new ArrayList<>();
addLetter(n, 0, "", alphabet, allWords);
for (String string : allWords) {
System.out.println(string);
}
System.out.println("The number of string is " + allWords.size());
}
private static void addLetter(int n, int ind, String prefix, Map<String, Integer> alphabet, List<String> allWords) {
if (ind == n) {
allWords.add(prefix);
return;
}
for (String letter : alphabet.keySet()) {
if (alphabet.get(letter) > 0) {
alphabet.put(letter, alphabet.get(letter) - 1);
addLetter(n, ind+1, prefix+letter, alphabet, allWords);
alphabet.put(letter, alphabet.get(letter) + 1);
}
}
}
}
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
class Solution {
public static void main(String[] args) {
List<String> res= genList(4);
System.out.println(res.size());
print(res);
}
public static void print(List<String> l){
for(String s: l){
System.out.println(s);
}
}
public static char[] chars= {'a','b','c'};
public static List<String> genList(int n){
List<String> res= new ArrayList<String>();
if(n<=0){
return res;
}
if(n>=1){
for(int j=0; j<chars.length; j++)
res.add(""+chars[j]);
}
for(int i=1;i< n; i++){
String[] tArray= new String[res.size()];
res.toArray(tArray);
res.clear();
for(int k=0; k<tArray.length;k++){
String ts = tArray[k];
for(int j=0;j <3; j++){
String ns =ts+chars[j];
if(validateS(ns))
res.add(ns);
}
}
}
return res;
}
public static boolean validateS(String s){
char[] cs= s.toCharArray();
int numb=0, numc=0;
for(char c: cs){
if(c=='b'){
numb++;
}
if(c=='c'){
numc++;
}
}
if(numb <=1 && numc<=2){
return true;
}
return false;
}
}
A simple O(1) algorism:
public class FB1 {
public static void main(String[] argu) {
for (int i=1; i<5; i++) {
BigInteger result = solve(i);
System.out.println(i +", result is " + result);
}
}
private static BigInteger solve(int n) {
return BigInteger.ONE.add(choose(n,1).multiply(BigInteger.valueOf(2))).add(choose(n,2)).add(choose(n,1).multiply(choose(n -1 ,1))).add(choose(n , 1).multiply(choose(n - 1, 2)));
}
private static BigInteger choose(int n, int k) {
BigInteger r = BigInteger.ONE;
for (int i=0; i<k; i++) {
r = r.multiply(BigInteger.valueOf(n - i));
}
for (int i=2; i<=k; i++) {
r = r.divide(BigInteger.valueOf(i));
}
// System.out.println(n + "," + k + " = " + r);
return r;
}
}
output:
1, result is 3
2, result is 8
3, result is 19
4, result is 39
int max_abc(int nA, int nB, int nC)
{
if ((nB < 0) || (nC < 0))
return 0;
if (nA == 0)
return 1;
if ((nB == 0) && (nC == 0))
return 1;
int res = max_abc(nA-1, nB, nC);
res += max_abc(nA-1, nB-1, nC);
res += max_abc(nA-1, nB, nC-1);
return res;
}
int main()
{
int nA =3, nB = 1, nC =2;
printf("max %d \n", max_abc(nA, nB, nC));
return 0;
}
int max_abc(int nA, int nB, int nC)
{
if ((nB < 0) || (nC < 0))
return 0;
if (nA == 0)
return 1;
if ((nB == 0) && (nC == 0))
return 1;
int res = max_abc(nA-1, nB, nC);
res += max_abc(nA-1, nB-1, nC);
res += max_abc(nA-1, nB, nC-1);
return res;
}
int main()
{
int nA =3, nB = 1, nC =2;
printf("max %d \n", max_abc(nA, nB, nC));
return 0;
}
/*
Find the number of strings of length 'n' that could be formed with letters
'a', 'b' and 'c', given the constraint that the letter 'b' could only be used once
and the letter 'c' could only be used twice.
*/
#include <iostream>
#include <vector>
using namespace std;
void fooCore(vector<char>& vec, int currIndex, int maxIndex, int& count, int& bCount, int& cCount)
{
if (currIndex > maxIndex)
{
++count;
return;
}
// for 'a'
vec[currIndex] = 'a';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, cCount);
// for 'b'
if (bCount == 1)
{
vec[currIndex] = 'b';
fooCore(vec, currIndex + 1, maxIndex, count, --bCount, cCount);
++bCount;
}
// for 'c'
if (cCount == 1 || cCount == 2)
{
vec[currIndex] = 'c';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, --cCount);
++cCount;
}
}
int foo(int n)
{
if (n <= 0)
{
return 0;
}
vector<char> vec;
vec.resize(n);
int count{};
int bMaxCount = 1;
int cMaxCount = 2;
fooCore(vec, 0, n - 1, count, bMaxCount, cMaxCount);
return count;
}
int main()
{
cout << foo(0) << '\n';
cout << foo(1) << '\n';
cout << foo(2) << '\n';
cout << foo(3) << '\n';
return 0;
}
/*
0
3
8
19
*/
/*
Find the number of strings of length 'n' that could be formed with letters
'a', 'b' and 'c', given the constraint that the letter 'b' could only be used once
and the letter 'c' could only be used twice.
*/
#include <iostream>
#include <vector>
using namespace std;
void fooCore(vector<char>& vec, int currIndex, int maxIndex, int& count, int& bCount, int& cCount)
{
if (currIndex > maxIndex)
{
++count;
return;
}
// for 'a'
vec[currIndex] = 'a';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, cCount);
// for 'b'
if (bCount == 1)
{
vec[currIndex] = 'b';
fooCore(vec, currIndex + 1, maxIndex, count, --bCount, cCount);
++bCount;
}
// for 'c'
if (cCount == 1 || cCount == 2)
{
vec[currIndex] = 'c';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, --cCount);
++cCount;
}
}
int foo(int n)
{
if (n <= 0)
{
return 0;
}
vector<char> vec;
vec.resize(n);
int count{};
int bMaxCount = 1;
int cMaxCount = 2;
fooCore(vec, 0, n - 1, count, bMaxCount, cMaxCount);
return count;
}
int main()
{
cout << foo(0) << '\n';
cout << foo(1) << '\n';
cout << foo(2) << '\n';
cout << foo(3) << '\n';
return 0;
}
/*
0
3
8
19
*/
def count_abc(n, nb, nc):
if n == 1:
return 1 + (1 if nb else 0) + (1 if nc else 0)
ret = count_abc(n-1, nb, nc)
if nb > 0:
c2 = count_abc(n-1, nb-1, nc)
ret += c2
if nc > 0:
c3 = count_abc(n-1, nb, nc-1)
ret += c3
return ret
if __name__ == '__main__':
print(count_abc(1, 1, 2))
print(count_abc(2, 1, 2))
print(count_abc(3, 1, 2))
print(count_abc(4, 1, 2))
print(count_abc(5, 1, 2))
print(count_abc(6, 1, 2))
print(count_abc(7, 1, 2))
print(count_abc(100, 1, 2))
This is a typical dynamic programing question.
public static int countWordsDynamic(int n, int bCount, int cCount) {
int[][][] counts = new int[n + 1][bCount + 1][cCount + 1];
for (int i = 0; i <= bCount; i++) {
for (int j = 0; j <= cCount; j++) {
counts[0][i][j] = 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= bCount; j++) {
for (int k = 0; k <= cCount; k++) {
counts[i][j][k] = counts[i - 1][j][k];
if (j > 0) {
counts[i][j][k] += counts[i - 1][j - 1][k];
}
if (k > 0) {
counts[i][j][k] += counts[i - 1][j][k - 1];
}
}
}
}
return counts[n][bCount][cCount];
}
You don't count the As, you count the Bs and the Cs.
0B-1C = n
1B-1C= n choose 2 = n(n-1)/2!
2B-1C = n choose 3 = n(n-1)(n-2)/3!
2B-0C = n choose 2 = n(n-1)/2!
1B-0C = n
0B -0C = 1
Sum = n(n-1) + 2n + 1 + n choose 3 = (6*n^2 + 6n + 6 + n^3 -3* n*2 + 2n) /6
= (n^3 + 3n^2 + 8n + 6)/6 = n(n-1)(n-2)/6 + n+1
This sum is an integer because n+1 is an integer and n(n-1)(n-2) is divisible by 3 and 2:-)
function countChar(str, char) {
let count = 0;
for (let i=0; i<str.length; i++) {
if (str[i] === char) {
count++;
}
}
return count;
}
function getStringsWithCharsInLengthN(n) {
let sum = 0;
let stringArr = [];
if (n >= 1) {
let newStringArr = ['a', 'b', 'c'];
for (let i = 1; i<n; i++) {
newStringArr.forEach((string)=> {
if (countChar(string, 'b') < 1) {
stringArr.push(string + 'b');
}
if (countChar(string, 'c') < 2) {
stringArr.push(string + 'c');
}
stringArr.push(string + 'a');
});
newStringArr = stringArr;
stringArr = [];
}
stringArr = newStringArr;
}
return stringArr.length;
}
console.log("Length for string with 1 character: " + getStringsWithCharsInLengthN(1));
console.log("Length for string with 2 characters: " + getStringsWithCharsInLengthN(2));
console.log("Length for string with 3 characters: " + getStringsWithCharsInLengthN(3));
console.log("Length for string with 4 characters: " + getStringsWithCharsInLengthN(4));
console.log("Length for string with 5 characters: " + getStringsWithCharsInLengthN(5));
console.log("Length for string with 6 characters: " + getStringsWithCharsInLengthN(6));
output:
Length for string with 1 character: 3
Length for string with 2 characters: 8
Length for string with 3 characters: 19
Length for string with 4 characters: 39
Length for string with 5 characters: 71
Length for string with 6 characters: 118
def findCounts(n, bcount, ccount):
if bcount < 0 or ccount < 0:
return 0
if n == 0: # no more chars left to be added
return 1
if bcount ==0 and ccount == 0:
return 1
res = findCounts(n-1,bcount, ccount) # if a is added
res += findCounts(n-1,bcount-1, ccount) # if b is added
res += findCounts(n-1, bcount, ccount-1) # if c is added
return res
print(findCounts(4,1,2))
# Given a length n, count the number of strings of length n that can be made
# using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.
def num_strings(n: int) -> int:
case_all_a = 1
case_c = n
case_b = n
case_cc = n * (n - 1) / 2 # divide by 2 since the order doesn't matter
case_cb = n * (n - 1)
case_ccb = n * (n - 1) * (n - 2) / 2
res = case_all_a
if n > 0:
res += case_c + case_b
if n > 1:
res += case_cc + case_cb
if n > 2:
res += case_ccb
return res
for i in range(5):
print(f"num_strings({i}) => {num_strings(i)}")
Code:
#include <iostream>
using namespace std;
// To execute C++, please define "int main()"
int factorial(int n)
{
if (n==0)
return 1;
else
return n*factorial(n-1);
}
void count_c(int n)
{
int aCount=0;
int bCount=0;
int cCount=0;
int Sum=0;
for (aCount=0;aCount < n+1; aCount++)
{
for (bCount=0;bCount < 2; bCount++)
{
for (cCount=0;cCount < 3;cCount++)
{
if (aCount+bCount+cCount == n)
{
Sum=Sum+(factorial(n)/ (factorial(aCount) * factorial(bCount) *factorial(cCount)));
}
}
}
}
cout<<Sum<<endl;
}
int main() {
int n=5;
count_c(n);
return 0;
}
{#include <iostream>
using namespace std;
// To execute C++, please define "int main()"
int factorial(int n)
{
if (n==0)
return 1;
else
return n*factorial(n-1);
}
void count_c(int n)
{
int aCount=0;
int bCount=0;
int cCount=0;
int Sum=0;
for (aCount=0;aCount < n+1; aCount++)
{
for (bCount=0;bCount < 2; bCount++)
{
for (cCount=0;cCount < 3;cCount++)
{
if (aCount+bCount+cCount == n)
{
Sum=Sum+(factorial(n)/ (factorial(aCount) * factorial(bCount) *factorial(cCount)));
}
}
}
}
cout<<Sum<<endl;
}
int main() {
int n=5;
count_c(n);
return 0;
}}
/*
Find the number of strings of length 'n' that could be formed with letters
'a', 'b' and 'c', given the constraint that the letter 'b' could only be used once
and the letter 'c' could only be used twice.
*/
#include <iostream>
#include <vector>
using namespace std;
void fooCore(vector<char>& vec, int currIndex, int maxIndex, int& count, int& bCount, int& cCount)
{
if (currIndex > maxIndex)
{
++count;
return;
}
// for 'a'
vec[currIndex] = 'a';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, cCount);
// for 'b'
if (bCount == 1)
{
vec[currIndex] = 'b';
fooCore(vec, currIndex + 1, maxIndex, count, --bCount, cCount);
++bCount;
}
// for 'c'
if (cCount == 1 || cCount == 2)
{
vec[currIndex] = 'c';
fooCore(vec, currIndex + 1, maxIndex, count, bCount, --cCount);
++cCount;
}
}
int foo(int n)
{
if (n <= 0)
{
return 0;
}
vector<char> vec;
vec.resize(n);
int count{};
int bMaxCount = 1;
int cMaxCount = 2;
fooCore(vec, 0, n - 1, count, bMaxCount, cMaxCount);
return count;
}
int main()
{
cout << foo(0) << '\n';
cout << foo(1) << '\n';
cout << foo(2) << '\n';
cout << foo(3) << '\n';
return 0;
}
/*
0
3
8
19
*/
geeksforgeeks count-strings-can-formed-using-b-c-given-constraints
- anoophky September 07, 2019