Question asked in one of my interview

Can anyone help me in this question. It was asked in one of my interview 3-4 months ago and i still don’t know the answer.

A box contain a number of chocolates that can only be removed 1 at a time or 3 at a time. How many ways can the box be emptied? The answer can be very large so return it modulo of 10^9+7.

for ex. n=7 chocolates initially they can be removed nine ways as follow:

(1,1,1,1,1,1,1)

(1,1,1,1,3)

(1,1,1,3,1)

(1,1,3,1,1)

(1,3,1,1,1)

(3,1,1,1,1)

(1,3,3)

(3,1,3)

(3,3,1)

1<=n<=10^9

Time limit 1 sec.

Input : n

output : as asked in question

Note : beware of limits of n

1 Like

Think of a DP solution, if a am not wrong, it is similar to the stair case problem with a modification.

2 Likes

I thought about the DP solution and did’t get anything but I think I got something else its like let say we have only one 3 in answer then two 3’s and so on… As 10^9<3^19 so we can do it now and for let say one 3(in our answer) condition we can find all possible answer(with only one 3) using xCy but the problem is xCy can be large so do you have any suggestion for this or how you think DP can be applied. Because N is too big.
Thanks btw

#include<iostream>
#include<climits>
#include<algorithm>
#define MAX 1000
using namespace std;

int noOfWays(int n, int dp[]){
	//Lookup
	if(dp[n]!=-1){
		return dp[n];
	}
	else{
		return dp[n] = noOfWays(n-1, dp)+noOfWays(n-3, dp);;
		
	}
}

int main(){
	int n; cin>>n;
	int dp[MAX];
	std::fill_n(dp, MAX, -1);
	
	// spl cases
	dp[0] = 1, dp[1]=1, dp[2]=1;
	
	cout<<noOfWays(n, dp)<<endl;
}

This is the logic. You can take care of constraints

#include <iostream>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define int long long
using namespace std;
const int MOD = 1000000007;

signed main() {
    FAST_IO;

    int n;
    cin >> n;
    int dp[n + 1];
    dp[0] = dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++) dp[i] = (dp[i - 1] + dp[i - 3]) % MOD;
    cout << dp[n];
    return 0;
}

Here, dp[i] is the number of ways you can remove i chocolates from the box.
If we have 0, 1 or 2 chocolates there is only 1 way to remove them. Those are our base cases.

1 Like

this problem can be done by the tabulisation like to reach from any number n we have to reach till 0 and you can fill 1-D table by reverse or by front i am filling it by reverse let say i want the number of ways to reach till i from n so i can reach i from only i+1 or from i+3 because we have to removed 3 or 1 element to reach till any number i as given in question so after reaching i we will calculate number of ways to reach i+1 and i+3 and add them that is the total way to reach the i from n and we will do it till we reach the 0 and our anser in the zero index…
lets dry run your test case for n==7
i start index 7 as 1 because there is only one way to reach 7 from 7 and calculate till 0

These solutions will exceed the time limit. n <= 10^9, so he wants somewhat like a O(log(n)) approach, with O(1) space complexity.

Are you asking for a solution better than O(n)?

Yes, he is. That should be clarified when you read the problem constraints. O(n) will lead to a TLE verdict. I am currently thinking of how to approach the problem. It should be based upon combinatorics.

1 Like

yeah exactly and I tried combinatorics approach(during the interview) but stuck somewhere.

I guess what they did is they modified the fibonacci problem. Maybe searching up how to calculate nth fibonacci number where n <= 10^9, in O(1) time might help you.

The combination series i got was horrible XD

1 Like

Basically the question is:

dp[x] = dp[x - 1] + dp[x - 3]

We have to compute this in O(log n) time.

Our main aim is to represent dp[x] as (dp[0] * a + dp[1] * b) % (10^9 + 7), where a and b are whole numbers.

Basically, the answer will be a + b, as dp[0] = 1, and dp[1] = 1

So basically, if we go,
dp[2] = dp[0] * 0 + dp[1] * 1
dp[3] = dp[0] * 1 + dp[2] = dp[0] * 1 + dp[1] * 1
dp[4] = dp[0] * 1 + dp[1] * 2

Like this, I am sure you will find a pattern to find a and b in the representation of dp[x].

Note: You don’t have to make the array, array is just for your understanding.

1 Like

dp[n] = \begin{bmatrix}1 & 1 &1 \end{bmatrix}\times \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0& 1 & 1\end{bmatrix}^n.

7 Likes

how is 3,3,3 a way to remove 7 chocolates?

We would have to use Matrix exponentiation .
Refer to https://www.google.com/amp/s/www.geeksforgeeks.org/matrix-exponentiation/amp/

1 Like

import java.util.*;
class hello
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
long n = sc.nextInt();
long C3sub = 3;
long totalways = 0;
for(long x = 1; x <= (n-(n/3)); x++)
{
totalways = totalways + ((fact((n-C3sub)+(C3sub/3)))/(fact(n-C3sub)*fact(C3sub/3)));
C3sub = C3sub + 3;
}
totalways=totalways+1;
System.out.println("Total ways= " +totalways);
}
static long fact(long k)
{
long i,fact=1;

for(i=1;i<=k;i++){
fact=fact*i;}
return fact;
}
}

Yeah my bad it was 3 3 1, I edited that

my solution is running till 32 chocolates but after that i think calculations become too big and it gives an error

Can you explain it because I don’t know java