Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
3.
Implementation in C++
3.1.
Complexity Analysis
4.
Frequently Asked Questions-
5.
Key takeaways
Last Updated: Mar 27, 2024

Greatest Sum Divisible by Three

Author Ayush Tiwari
1 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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:

  1. 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].
       
  2. 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].
       
  3.  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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!

Previous article
Maximum Area of the Square Submatrix
Next article
Maximal Square
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass