იპოვნეთ 3 – ის უდიდესი ჯერადი


Რთული ტური Hard
ხშირად ეკითხებიან Amazon
დინამიური პროგრამირება მათემატიკის Queue დახარისხება

პრობლემის განცხადება

პრობლემა "იპოვნეთ 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-ზე. ამრიგად, ეს თვისება შეიძლება გამოყენებულ იქნას ზემოთ მოცემული პრობლემის გადასაჭრელად.

დალაგება მასივი ზრდადობით და შეინარჩუნეთ სამი კუდები, queue0 მასივის ყველა ელემენტის შესანახად, რომელიც ტოვებს ნარჩენს 0-ს, გაყოფა 3-ზე, queue1- ში მასივის ყველა ელემენტის შესანახად, რომელიც ტოვებს დანარჩენ 1-ს, როდესაც იყოფა 3-ზე და queue2- ში მასივის ელემენტების შესანახად, რომლებიც ტოვებს დანარჩენ 2-ს გაყოფილი 3-ზე.

მასივის ყველა ელემენტის ჯამის მიხედვით, არსებობს 3 შემთხვევა,
საქმე 1 : იყოფა 3-ზე
შეინახეთ სამი რიგის ყველა ელემენტი მასივში და დახარისხეთ მასივი კლებადობით, ეს არის პასუხი.
საქმე 2 : ტოვებს ნარჩენების 1-ს, როდესაც იყოფა 3-ზე
მოაცილეთ 1 ელემენტი queue1– დან ან, თუ queue1 ცარიელია, ამოიღეთ 2 ელემენტი queue2– დან, თუ რომელიმე მათგანის გაკეთება შეუძლებელია, 3 – ის ჯერადის შექმნის საშუალება არ არსებობს.
რიგებში დარჩენილი ყველა ელემენტის მასივში გადატანა და მასივის დალაგება კლებადობით, ეს არის პასუხი.
საქმე 3 : ტოვებს ნარჩენების 2-ს, როდესაც იყოფა 3-ზე
მოაცილეთ 1 ელემენტი queue2– დან ან, თუ queue2 ცარიელია, ამოიღეთ 2 ელემენტი queue1– დან, ან თუ რომელიმე მათგანის გაკეთება შეუძლებელია, მრავალჯერადიდან გადაადგილება აღარ არის, თუ 3.
რიგებში დარჩენილი ყველა ელემენტის მასივში გადატანა, მასივის დალაგება კლებადობით, ეს არის პასუხი.

კოდი

ჯავის კოდი, რომ იპოვოთ 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

C ++ კოდი 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

სირთულის ანალიზი

დროის სირთულე 

O (N log N), რადგან ჩვენ დავალაგეთ სამი შუალედური რიგი. და უარეს შემთხვევაში, ყველა n ელემენტი შეიძლება დასრულდეს ერთ რიგში. მაშინ ყველაზე ცუდი სირთულე იქნება O (N log N).

სივრცის სირთულე

O (N), როგორც ჩვენ გამოვიყენეთ რიგები N ელემენტების შესანახად. ალგორითმს აქვს ხაზოვანი სივრცის სირთულე.