Find two numbers with maximum sum formed by array digits

Posted in

Find two numbers with maximum sum formed by array digits
vinaykhatri

Vinay Khatri
Last updated on July 20, 2024

    Problem

    Given an integer array having digits between 0 and 9, find two numbers with maximum sum formed using all the array digits. The difference in the number of digits of the two numbers should be ± 1.

    Sample Input

    [3, 4, 5, 6]

    Sample Output

    64 and 53

    Approach

    It is obvious that the largest possible number can be formed by having the largest element of the array as the first digit, second largest as the second digit and so on. Since we have to make two numbers here, we can select alternate numbers of the array for each number after sorting the array.

    For example, if we have the array as [3,4,5,6] . After sorting it, we get [6,5,4,3] . We can pick 6, 4 for the first number and 5,3 for the second number. The numbers will be 64 and 53 which will give the largest possible sum. The time complexity of the approach is O(NlogN)

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
     
    pair<int, int> findMaximum(vector<int> arr)    
    {
        sort(arr.rbegin(), arr.rend());
     
        int x = 0;
        for (int i = 0; i < arr.size(); i = i + 2) {
            x = x * 10 + arr[i];
        }
     
        int y = 0;
        for (int i = 1; i < arr.size(); i = i + 2) {
            y = y * 10 + arr[i];
        }
     
        return make_pair(x, y);
    }
     
    int main()
    {
        vector<int> arr = {3, 4, 5, 6};
     
        pair<int, int> ans = findMaximum(arr);
        cout << ans.first <<" "<< ans.second;
    
    }
    

    Output

    64 53

    Python Programming

    def findMaximum(arr):
     
        arr.sort(reverse=True)
     
        x = 0
        for i in range (0, len(arr), 2):
            x = x * 10 + arr[i]
     
        y = 0
        for i in range (1, len(arr), 2):
            y = y * 10 + arr[i]
     
        print(x,y)
    
    arr = [3,4,5,6]
    findMaximum(arr)

    Output

    64 53

    Java Programming

    import java.util.Arrays;
    import java.util.Comparator;
     
    class Main
    {
        public static void findMaximum(Integer[] arr)
        {
        
            Arrays.sort(arr, Comparator.reverseOrder());
    
            int x = 0;
            for (int i = 0; i < arr.length; i = i + 2) {
                x = x * 10 + arr[i];
            }
     
            int y = 0;
            for (int i = 1; i < arr.length; i = i + 2) {
                y = y * 10 + arr[i];
            }
     
            System.out.println(x);
            System.out.println(y);
        }
     
        public static void main(String[] args)
        {
            Integer[] arr = { 3,4,5,6 };
     
            findMaximum(arr);
        }
    }

    Output

    64
    53

    People are also reading:

    Leave a Comment on this Post

    0 Comments