Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample Examples

Approach

Implementation in C++

3.1.

Complexity Analysis

Frequently Asked Questions-

Key takeaways

Last Updated: Mar 27, 2024

Greatest Sum Divisible by Three

Q: Q1. Give examples where dynamic programming can be applied?Ans- There are some examples where dynamic programming can be applied

Longest common subsequence0-1 KnapsackCoin change problem All pair shortest path problemReliability design problemWord break problemMatrix chain multiplication and many more.

Q: Q2. What are overlapping subproblems?

Ans- A problem has overlapping subproblems if it can be divided into smaller subproblems that are reused multiple times.

Author Ayush Tiwari

Introduction

This blog finds the maximum sum from the array such that the sum is divisible by three.

Problem Statement

You are given an array arr[] of length n contains integers, we need to find out the maximum possible sum of elements of the array such that it is divisible by three i.e you have to pick elements from an array whose sum is divisible by three and also sum is maximum.

Let's take some examples to understand this problem better.

Sample Examples

Example 1:

Given Array- arr[] = {1,2,3,4,4}
Output - 12

Explanation: Pick the numbers 1,3,4, and 4 whose sum is 12 and the sum is divisible by three.

Example 2:

Given Array- arr[ ] = {3,3,3,1,2}
Output - 12

Explanation: We can pick all elements sum is 12 and divisible by three.

Example 3:

Given Array- arr[ ] = {4}
Output - 0

Explanation: We cannot pick any element because 4 is not divisible by three.

Approach

The problem can easily be solved with dynamic programming. Lets first define our dynamic programing state dp[i][j], which stores the maximum sum that we can get using the first ‘i’ elements of the array and has remainder ‘j’, here we need sums divisible by 3 so j will be 0, 1, and 2.

why do we need all 3 values?

Let’s say we have the number 8 at ith index. 8 % 3 = 2

8 is not divisible by 3 and has remainder 2. so if we add 8 to the sum which has remainder 1

and these 2 will make a new sum which will be divisible by 3.

To handle cases like this, we need all three states in our dynamic programming.

The basic idea is as follows:

If let’s say we are at index ‘i’, and arr[i] % 3 = 2, then we do the following things,
1. arr[i] can be added with the dp[i-1][0] and this new sum will have remainder 2, so we will update dp[i][2].
2. arr[i] can be added with the dp[i-1][1] and this new sum will have a remainder of 0, so we will update dp[i][0].
3. arr[i] can be added with the dp[i-1][2] and this new sum will have remainder 1, so we will update dp[i][1].
If let’s say we are at index ‘i’, and arr[i] % 3 = 1, then we do the following things,
1. arr[i] can be added with the dp[i-1][0] and this new sum will have remainder 1, so we will update dp[i][1].
2. arr[i] can be added with the dp[i-1][1] and this new sum will have a remainder of 2, so we will update dp[i][2].
3. arr[i] can be added with the dp[i-1][2] and this new sum will have remainder 0, so we will update dp[i][0].
If let’s say we are at index ‘i’, and arr[i] % 3 = 0, then we do the following things,
1. arr[i] can be added with the dp[i-1][0] and this new sum will have remainder 0, so we will update dp[i][0].
2. arr[i] can be added with the dp[i-1][1] and this new sum will have a remainder of 1, so we will update dp[i][1].
3. arr[i] can be added with the dp[i-1][2] and this new sum will have remainder 2, so we will update dp[i][2].

Note: if dp[i-1][j] is zero then the other two sums will be considered only if they are greater than 0

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
// function to find maximum sum is divisble by three
int max_sum(int arr[], int n)
{
    int dp[n][3];
    memset(dp, 0, sizeof(dp));
    dp[0][arr[0] % 3] = arr[0];
    for (int i = 1; i < n; i++)
    {
        int num = arr[i];
        // if remainder is 0
        if (num % 3 == 0)
        {
            dp[i][0] = dp[i - 1][0] + num;
            dp[i][1] = dp[i - 1][1] > 0 ? dp[i - 1][1] + num : 0;
            dp[i][2] = dp[i - 1][2] > 0 ? dp[i - 1][2] + num : 0;
        }
        // if remainder is 1
        else if (num % 3 == 1)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] > 0 ? dp[i - 1][2] + num : 0);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + num);
            dp[i][2] = dp[i - 1][1] > 0 ? dp[i - 1][1] + num : 0;
        }
        // if remainder is 2
        else
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] > 0 ? dp[i - 1][1] + num : 0);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] > 0 ? dp[i - 1][2] + num : 0);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + num);
        }
    }
    return dp[n - 1][0];
}
// driver function
int main()
{
    int n;
    cin >> n; // number of elements in array
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    int ans = max_sum(arr, n);
    cout << "The Maximum sum is divisible by three is : " << ans;
}

Input:

5
1 2 3 4 4

Output:

The maximum sum is divisible by three is: 12

Complexity Analysis

Time complexity - O(N), O(n) for traversing the array once.

Space complexity - O(N). in the form of dp[][].

Frequently Asked Questions-

Q1. Give examples where dynamic programming can be applied?
Ans- There are some examples where dynamic programming can be applied

Longest common subsequence
0-1 Knapsack
Coin change problem
All pair shortest path problem
Reliability design problem
Word break problem
Matrix chain multiplication and many more.

Q2. What are overlapping subproblems?

Ans- A problem has overlapping subproblems if it can be divided into smaller subproblems that are reused multiple times.

Q3. Why do we use dynamic programming?
Ans- When we solve a problem with recursion, then generally, we make overlapping recursion calls which contribute to poor time complexity. Hence for escaping from these overlapping sub calls, we prefer to write code using DP.

Key takeaways

In this article, we’ve discussed the greatest sum divisible by three problem. Here an effective method has been used, which is called dynamic programming. This is a crucial topic, and there are numerous exciting problems related to this topic. Some of these are Tower of Hanoi, the rod cutting problem.

I would suggest you solve them to gain more confidence on this topic. These questions are asked during various coding contests as well as placements tests

To practice more such problems, Coding Ninjas Studio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

Coding and practicing in Code studio.

Keep Learning, Keep Going.

Happy Coding!