Given an integer n and a range [l, r], the task is to find the count of total sub-sets of size n with integers from the given range such that the total sum of its elements is divisible by 3.
Examples:
Input: n = 2, l = 1, r = 5
Output: 9
Possible sub-sets are {1, 2}, {2, 1}, {3, 3}, {5, 1}, {1, 5}, {4, 2}, {2, 4}, {5, 4} and {4, 5}
Input: n = 3, l = 9, r = 9
Output: 1
{9, 9, 9} is the only possible sub-set
Approach: Since we need the sum of the sub-set elements to be divisible by 3. So, instead of caring about the numbers, we will count the numbers such that they give remainder 0, 1 and 2 on dividing with 3 separately by the formula given below:
For example, an element k such that k % 3 = 2 can be found as k = 3 * x + 2 for some integer x.
Then we have l ? (3 * x) + 2 ? r
l – 2 ? (3 * x) ? r – 2
ceil((l – 2) / 3) ? x ? floor((r – 2) / 3)
Now, by dynamic programming dp[i][j] we can check how many elements will give a sum that is divisible by 3. Here dp[i][j] represents the sum of first i elements that give remainder j on dividing by 3.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define MOD 1000000007#define ll long long intusing namespace std;// Function to return the total number of // required sub-setsint totalSubSets(ll n, ll l, ll r){ // Variable to store total elements // which on dividing by 3 give // remainder 0, 1 and 2 respectively ll zero = floor((double)r / 3) - ceil((double)l / 3) + 1; ll one = floor((double)(r - 1) / 3) - ceil((double)(l - 1) / 3) + 1; ll two = floor((double)(r - 2) / 3) - ceil((double)(l - 2) / 3) + 1; // Create a dp table ll dp[n][3]; memset(dp, 0, sizeof(dp)); dp[0][0] = zero; dp[0][1] = one; dp[0][2] = two; // Process for n states and store // the sum (mod 3) for 0, 1 and 2 for (ll i = 1; i < n; ++i) { // Use of MOD for large numbers dp[i][0] = ((dp[i - 1][0] * zero) + (dp[i - 1][1] * two) + (dp[i - 1][2] * one)) % MOD; dp[i][1] = ((dp[i - 1][0] * one) + (dp[i - 1][1] * zero) + (dp[i - 1][2] * two)) % MOD; dp[i][2] = ((dp[i - 1][0] * two) + (dp[i - 1][1] * one) + (dp[i - 1][2] * zero)) % MOD; } // Final answer store at dp[n - 1][0] return dp[n - 1][0];}// Driver Programint main(){ ll n = 5; ll l = 10; ll r = 100; cout << totalSubSets(n, l, r); return 0;} |
Java
// Java implementation of the approachclass GFG{ static int MOD = 1000000007; // Function to return the total number of // required sub-sets static int totalSubSets(int n, int l, int r) { // Variable to store total elements // which on dividing by 3 give // remainder 0, 1 and 2 respectively int zero = (int)Math.floor((double)r / 3) - (int)Math.ceil((double)l / 3) + 1; int one = (int)Math.floor((double)(r - 1) / 3) - (int)Math.ceil((double)(l - 1) / 3) + 1; int two = (int)Math.floor((double)(r - 2) / 3) - (int)Math.ceil((double)(l - 2) / 3) + 1; // Create a dp table int [][] dp = new int[n][3]; dp[0][0] = zero; dp[0][1] = one; dp[0][2] = two; // Process for n states and store // the sum (mod 3) for 0, 1 and 2 for (int i = 1; i < n; ++i) { // Use of MOD for large numbers dp[i][0] = ((dp[i - 1][0] * zero) + (dp[i - 1][1] * two) + (dp[i - 1][2] * one)) % MOD; dp[i][1] = ((dp[i - 1][0] * one) + (dp[i - 1][1] * zero) + (dp[i - 1][2] * two)) % MOD; dp[i][2] = ((dp[i - 1][0] * two) + (dp[i - 1][1] * one) + (dp[i - 1][2] * zero)) % MOD; } // Final answer store at dp[n - 1][0] return dp[n - 1][0]; } // Driver Program public static void main(String []args) { int n = 5; int l = 10; int r = 100; System.out.println(totalSubSets(n, l, r)); }}// This code is contributed by ihritik |
Python3
# Python3 implementation of the approach import math# Function to return the total# number of required sub-sets def totalSubSets(n, l, r): MOD = 1000000007 ; # Variable to store total elements # which on dividing by 3 give # remainder 0, 1 and 2 respectively zero = (math.floor(r / 3) - math.ceil(l / 3) + 1); one = (math.floor((r - 1) / 3) - math.ceil((l - 1) / 3) + 1); two = (math.floor((r - 2) / 3) - math.ceil((l - 2) / 3) + 1); # Create a dp table dp = [[0 for x in range(3)] for y in range(n)] dp[0][0] = zero; dp[0][1] = one; dp[0][2] = two; # Process for n states and store # the sum (mod 3) for 0, 1 and 2 for i in range(1, n): # Use of MOD for large numbers dp[i][0] = ((dp[i - 1][0] * zero) + (dp[i - 1][1] * two) + (dp[i - 1][2] * one)) % MOD; dp[i][1] = ((dp[i - 1][0] * one) + (dp[i - 1][1] * zero) + (dp[i - 1][2] * two)) % MOD; dp[i][2] = ((dp[i - 1][0] * two)+ (dp[i - 1][1] * one) + (dp[i - 1][2] * zero)) % MOD; # Final answer store at dp[n - 1][0] return dp[n - 1][0];# Driver Coden = 5; l = 10; r = 100; print(totalSubSets(n, l, r)); # This code is contributed# by chandan_jnu |
C#
// C# implementation of the approachusing System;class GFG{ static int MOD = 1000000007; // Function to return the total number of // required sub-sets static int totalSubSets(int n, int l, int r) { // Variable to store total elements // which on dividing by 3 give // remainder 0, 1 and 2 respectively int zero = (int)Math.Floor((double)r / 3) - (int)Math.Ceiling((double)l / 3) + 1; int one = (int)Math.Floor((double)(r - 1) / 3) - (int)Math.Ceiling((double)(l - 1) / 3) + 1; int two = (int)Math.Floor((double)(r - 2) / 3) - (int)Math.Ceiling((double)(l - 2) / 3) + 1; // Create a dp table int [, ] dp = new int[n, 3]; dp[0,0] = zero; dp[0,1] = one; dp[0,2] = two; // Process for n states and store // the sum (mod 3) for 0, 1 and 2 for (int i = 1; i < n; ++i) { // Use of MOD for large numbers dp[i,0] = ((dp[i - 1, 0] * zero) + (dp[i - 1, 1] * two) + (dp[i - 1, 2] * one)) % MOD; dp[i,1] = ((dp[i - 1, 0] * one) + (dp[i - 1, 1] * zero) + (dp[i - 1, 2] * two)) % MOD; dp[i,2] = ((dp[i - 1, 0] * two) + (dp[i - 1, 1] * one) + (dp[i - 1, 2] * zero)) % MOD; } // Final answer store at dp[n - 1,0] return dp[n - 1, 0]; } // Driver Program public static void Main() { int n = 5; int l = 10; int r = 100; Console.WriteLine(totalSubSets(n, l, r)); }}// This code is contributed by ihritik |
Javascript
<script> // JavaScript implementation of the approach let MOD = 1000000007; // Function to return the total number of // required sub-sets function totalSubSets(n, l, r) { // Variable to store total elements // which on dividing by 3 give // remainder 0, 1 and 2 respectively let zero = Math.floor(r / 3) - Math.ceil(l / 3) + 1; let one = Math.floor((r - 1) / 3) - Math.ceil((l - 1) / 3) + 1; let two = Math.floor((r - 2) / 3) - Math.ceil((l - 2) / 3) + 1; // Create a dp table let dp = new Array(n); for(let i = 0; i < n; i++) { dp[i] = new Array(3); for(let j = 0; j < 3; j++) { dp[i][j] = 0; } } dp[0][0] = zero; dp[0][1] = one; dp[0][2] = two; // Process for n states and store // the sum (mod 3) for 0, 1 and 2 for (let i = 1; i < n; ++i) { // Use of MOD for large numbers dp[i][0] = ((dp[i - 1][0] * zero) + (dp[i - 1][1] * two) + (dp[i - 1][2] * one)) % MOD; dp[i][1] = ((dp[i - 1][0] * one) + (dp[i - 1][1] * zero) + (dp[i - 1][2] * two)) % MOD; dp[i][2] = ((dp[i - 1][0] * two) + (dp[i - 1][1] * one) + (dp[i - 1][2] * zero)) % MOD; } // Final answer store at dp[n - 1][0] return dp[n - 1][0]; } let n = 5; let l = 10; let r = 100; document.write(totalSubSets(n, l, r)); </script> |
PHP
<?php# Php implementation of the approach # Function to return the total number of # required sub-sets function totalSubSets($n, $l, $r) { $MOD = 1000000007 ; // Variable to store total elements // which on dividing by 3 give // remainder 0, 1 and 2 respectively $zero = floor($r / 3) - ceil($l / 3) + 1; $one = floor(($r - 1) / 3) - ceil(($l - 1) / 3) + 1; $two = floor(($r - 2) / 3) - ceil(($l - 2) / 3) + 1; // Create a dp table $dp = array() ; for($i = 0; $i < $n; $i++) for($j = 0; $j < 3; $j++) $dp[$i][$j] = 0 ; $dp[0][0] = $zero; $dp[0][1] = $one; $dp[0][2] = $two; // Process for n states and store // the sum (mod 3) for 0, 1 and 2 for ($i = 1; $i < $n; ++$i) { // Use of MOD for large numbers $dp[$i][0] = (($dp[$i - 1][0] * $zero) + ($dp[$i - 1][1] * $two) + ($dp[$i - 1][2] * $one)) % $MOD; $dp[$i][1] = (($dp[$i - 1][0] * $one) + ($dp[$i - 1][1] * $zero) + ($dp[$i - 1][2] * $two)) % $MOD; $dp[$i][2] = (($dp[$i - 1][0] * $two) + ($dp[$i - 1][1] * $one) + ($dp[$i - 1][2] * $zero)) % $MOD; } // Final answer store at dp[n - 1][0] return $dp[$n - 1][0]; } // Driver Program $n = 5; $l = 10; $r = 100; echo totalSubSets($n, $l, $r); // This code is contributed by Ryuga?> |
Output
80107136
Time Complexity: O(n)
Auxiliary Space: O(n), since n extra space has been taken.
Efficient approach : Space optimization O(1)
To optimize the space complexity of the previous code, we can observe that we only need to keep track of the sum (mod 3) of the previous state, i.e., dp[i-1][0], dp[i-1][1], and dp[i-1][2], to compute the sum (mod 3) of the current state dp[i][0], dp[i][1], and dp[i][2]. Hence, we can replace the 2D dp array with three variables sum0, sum1, and sum2 to keep track of the sum (mod 3) of the previous state.
Implementation Steps:
- Create variable zero ,one and two to store total elements which on dividing by 3 give remainder 0, 1 and 2 respectively .
- Now Initialize the sum (mod 3) of the previous state sum0, sum1 and sum2.
- Now iterate over subproblems and update current values.
- After every iteration update sum0, sum1 and sum2 for further iterations.
- At last return final answer stored in sum0.
Implementation:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define MOD 1000000007#define ll long long intusing namespace std;// Function to return the total number of// required sub-setsint totalSubSets(ll n, ll l, ll r){ // Variable to store total elements // which on dividing by 3 give // remainder 0, 1 and 2 respectively ll zero = floor((double)r / 3) - ceil((double)l / 3) + 1; ll one = floor((double)(r - 1) / 3) - ceil((double)(l - 1) / 3) + 1; ll two = floor((double)(r - 2) / 3) - ceil((double)(l - 2) / 3) + 1; // Initialize the sum (mod 3) of the previous state ll sum0 = zero, sum1 = one, sum2 = two; // Process for n states and store // the sum (mod 3) for 0, 1 and 2 for (ll i = 1; i < n; ++i) { // Compute the sum (mod 3) of the current state ll curSum0 = ((sum0 * zero) + (sum1 * two) + (sum2 * one)) % MOD; ll curSum1 = ((sum0 * one) + (sum1 * zero) + (sum2 * two)) % MOD; ll curSum2 = ((sum0 * two) + (sum1 * one) + (sum2 * zero)) % MOD; // Update the sum (mod 3) of the previous state sum0 = curSum0; sum1 = curSum1; sum2 = curSum2; } // Final answer is stored in sum0 return sum0;}// Driver Programint main(){ ll n = 5; ll l = 10; ll r = 100; cout << totalSubSets(n, l, r); return 0;} |
Java
import java.util.*;public class Main { static final int MOD = 1000000007; // Function to return the total number of // required sub-sets static int totalSubSets(long n, long l, long r) { // Variable to store total elements // which on dividing by 3 give // remainder 0, 1 and 2 respectively long zero = (long)Math.floor((double)r / 3) - (long)Math.ceil((double)l / 3) + 1; long one = (long)Math.floor((double)(r - 1) / 3) - (long)Math.ceil((double)(l - 1) / 3) + 1; long two = (long)Math.floor((double)(r - 2) / 3) - (long)Math.ceil((double)(l - 2) / 3) + 1; // Initialize the sum (mod 3) of the previous state long sum0 = zero, sum1 = one, sum2 = two; // Process for n states and store // the sum (mod 3) for 0, 1 and 2 for (long i = 1; i < n; ++i) { // Compute the sum (mod 3) of the current state long curSum0 = ((sum0 * zero) + (sum1 * two) + (sum2 * one)) % MOD; long curSum1 = ((sum0 * one) + (sum1 * zero) + (sum2 * two)) % MOD; long curSum2 = ((sum0 * two) + (sum1 * one) + (sum2 * zero)) % MOD; // Update the sum (mod 3) of the previous state sum0 = curSum0; sum1 = curSum1; sum2 = curSum2; } // Final answer is stored in sum0 return (int)sum0; } // Driver Program public static void main(String[] args) { long n = 5; long l = 10; long r = 100; System.out.println(totalSubSets(n, l, r)); }} |
Python3
MOD = 1000000007# Function to calculate the total number of subsetsdef totalSubSets(n, l, r): zero = (r // 3) - ((l - 1) // 3) one = ((r - 1) // 3) - ((l - 2) // 3) two = ((r - 2) // 3) - ((l - 3) // 3) # Initialize the sum sum0 = zero sum1 = one sum2 = two # Iterate for each index from 1 to n (exclusive) for i in range(1, n): curSum0 = ((sum0 * zero) + (sum1 * two) + (sum2 * one)) % MOD curSum1 = ((sum0 * one) + (sum1 * zero) + (sum2 * two)) % MOD curSum2 = ((sum0 * two) + (sum1 * one) + (sum2 * zero)) % MOD # Update the sums for the next iteration sum0 = curSum0 sum1 = curSum1 sum2 = curSum2 return sum0# Driver coden = 5l = 10r = 100print("Total number of subsets:", totalSubSets(n, l, r)) |
C#
using System;public class Program{ const long MOD = 1000000007; static long TotalSubSets(long n, long l, long r) { // Variable to store total elements // which on dividing by 3 give // remainder 0, 1 and 2 respectively long zero = (long)Math.Floor((double)r / 3) - (long)Math.Ceiling((double)l / 3) + 1; long one = (long)Math.Floor((double)(r - 1) / 3) - (long)Math.Ceiling((double)(l - 1) / 3) + 1; long two = (long)Math.Floor((double)(r - 2) / 3) - (long)Math.Ceiling((double)(l - 2) / 3) + 1; // Initialize the sum (mod 3) of the previous state long sum0 = zero, sum1 = one, sum2 = two; // Process for n states and store // the sum (mod 3) for 0, 1 and 2 for (long i = 1; i < n; ++i) { // Compute the sum (mod 3) of the current state long curSum0 = ((sum0 * zero) + (sum1 * two) + (sum2 * one)) % MOD; long curSum1 = ((sum0 * one) + (sum1 * zero) + (sum2 * two)) % MOD; long curSum2 = ((sum0 * two) + (sum1 * one) + (sum2 * zero)) % MOD; // Update the sum (mod 3) of the previous state sum0 = curSum0; sum1 = curSum1; sum2 = curSum2; } // Final answer is stored in sum0 return (int)sum0; } public static void Main() { long n = 5; long l = 10; long r = 100; Console.WriteLine(TotalSubSets(n, l, r)); }} |
Javascript
// Function to return the total number of required sub-setsfunction totalSubSets(n, l, r) { const MOD = 1000000007; // Variable to store total elements // which on dividing by 3 give // remainder 0, 1, and 2 respectively const zero = Math.floor(r / 3) - Math.ceil(l / 3) + 1; const one = Math.floor((r - 1) / 3) - Math.ceil((l - 1) / 3) + 1; const two = Math.floor((r - 2) / 3) - Math.ceil((l - 2) / 3) + 1; // Initialize the sum (mod 3) of the previous state let sum0 = zero, sum1 = one, sum2 = two; // Process for n states and store // the sum (mod 3) for 0, 1, and 2 for (let i = 1; i < n; ++i) { // Compute the sum (mod 3) of the current state const curSum0 = ((sum0 * zero) + (sum1 * two) + (sum2 * one)) % MOD; const curSum1 = ((sum0 * one) + (sum1 * zero) + (sum2 * two)) % MOD; const curSum2 = ((sum0 * two) + (sum1 * one) + (sum2 * zero)) % MOD; // Update the sum (mod 3) of the previous state sum0 = curSum0; sum1 = curSum1; sum2 = curSum2; } // Final answer is stored in sum0 return sum0;}// Driver Program const n = 5; const l = 10; const r = 100; console.log(totalSubSets(n, l, r)); |
Output:
80107136
Time Complexity: O(n)
Auxiliary Space: O(1), since no extra space has been taken.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
