Directi Interview Question
Developer Program EngineersCountry: India
Interview Type: Phone Interview
public static int count(int n, int r, int g, int b){
int count = 0;
int x = n - (r+g+b);
if(x==0)
return fact(n)/(fact(r)*fact(g)*fact(b));
for(int i=0; i<=x; i++){
for(int j=0; j<=x-i; j++){
for(int k=0; k<=x-i-j; k++){
int p = r + i;
int q = g + j;
int s = b + k;
if(n == p+q+s)
count = count + fact(n)/(fact(p)*fact(q)*fact(s));
}
}
}
return count;
}
public static int fact(int n){
int count = 1;
for(int i=2; i<=n; i++){
count = count*i;
}
return count;
}
int Count(int n, int r, int g, int b)
{
vector<int> fact(n+1);
fact[0] = 1;
for (int i = 1 ; i <= n ; i++) {
fact[i] = fact[i-1]*i;
}
int remain = n - (r + g + b);
int sum = 0;
for (int i = 0 ; i <= remain ; i++) {
for (int j = 0 ; j <= remain-i ; j++) {
int k = remain - (i+j);
sum = sum + fact[n] / (fact[i+r]* fact[j+g]*fact[b+k]);
}
}
return sum;
}
int Count(int n, int r, int g, int b)
{
vector<int> fact(n+1);
fact[0] = 1;
for (int i = 1 ; i <= n ; i++) {
fact[i] = fact[i-1]*i;
}
int remain = n - (r + g + b);
int sum = 0;
for (int i = 0 ; i <= remain ; i++) {
for (int j = 0 ; j <= remain-i ; j++) {
int k = remain - (i+j);
sum = sum + fact[n] / (fact[i+r]* fact[j+g]*fact[b+k]);
}
}
return sum;
}
int Count(int n, int r, int g, int b)
{
vector<int> fact(n+1);
fact[0] = 1;
for (int i = 1 ; i <= n ; i++) {
fact[i] = fact[i-1]*i;
}
int remain = n - (r + g + b);
int sum = 0;
for (int i = 0 ; i <= remain ; i++) {
for (int j = 0 ; j <= remain-i ; j++) {
int k = remain - (i+j);
sum = sum + fact[n] / (fact[i+r]* fact[j+g]*fact[b+k]);
}
}
return sum;
}
I am not sure if this is the right solution but it give the right answer for the example.
Basically, distribute the 'extra' (i.e n - r - g - b) into the three types and for each such distribution calculate the number of permutations using multiset permutations.
package com.algo;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class StringOfSizeN {
private static final int numberOfWays(int r, int g, int b, int n) {
if (r + g + b > n) {
return -1;
}
int extras = n - (r + g + b);
List<List<Integer>> rgbs = getPartitions(extras, 3);
int sum = 0;
for (List<Integer> list : rgbs) {
int R = r + list.get(0);
int G = g + list.get(1);
int B = b + list.get(2);
sum += getCombosCount(n, R, G, B);
}
return sum;
}
private static int getCombosCount(int n, int r, int g, int b) {
return factorial(n) / (factorial(r) * factorial(g) * factorial(b));
}
private static Map<Integer, Integer> factorialCache = new HashMap<Integer, Integer>();
private static int factorial(int i) {
if (i <= 1) {
return 1;
}
if (factorialCache.containsKey(i)) {
return factorialCache.get(i);
} else {
int f = i * factorial(i - 1);
factorialCache.put(i, f);
return f;
}
}
private static List<List<Integer>> getPartitions(int extras, int n) {
if (n == 1) {
List<List<Integer>> l = new ArrayList<>();
List<Integer> l2 = new ArrayList<>();
l2.add(extras);
l.add(l2);
return l;
}
List<List<Integer>> allPartitions = new ArrayList<>();
for (int r = 0; r <= extras; r++) {
List<List<Integer>> l = getPartitions(extras - r, n - 1);
for (List<Integer> list : l) {
List<Integer> copy = new ArrayList<>(list);
copy.add(r);
allPartitions.add(copy);
}
}
return allPartitions;
}
public static void main(String[] args) {
System.out.println(StringOfSizeN.numberOfWays(1, 1, 1, 4));
}
}
solution in python.......
no of ways= fact(n)/(fact(p)*fact(q)*fact(s))
where p,q,s are no of characters of 3 types
# your code goes here
r=int(raw_input())
g=int(raw_input())
b=int(raw_input())
n=int(raw_input())
fact=[]
fact.append(1);
for i in range(1,1001):
fact.append(fact[i-1]*i)
def getPartitions(e,n):
l=[]
if n==1:
p=[]
p.append(e);
l.append(p)
return l
for i in range(0,e+1):
lt=getPartitions(e-i,n-1);
for j in lt:
j.append(i);
l.append(j);
return l
def ways(r,g,b,n):
sum=0;
l=getPartitions(n-r-g-b,3)
for i in l:
p=r+i[0]
q=g+i[1]
r=b+i[2]
print i
sum+=(((fact[n]/fact[p])/fact[q])/fact[r])
return sum
print ways(r,g,b,n);
import java.util.HashMap;
public class RGB {
public static HashMap<Integer,Long> factorialCache=new HashMap();
public static void main(String[] args) {
// TODO Auto-generated method stub
int r=2,g=2,b=1,n=5;
int e=n-(r+g+b),count=0;
//System.out.print("e="+e);
factorialCache.put(1,Long.parseLong("1"));
for(int i=2;i<=n;i++)
{
long f=i*factorialCache.get(i-1);
factorialCache.put(i,f);
}
//System.out.print("e="+factorialCache.get(6));
for(int i=0;i<=e;i++)
{
for(int j=0;j<=e;j++)
{
//for(int k=0;k<=e;k++)
{
int k=e-(i+j);
if(k<0) continue;
else
count+=ways(r+i,g+j,b+k,n);
}
}
}
System.out.print(count);
}
public static long ways(int r,int g,int b,int n)
{
return ((factorialCache.get(n)/factorialCache.get(r))/factorialCache.get(g))/factorialCache.get(b);
}
}
import java.util.*;
import java.io.*;
public class answer {
public static int fact(int n){
int factorial =1;
int i=1;
while (i<n+1){
factorial = factorial*i;
i++;
}
return factorial;
}
public static int ways(int n, int a, int b) {
return fact(n)/(fact(n-a-b)*fact(a)*fact(b));
}
public static void main (String args[]){
Scanner sc = new Scanner (System.in);
int n= sc.nextInt();
int a= sc.nextInt();
int b= sc.nextInt();
int c= sc.nextInt();
int ans = ways(n,a,b)+ ways(n,b,c) + ways(n,c,a);
System.out.println("Total no. of ways= "+ ans);
}
}
int Count(int n, int r, int g, int b)
{
vector<int> fact(n+1);
fact[0] = 1;
for (int i = 1 ; i <= n ; i++) {
fact[i] = fact[i-1]*i;
}
int remain = n - (r + g + b);
int sum = 0;
for (int i = 0 ; i <= remain ; i++) {
for (int j = 0 ; j <= remain-i ; j++) {
int k = remain - (i+j);
sum = sum + fact[n] / (fact[i+r]* fact[j+g]*fact[b+k]);
}
}
return sum;
}
- Himanshu Sahu July 19, 2015