Given three integers A, B and C, the task is to find the value of the expression
Since the answer can be very large, print the answer modulo 109 + 7.
Examples:
Input: A = 1, B = 1, C = 2
Output: 3
Explanation: The value of the given expression is: (1 * 1 * 1 + 1 * 1 * 2) % (109 + 7) = 3
Therefore, the required output is 3.Input: A = 10, B =100, C = 1000
Output: 13874027
Naive Approach: The simplest approach to solve this problem is to generate all possible triplets (i, j, k) and print the sum of all possible products (i * j * k) mod (109 + 7).
Algorithm:
Step 1: Initialize a constant integer M should have the value 1000000007.
Step 2: Create a function called “findTripleSum” that accepts three long long integers, A, B, and C, as inputs and outputs another long long integer.
Step 3: In order to store the necessary sum, initialize the long integer “sum” to 0.
Step 4: Use a for loop to iterate through i’s range of possible values, from 1 to A.
a. Use a second for loop inside the first one to run through all conceivable j values, from 1 to B.
1. Use a third for loop inside the second loop to run through all k’s potential values, from 1 to C.
a1. Calculate the (i * j * k) product and place the result in the long long integer variable “prod” inside the third loop.
a2. Update the “sum” variable by adding the “prod” variable modulo M.
Step 5: Return the final value of “sum”.
Below is the implementation of the above approach.
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define M 1000000007// Function to find the sum of all// possible triplet products (i * j * k)long long findTripleSum(long long A, long long B, long long C){ // Stores sum required sum long long sum = 0; // Iterate over all // possible values of i for (long long i = 1; i <= A; i++) { // Iterate over all // possible values of j for (long long j = 1; j <= B; j++) { // Iterate over all // possible values of k for (long long k = 1; k <= C; k++) { // Stores the product // of (i * j *k) long long prod = (((i % M) * (j % M)) % M * (k % M)) % M; // Update sum sum = (sum + prod) % M; } } } return sum;}// Driver Codeint main(){ long long A = 10; long long B = 100; long long C = 1000; cout << findTripleSum(A, B, C); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{static int M = 1000000007;// Function to find the sum of all// possible triplet products (i * j * k)static int findTripleSum(int A, int B, int C){ // Stores sum required sum int sum = 0; // Iterate over all // possible values of i for(int i = 1; i <= A; i++) { // Iterate over all // possible values of j for(int j = 1; j <= B; j++) { // Iterate over all // possible values of k for(int k = 1; k <= C; k++) { // Stores the product // of (i * j *k) int prod = (((i % M) * (j % M)) % M * (k % M)) % M; // Update sum sum = (sum + prod) % M; } } } return sum;}// Driver Codepublic static void main(String args[]){ int A = 10; int B = 100; int C = 1000; System.out.println(findTripleSum(A, B, C));}}// This code is contributed by bgangwar59 |
Python3
# Python3 program to implement# the above approachM = 1000000007# Function to find the sum # of all possible triplet# products (i * j * k)def findTripleSum(A, B, C): # Stores sum required sum sum = 0 # Iterate over all # possible values of i for i in range(1, A + 1): # Iterate over all # possible values of j for j in range(1, B + 1): # Iterate over all # possible values of k for k in range(1, C + 1): # Stores the product # of (i * j *k) prod = (((i % M) * (j % M)) % M * (k % M)) % M # Update sum sum = (sum + prod) % M return sum# Driver Codeif __name__ == '__main__': A = 10 B = 100 C = 1000 print(findTripleSum(A, B, C))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approach using System;class GFG{ static int M = 1000000007; // Function to find the sum of all// possible triplet products (i * j * k)static int findTripleSum(int A, int B, int C){ // Stores sum required sum int sum = 0; // Iterate over all // possible values of i for(int i = 1; i <= A; i++) { // Iterate over all // possible values of j for(int j = 1; j <= B; j++) { // Iterate over all // possible values of k for(int k = 1; k <= C; k++) { // Stores the product // of (i * j *k) int prod = (((i % M) * (j % M)) % M * (k % M)) % M; // Update sum sum = (sum + prod) % M; } } } return sum;} // Driver Codepublic static void Main(){ int A = 10; int B = 100; int C = 1000; Console.WriteLine(findTripleSum(A, B, C));}}// This code is contributed by code_hunt |
Javascript
<script>// JavaScript program to implement the above approachlet M = 1000000007;// Function to find the sum of all// possible triplet products (i * j * k)function findTripleSum(A, B, C){ // Stores sum required sum let sum = 0; // Iterate over all // possible values of i for(let i = 1; i <= A; i++) { // Iterate over all // possible values of j for(let j = 1; j <= B; j++) { // Iterate over all // possible values of k for(let k = 1; k <= C; k++) { // Stores the product // of (i * j *k) let prod = (((i % M) * (j % M)) % M * (k % M)) % M; // Update sum sum = (sum + prod) % M; } } } return sum;}// Driver Code let A = 10; let B = 100; let C = 1000; document.write(findTripleSum(A, B, C)); // This code is contributed by susmitakunndugoaldanga.</script> |
Output:
13874027
Time Complexity: O(A * B * C)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
Single summation:
Double summation:
= ((A * (A + 1) / 2) * (B * (B + 1) / 2))
Similarly, for triple summation:
= ((A * (A + 1) / 2) * (B * (B + 1) / 2) * (C * (C + 1) / 2))
Follow the steps below to solve the problem:
- Initialize a variable, say MMI to store the modulo multiplicative inverse of 8.
- Initialize a variable say M to store the value of 109 + 7.
Finally, print the value of ((A * (A + 1) % M) * (B * (B + 1) % M) * (C * (C + 1) % M) * MMI) % M.
C++
// C++ implementation to implement// the above approach#include <bits/stdc++.h>using namespace std;#define M 1000000007// Function to find the value// of power(X, N) % Mlong long power(long long x, long long N){ // Stores the value // of (X ^ N) % M long long res = 1; // Calculate the value of // power(x, N) % M while (N > 0) { // If N is odd if (N & 1) { // Update res res = (res * x) % M; } // Update x x = (x * x) % M; // Update N N = N >> 1; } return res;}// Function to find modulo multiplicative// inverse of X under modulo Mlong long modinv(long long X){ return power(X, M - 2);}// Function to find the sum of all// possible triplet products (i * j * k)int findTripleSum(long long A, long long B, long long C){ // Stores modulo multiplicative // inverse of 8 long long MMI = modinv(8); // Stores the sum of all // possible values of (i * j * k) long long res = 0; // Update res res = ((((A % M * (A + 1) % M) % M * (B % M * (B + 1) % M) % M) % M * (C % M * (C + 1) % M) % M) % M * MMI) % M; return res;}// Driver Codeint main(){ long long A = 10; long long B = 100; long long C = 1000; cout << findTripleSum(A, B, C); return 0;} |
Java
// Java implementation to implement// the above approachimport java.util.*;class GFG{ static final int M = 1000000007;// Function to find the value// of power(X, N) % Mstatic long power(long x, long N){ // Stores the value // of (X ^ N) % M long res = 1; // Calculate the value of // power(x, N) % M while (N > 0) { // If N is odd if (N % 2 == 1) { // Update res res = (res * x) % M; } // Update x x = (x * x) % M; // Update N N = N >> 1; } return res;}// Function to find modulo multiplicative// inverse of X under modulo Mstatic long modinv(long X){ return power(X, M - 2);}// Function to find the sum of all// possible triplet products (i * j * k)static long findTripleSum(long A, long B, long C){ // Stores modulo multiplicative // inverse of 8 long MMI = modinv(8); // Stores the sum of all // possible values of (i * j * k) long res = 0; // Update res res = ((((A % M * (A + 1) % M) % M * (B % M * (B + 1) % M) % M) % M * (C % M * (C + 1) % M) % M) % M * MMI) % M; return res;}// Driver Codepublic static void main(String[] args){ long A = 10; long B = 100; long C = 1000; System.out.print(findTripleSum(A, B, C));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to # implement the above approachM = 1000000007# Function to find the value# of power(X, N) % Mdef power(x,N): global M # Stores the value # of (X ^ N) % M res = 1 # Calculate the value of # power(x, N) % M while (N > 0): # If N is odd if (N & 1): # Update res res = (res * x) % M # Update x x = (x * x) % M # Update N N = N >> 1 return res# Function to find modulo # multiplicative inverse # of X under modulo Mdef modinv(X): return power(X, M - 2)# Function to find the # sum of all possible # triplet products (i * j * k)def findTripleSum(A, B, C): global M # Stores modulo multiplicative # inverse of 8 MMI = modinv(8) # Stores the sum of all # possible values of (i * j * k) res = 0 # Update res res = ((((A % M * (A + 1) % M) % M * (B % M * (B + 1) % M) % M) % M * (C % M * (C + 1) % M) % M) % M * MMI)% M return res# Driver Codeif __name__ == '__main__': A = 10 B = 100 C = 1000 print(findTripleSum(A, B, C))# This code is contributed by SURENDRA_GANGWAR |
C#
// C# implementation to implement// the above approachusing System;class GFG{ static readonly int M = 1000000007;// Function to find the value// of power(X, N) % Mstatic long power(long x, long N){ // Stores the value // of (X ^ N) % M long res = 1; // Calculate the value of // power(x, N) % M while (N > 0) { // If N is odd if (N % 2 == 1) { // Update res res = (res * x) % M; } // Update x x = (x * x) % M; // Update N N = N >> 1; } return res;}// Function to find modulo multiplicative// inverse of X under modulo Mstatic long modinv(long X){ return power(X, M - 2);}// Function to find the sum of all// possible triplet products (i * j * k)static long findTripleSum(long A, long B, long C){ // Stores modulo multiplicative // inverse of 8 long MMI = modinv(8); // Stores the sum of all // possible values of (i * j * k) long res = 0; // Update res res = ((((A % M * (A + 1) % M) % M * (B % M * (B + 1) % M) % M) % M * (C % M * (C + 1) % M) % M) % M * MMI) % M; return res;}// Driver Codepublic static void Main(String[] args){ long A = 10; long B = 100; long C = 1000; Console.Write(findTripleSum(A, B, C));}}// This code is contributed by Amit Katiyar |
Javascript
// JS implementation to // implement the above approachlet M = 1000000007n// Function to find the value// of power(X, N) % Mfunction power(x,N){ // Stores the value // of (X ^ N) % M let res = 1n // Calculate the value of // power(x, N) % M while (N > 0n) { // If N is odd if ((N & 1n) == 1n) // Update res res = (res * x) % M // Update x x = (x * x) % M // Update N N = N >> 1n } return res}// Function to find modulo // multiplicative inverse // of X under modulo Mfunction modinv(X){ return power(X, M - 2n)}// Function to find the // sum of all possible // triplet products (i * j * k)function findTripleSum(A, B, C){ // Stores modulo multiplicative // inverse of 8 let MMI = modinv(8n) // Stores the sum of all // possible values of (i * j * k) let res = 0n // Update res res = ((((A % M * (A + 1n) % M) % M * (B % M * (B + 1n) % M) % M) % M * (C % M * (C + 1n) % M) % M) % M * MMI)% M return res}// Driver Codelet A = 10nlet B = 100nlet C = 1000nconsole.log(findTripleSum(A, B, C))// This code is contributed by phasing17 |
Output:
13874027
Time Complexity: O(log2N), Where N = (A * B * C)
Auxiliary Space: O(1)
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!
