3 کا سب سے بڑا ملٹیپریس تلاش کریں


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے ایمیزون
متحرک پروگرامنگ ریاضی قطار چھانٹ

مسئلہ یہ بیان

"3 کا سب سے بڑا مل multipleٹ تلاش کریں" مسئلہ یہ بتاتا ہے کہ آپ کو ایک دیا جاتا ہے صف مثبت کی اشارے(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 کی طرف سے تقسیم.

صف میں موجود تمام عناصر کے جوہر کے مطابق ، 3 معاملات ہیں ، یعنی ،
کیس 1 : 3 سے تقسیم پذیر
تینوں قطار کے تمام عناصر کو ایک صف میں جمع کریں اور سرے کو نزولی ترتیب میں ترتیب دیں ، یہ جواب ہے۔
کیس 2 : 1 کے ساتھ تقسیم ہونے پر باقی 3 کو چھوڑ دیتا ہے
قطار 1 سے 1 عنصر کو ہٹا دیں یا اگر قطار 1 خالی ہے تو 2 عناصر کو قطار 2 سے ہٹائیں ، اگر ان میں سے کسی ایک کا بھی ممکن نہیں ہے تو 3 کا ایک سے زیادہ بنانے کا کوئی طریقہ نہیں ہے۔
قطار میں باقی تمام عناصر کو ایک صف میں منتقل کریں اور سرے کو نزولی ترتیب میں ترتیب دیں ، یہ جواب ہے۔
کیس 3 : 2 کے ساتھ تقسیم ہونے پر باقی 3 کو چھوڑ دیتا ہے
قطار 1 سے 2 عنصر کو ہٹا دیں یا اگر قطار 2 خالی ہے تو قطار 2 سے 1 عناصر کو ہٹا دیں یا اگر ان میں سے کوئی بھی کرنا ممکن نہیں ہے تو 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 لاگ N)، کیونکہ ہم تینوں انٹرمیڈیٹ قطار کو چھانٹ رہے ہیں۔ اور بدترین صورت میں ، تمام عنصر ایک ہی قطار میں ختم ہوسکتے ہیں۔ تب سب سے خراب معاملہ کی پیچیدگی O (N log N) ہوگی۔

خلائی پیچیدگی

O (N) ، جیسا کہ ہم نے N عناصر کو ذخیرہ کرنے کیلئے قطاریں استعمال کی ہیں۔ الگورتھم میں خلا والی پیچیدگی ہوتی ہے۔