3 નું સૌથી મોટું મલ્ટીપલ મેળવો


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન
ડાયનેમિક પ્રોગ્રામિંગ મઠ કતાર સોર્ટિંગ

સમસ્યા નિવેદન

"3 નું સૌથી મોટું મલ્ટીપ્લાય મેળવો" સમસ્યા જણાવે છે કે તમને એક આપવામાં આવ્યું છે એરે સકારાત્મક પૂર્ણાંક(0 થી 9). એરેના તત્વોને ફરીથી ગોઠવીને રચના કરી શકાય તેવા 3 નું મહત્તમ મલ્ટીપ્લાય શોધો.

ઉદાહરણો

arr[] = {5, 2, 1, 0, 9, 3}
9 5 3 1 0

 

3 નું સૌથી મોટું મલ્ટીપલ મેળવો

arr[] = {1, 2, 3, 4, 5}
5 4 3 2 1

3 નું સૌથી મોટું મલ્ટિપોલ શોધવા માટે એલ્ગોરિધમ

ત્રણના દરેક ગુણાંકમાં એક વિશેષ સંપત્તિ છે. તેના અંકોનો સરવાળો પણ 3 દ્વારા વિભાજીત થાય છે, ઉદાહરણ તરીકે,
123 એ 3 દ્વારા વિભાજીત છે, તેથી (1 + 2 + 3) = 6 પણ 3 દ્વારા વિભાજીત છે તેથી, આ મિલકતનો ઉપયોગ ઉપરોક્ત સમસ્યાને હલ કરવા માટે થઈ શકે છે.

સૉર્ટ ચડતા ક્રમમાં એરે અને ત્રણ જાળવો પૂંછડીઓ, એરેમાં બધા તત્વો સંગ્રહવા માટે કતાર 0 કે જે 0 બાકી હોય ત્યારે 3, 1 એ વિભાજિત થાય ત્યારે એરેમાં બધા તત્વો સંગ્રહવા માટે ક્યુ 1 3 દ્વારા વિભાજિત.

એરેમાંના બધા તત્વોના સરવાળો મુજબ, ત્યાં 3 કેસ છે, એટલે કે
કેસ 1 : 3 દ્વારા વિભાજીત
એરેમાં ત્રણ કતારોના બધા તત્વો સંગ્રહિત કરો અને એરેને ઉતરતા ક્રમમાં સ sortર્ટ કરો, આ જવાબ છે.
કેસ 2 : 1 દ્વારા ભાગવામાં આવે ત્યારે બાકીની 3 બાકી
ક્યુ 1 થી 1 તત્વ કા Removeો અથવા જો ક્યુ 1 ખાલી હોય તો કતાર 2 માંથી 2 તત્વો કા removeી નાખો, જો આમાંથી કોઈ પણ કરવાનું શક્ય ન હોય તો 3 ની ગુણાકાર બનાવવાની કોઈ રીત નથી.
કતારમાં બાકી રહેલા બધા તત્વોને એરેમાં ખસેડો અને એરેને ઉતરતા ક્રમમાં સ sortર્ટ કરો, આ જવાબ છે.
કેસ 3 : 2 દ્વારા ભાગવામાં આવે ત્યારે બાકીની 3 બાકી
ક્યુ 1 થી 2 તત્વ દૂર કરો અથવા જો ક્યુ 2 ખાલી હોય તો કતાર 2 માંથી 1 તત્વો કા removeો અથવા જો આમાંથી કોઈ પણ કરવાનું શક્ય ન હોય તો 3 થી મલ્ટીપલ જવાનો કોઈ રસ્તો નથી.
કતારમાં બાકી રહેલા બધા તત્વોને એરેમાં ખસેડો, એરેને ઉતરતા ક્રમમાં સ sortર્ટ કરો, આ જવાબ છે.

કોડ

3 નું સૌથી મોટું મલ્ટીપલ શોધવા માટે જાવા કોડ

import java.util.*;

class FindTheLargestMultipleOf3 {
    private static void fillAns(ArrayList<Integer> ans, Queue<Integer> q0, Queue<Integer> q1, Queue<Integer> q2) {
        while (!q0.isEmpty()) {
            ans.add(q0.poll());
        }

        while (!q1.isEmpty()) {
            ans.add(q1.poll());
        }

        while (!q2.isEmpty()) {
            ans.add(q2.poll());
        }
    }

    private static boolean findLargestMultiple(int[] arr) {
        int n = arr.length;

        // sort the array in ascending order
        Arrays.sort(arr);

        // maintain 3 queues as mentioned
        Queue<Integer> queue0 = new LinkedList<>();
        Queue<Integer> queue1 = new LinkedList<>();
        Queue<Integer> queue2 = new LinkedList<>();

        // variable to store the sum of all the elements in array
        int sum = 0;

        // traverse the array and add elements to queue
        // also find the sum
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (arr[i] % 3 == 0) {
                queue0.add(arr[i]);
            } else if (arr[i] % 3 == 1) {
                queue1.add((arr[i]));
            } else {
                queue2.add(arr[i]);
            }
        }

