3-ын хамгийн том үржвэрийг олоорой


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Амазоны
Динамик програмчлал Математик дараалал Ангилах

Асуудлын мэдэгдэл

“3-ын хамгийн том үржвэрийг ол” гэсэн асуудалд танд an гэсэн хариулт өгсөн болно массив эерэг бүхэл тоо(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 ба 2-р үлдэгдэлд 2-р дарааллыг үлдээх. 3-т хуваагдсан

Массив дахь бүх элементүүдийн нийлбэрийн дагуу 3 тохиолдол байдаг, өөрөөр хэлбэл
Кейс 1 : 3-т хуваагддаг
Гурван дарааллын бүх элементүүдийг массив дотор хадгалж, массивыг буурах дарааллаар эрэмбэл, энэ бол хариулт юм.
Кейс 2 : 1-т хуваахад үлдсэн 3 навч
Дараалал1-ээс 1 элемент хасах эсвэл дараалал1 хоосон бол дарааллын2-оос 2 элементийг хасах, хэрэв эдгээрийг хийх боломжгүй бол 3-ын үржвэрийг үүсгэх арга байхгүй.
Дараалалд үлдсэн бүх элементүүдийг массив руу шилжүүлж массивыг буурах дарааллаар эрэмбэл, энэ бол хариулт юм.
Кейс 3 : 2-т хуваахад үлдсэн 3 навч
Дараалал1-оос 2 элемент хасах эсвэл дараалал2 хоосон бол дараалал2-ээс 1 элемент хасах эсвэл эдгээрийн аль нэгийг нь хийх боломжгүй бол 3-аас олон тоогоор гарах боломжгүй юм.
Дараалалд үлдсэн бүх элементүүдийг массив руу шилжүүлж, массивыг буурах дарааллаар эрэмбэл, энэ бол хариулт юм.

код

3-ийн хамгийн том үржвэрийг олох Java код

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-ын хамгийн том үржвэрийг олох C ++ код

#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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал 

O (N log N), Учир нь бид гурван завсрын дарааллыг цэгцэлж байсан. Хамгийн муу тохиолдолд бүх n элементүүд нэг дараалалд орж магадгүй юм. Дараа нь хамгийн муу төвөгтэй байдал нь O (N log N) байх болно.

Сансрын нарийн төвөгтэй байдал

O (N), бид N элементүүдийг хадгалах дарааллыг ашигласан тул. Алгоритм нь шугаман орон зайн нарийн төвөгтэй байдаг.