Given an array arr[] of size N( > 2). The task is to find the maximum sum of digits of the product of any two numbers of the given array.
Examples:
Input : arr[] = {8, 7}
Output : 11
The product of 8 and 7 is 56. The sum of the digits of 56 is equal to 11.
Input : arr[] = {4, 3, 5}
Output : 6
Product of 4 & 3 = 12. Sum of the digits = 3.
Product of 3 & 5 = 15. Sum of the digits = 6.
Product of 4 & 5 = 20. Sum of the digits = 2.
Approach: Run nested loops to select two numbers of the array and get the product. For every product check the digit sum and find the maximum digit sum.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int sumDigits( int n)
{
int digit_sum = 0;
while (n) {
digit_sum += n % 10;
n /= 10;
}
return digit_sum;
}
int productOfNumbers( int arr[], int n)
{
int sum = INT_MIN;
for ( int i = 0; i < n - 1; i++) {
for ( int j = i + 1; j < n; j++) {
int product = arr[i] * arr[j];
sum = max(sum, sumDigits(product));
}
}
return sum;
}
int main()
{
int arr[] = { 4, 3, 5 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << productOfNumbers(arr, n);
return 0;
}
|
Java
import java.io.*;
class GFG
{
static int sumDigits( int n)
{
int digit_sum = 0 ;
while (n > 0 )
{
digit_sum += n % 10 ;
n /= 10 ;
}
return digit_sum;
}
static int productOfNumbers( int []arr, int n)
{
int sum = Integer.MIN_VALUE;
for ( int i = 0 ; i < n - 1 ; i++)
{
for ( int j = i + 1 ; j < n; j++)
{
int product = arr[i] * arr[j];
sum = Math.max(sum, sumDigits(product));
}
}
return sum;
}
public static void main (String[] args)
{
int []arr = { 4 , 3 , 5 };
int n = arr.length;
System.out.print( productOfNumbers(arr, n));
}
}
|
Python3
import sys
def sumDigits(n):
digit_sum = 0 ;
while (n > 0 ):
digit_sum + = n % 10 ;
n / = 10 ;
return digit_sum;
def productOfNumbers(arr, n):
sum = - sys.maxsize - 1 ;
for i in range (n - 1 ):
for j in range (i + 1 , n):
product = arr[i] * arr[j];
sum = max ( sum , sumDigits(product));
return sum ;
if __name__ = = '__main__' :
arr = [ 4 , 3 , 5 ];
n = len (arr);
print ( int (productOfNumbers(arr, n)));
|
C#
using System;
class GFG
{
static int sumDigits( int n)
{
int digit_sum = 0;
while (n > 0)
{
digit_sum += n % 10;
n /= 10;
}
return digit_sum;
}
static int productOfNumbers( int []arr, int n)
{
int sum = int .MinValue;
for ( int i = 0; i < n - 1; i++)
{
for ( int j = i + 1; j < n; j++)
{
int product = arr[i] * arr[j];
sum = Math.Max(sum, sumDigits(product));
}
}
return sum;
}
public static void Main (String[] args)
{
int []arr = { 4, 3, 5 };
int n = arr.Length;
Console.Write(productOfNumbers(arr, n));
}
}
|
Javascript
<script>
function sumDigits(n)
{
let digit_sum = 0;
while (n > 0) {
digit_sum += n % 10;
n = parseInt(n / 10, 10);
}
return digit_sum;
}
function productOfNumbers(arr, n)
{
let sum = Number.MIN_VALUE;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
let product = arr[i] * arr[j];
sum = Math.max(sum, sumDigits(product));
}
}
return sum;
}
let arr = [ 4, 3, 5 ];
let n = arr.length;
document.write(productOfNumbers(arr, n));
</script>
|
Time Complexity: O(n2 * log(p)), where p is the maximum product value of two elements in the array and n is the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.