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 हा by ने भाग घेता येतो, म्हणून (१ + २ +)) = 3. देखील by ने भाग घेता येतो. म्हणून, ही प्रॉपर्टी वरील समस्येचे निराकरण करण्यासाठी वापरली जाऊ शकते.

क्रमवारी लावा चढत्या क्रमाने अ‍ॅरे आणि तीन राखण्यासाठी पुरुषांचा संध्याकाळी वापरण्याचा कोट, उर्वरित 0 सोडलेल्या अ‍ॅरेमधील सर्व घटक संचयित करण्यासाठी रांगे 0, 3 ने विभाजित केल्यावर एर मधील सर्व घटक संचयित करण्यासाठी रांगे 1 आणि उर्वरित 1 सोडल्यास अ‍ॅरे मधील घटक संचयित करण्यासाठी उर्वरित 3 सोडल्यास उर्वरित 2 सोडते. by ने भागलेले.

अ‍ॅरे मधील सर्व घटकांच्या बेरीजनुसार 3 प्रकरणे आहेत,
प्रकरण 1 : 3 ने विभाज्य
अ‍ॅरे मध्ये तीन रांगेतील सर्व घटक साठवा आणि अ‍ॅरे उतरत्या क्रमाने क्रमबद्ध करा, हे उत्तर आहे.
प्रकरण 2 : 1 ने विभाजित केल्यावर उर्वरित 3 पाने
रांगा 1 वरून 1 घटक काढा किंवा जर रांगेत 1 रिकामी असेल तर रांगा 2 वरून 2 घटक काढा, जर त्यापैकी काहीही करणे शक्य नसेल तर 3 चे गुणाकार तयार करण्याचा कोणताही मार्ग नाही.
रांगेत उरलेले सर्व घटक अ‍ॅरे वर जा आणि अ‍ॅरे उतरत्या क्रमाने क्रमबद्ध करा, हे उत्तर आहे.
प्रकरण 3 : 2 ने विभाजित केल्यावर उर्वरित 3 पाने
रांगेतून 1 घटक काढा किंवा जर रांगेत 2 रिकामी असेल तर रांगा 2 वरून 2 घटक काढा किंवा जर त्यापैकी काहीही करणे शक्य नसेल तर 1 वरून मल्टीपलवर जाण्याचा कोणताही मार्ग नाही.
रांगेत उरलेल्या सर्व घटकांना अ‍ॅरे वर हलवा, अ‍ॅरे उतरत्या क्रमाने क्रमवारी लावा, हे उत्तर आहे.

कोड

जावा कोड 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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी 

ओ (एन लॉग एन), कारण आम्ही तीन इंटरमीडिएट रांगा लावतो आहोत. आणि सर्वात वाईट परिस्थितीत, सर्व एन घटक एकाच रांगेत समाप्त होऊ शकतात. तर सर्वात वाईट परिस्थितीची जटिलता ओ (एन लॉग एन) असेल.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), आपण एन घटक संचयित करण्यासाठी रांगा वापरल्या आहेत. अल्गोरिदम मध्ये रेषात्मक अवघडपणा आहे.