        // if sum is divisible by 3, do nothing
        if (sum % 3 == 0) {

        }
        // if sum leaves remainder 1 when divided by 3
        else if (sum % 3 == 1) {
            // remove 1 element from queue1
            if (!queue1.isEmpty()) {
                queue1.remove();
            } else {
                // or remove two elements from queue2
                if (!queue2.isEmpty()) {
                    queue2.remove();
                } else {
                    return false;
                }

                if (!queue2.isEmpty()) {
                    queue2.remove();
                } else {
                    return false;
                }
            }
        }
        // if sum leaves remainder 2 when divided by 3
        else {
            // remove one element from queue2
            if (!queue2.isEmpty()) {
                queue2.remove();
            } else {
                // or remove 2 elements from queue1
                if (!queue1.isEmpty()) {
                    queue1.remove();
                } else {
                    return false;
                }

                if (!queue1.isEmpty()) {
                    queue1.remove();
                } else {
                    return false;
                }
            }
        }

        // add the remaining elements to a list
        ArrayList<Integer> ans = new ArrayList<>();
        fillAns(ans, queue0, queue1, queue2);

        // sort the list in descending order, this is the answer
        Collections.sort(ans, Collections.reverseOrder());
        for (int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i) + " ");
        }
        System.out.println();

        return true;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 2, 1, 0, 9, 3};
        if (!findLargestMultiple(arr1)) {
            System.out.println("Not Possible");
        }

        // Example 2
        int arr2[] = new int[]{1, 2, 3, 4, 5};
        if (!findLargestMultiple(arr2)) {
            System.out.println("Not Possible");
        }
    }
}
9 5 3 1 0 
5 4 3 2 1

સી ++ કોડ 3 નો સૌથી મોટો મલ્ટિપલ શોધવા માટે

#include <bits/stdc++.h> 
using namespace std; 

void fillAns(vector<int> &ans, queue<int> q0, queue<int> q1, queue<int> q2) {
    while (!q0.empty()) {
        ans.push_back(q0.front());
        q0.pop();
    }
    
    while (!q1.empty()) {
        ans.push_back(q1.front());
        q1.pop();
    }
    
    while (!q2.empty()) {
        ans.push_back(q2.front());
        q2.pop();
    }
}

bool findLargestMultiple(int *arr, int n) {
    // sort the array in ascending order
    sort(arr, arr + n);
    
    // maintain 3 queues as mentioned
    queue<int> q0;
    queue<int> q1;
    queue<int> q2;
    
    // variable to store the sum of all the elements in array
    int sum = 0;
    
    // traverse the array and add elements to queue
    // also find the sum
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (arr[i] % 3 == 0) {
            q0.push(arr[i]);
        } else if (arr[i] % 3 == 1) {
            q1.push(arr[i]);
        } else {
            q2.push(arr[i]);
        }
    }
    
    // if sum is divisible by 3, do nothing
    if (sum % 3 == 0) {
        
    } 
    // if sum leaves remainder 1 when divided by 3
    else if (sum % 3 == 1) {
        // remove 1 element from queue1
        if (!q1.empty()) {
            q1.pop();
        } else {
            // or remove two elements from queue2
            if (!q2.empty()) {
                q2.pop();
            } else {
                return false;
            }
            if (!q2.empty()) {
                q2.pop();
            } else {
                return false;
            }
        }
    }
    // if sum leaves remainder 2 when divided by 3
    else {
        // remove one element from queue2
        if (!q2.empty()) {
            q2.pop();
        } else {
            // or remove 2 elements from queue1
            if (!q1.empty()) {
                q1.pop();
            } else {
                return false;
            }
            
            if (!q1.empty()) {
                q1.pop();
            } else {
                return false;
            }
        }
    }
    
    // add the remaining elements to a list
    vector<int> ans;
    fillAns(ans, q0, q1, q2);
    
    // sort the list in descending order, this is the answer
    sort(ans.begin(), ans.end(), greater<int>());
    for (int i = 0; i < ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    
    return true;
}

int main() {
    // Example 1
    int arr1[] = {5, 2, 1, 0, 9, 3};
    if (!findLargestMultiple(arr1,sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"Not Possible"<<endl;
    }

    // Example 2
    int arr2[] = {1, 2, 3, 4, 5};
    if (!findLargestMultiple(arr2,sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"Not Possible"<<endl;
    }
    
    return 0;
}
9 5 3 1 0 
5 4 3 2 1

જટિલતા વિશ્લેષણ

સમય જટિલતા 

ઓ (એન લોગ એન), કારણ કે આપણે ત્રણ મધ્યવર્તી કતારોને સingર્ટ કરી રહ્યા છીએ. અને સૌથી ખરાબ કિસ્સામાં, બધા n તત્વો એક જ કતારમાં સમાપ્ત થઈ શકે છે. પછી સૌથી ખરાબ કેસ જટિલતા ઓ (એન લોગ એન) હશે.

અવકાશ જટિલતા

ઓ (એન), જેમકે આપણે એન એલિમેન્ટ્સ સ્ટોર કરવા કતારો વાપરી છે. અલ્ગોરિધમનો રેખીય અવકાશ જટિલતા છે.