ब्यक्ति लाईट्कोड समाधानमा क्यान्डीहरू वितरण गर्नुहोस्


कठिनाई तह सजिलो
बाइनरी खोज गणित

समस्या वक्तव्य

यस समस्यामा हामीलाई दुई नम्बर दिइन्छ कैंडीnum_people। पहिलो नम्बर क्यान्डीहरू हामीसँग रहेको क्यान्डीहरूको संख्या हो। num_people व्यक्तिको संख्या देखाउँदछ जुनमा हामीले क्यान्डीहरू वितरण गर्नुपर्दछ।

क्यान्डी वितरणको नियम यो छ:
हामी बायाँ मान्छेबाट सुरु गर्छौं उसलाई १ क्यान्डी दिनुहोस् त्यसपछि हामी दोस्रो क्यान्डिलाई २ क्यान्डी दिन्छौं, 1rd क्यान्डी तेस्रो व्यक्तिलाई एन क्यान्डीसम्म एनथ व्यक्तिलाई दिन्छौं। त्यस पछि हामी फेरि बायाँको व्यक्तिबाट सुरु गर्छौं उसलाई एन + १ क्यान्डी दिने त्यसपछि एन + २, एन +।। यो चक्रीय वितरण जारी रहन्छ जबसम्म हामी क्यान्डीहरू चलाउँदैनौं अर्थात् जब हाम्रो बाँकी क्यान्डीहरू वर्तमान आवश्यकता भन्दा कम हुनेछ, हामी बाँकी क्यान्डीलाई वर्तमान व्यक्तिलाई दिनेछौं र त्यसपछि हामी रोक्नेछौं।

उदाहरणका

candies = 7, num_people = 4
[1,2,3,1]

व्याख्या:

पहिलो पालोमा, उत्तरहरू [०] + = १, र एर्रे [१,०,०,०] हो।
दोस्रो पालोमा, उत्तरहरू [१] + = २, र एर्रे [१,२,०,०] हो।
तेस्रो पालो, उत्तर [२] + =,, र एर्रे [१,२,2,०] हो।
चौथो पालो, उत्तर []] + = १ (किनकि त्यहाँ केवल एक क्यान्डी बाँकी छ), र अन्तिम एर्रे [१,२,3,१] हो।

candies = 10, num_people = 3
[5,2,3]

व्याख्या:

पहिलो पालोमा, उत्तरहरू [०] + = १, र एर्रे [१,०,०,०] हो।
दोस्रो पालोमा, उत्तरहरू [१] + = २, र एर्रे [१,२,०,०] हो।
तेस्रो पालो, उत्तर [२] + =,, र एर्रे [१,२,2,०] हो।
चौथो पालो, उत्तर [०] + =,, र अन्तिम एर्रे [,,२,0] हो।

दृष्टिकोण १ (ब्रुट फोर्स)

सब भन्दा साधारण तरीका भनेको पहिलो व्यक्तिलाई l क्यान्डी दिनुहोस् र २ देखि २ जना लाई दिनुहोस् र यस्तै अन्तिम व्यक्तिको लागि। फेरि फेरि पहिलो व्यक्ति सुरु गर्नुहोस् उसको आधारमा उसलाई क्यान्डीहरू दिदै।
यो a को प्रयोग गरेर गर्न सकिन्छ नेस्टेड लूप, जहाँ बाह्य लूप त्यहाँ कुनै क्यान्डी बाँकी छ कि छैन को लागी चलेको छ। भित्री लूप बायाँ देखि दायाँ तिर चल्नेछ जुन हालको क्यान्डीहरू प्रदान गर्न प्रत्येक स्थिति मानहरूको जोड दिन्छ। तर त्यहाँ त्यस्तो अवस्था हुन सक्छ जुन हालको बाँकी क्यान्डीहरू हालको आवश्यकता भन्दा सानो हुनेछ। यसैले त्यहाँ भित्री लूपमा अर्को अवस्था छ।

जब हाल आवश्यक क्यान्डीहरू बाँकी क्यान्डीहरू भन्दा बढी छ, बाँकी क्यान्डीहरू वर्तमान व्यक्तिलाई दिइनेछ। अन्यथा, हालको आवश्यक क्यान्डीहरू वर्तमान व्यक्तिलाई दिइनेछ।

लोग्टकोड समाधानमा क्यान्डी वितरणको लागि कार्यान्वयन

C ++ कार्यक्रम

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        vector<int>ans;
        /*
        initially everyone has no candy. Thus, answer array is filled up with zeros.
        */
        for(int i=0;i<num_people;i++){
            ans.push_back(0);
        }
        int cur=0;//current requirement is initialized to zero
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++; //current requirement increments by one each time.
                if(candies>=cur){ //checks if the remaining candies are greater than current requirement 
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}
5 2 3

जावा कार्यक्रम

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
        int[]ans=new int[num_people];
        Arrays.fill(ans,0);
        int cur=0;
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++;
                if(candies>=cur){
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
}
5 2 3

व्यक्ति लाईट्कोड समाधानमा क्यान्डी वितरणको लागि जटिलता विश्लेषण

समय जटिलता

हे (अधिकतम (वर्गमीटर (क्यान्डी)): हालको आवश्यकता प्रत्येक लूपमा एक एक गरेर बढ्छ। त्यसो भए, क्यान्डीहरूको संख्या पहिले १ ले घट्दछ र २ र त्यति घटाउनुहोस्।
त्यसो भए, समय t पछि, खारेको क्यान्डीहरूको संख्या t * (t + १) / २ वा लगभग t ^ २ क्यान्डी समय t पछि छोडिन्छ।
त्यसैले सी क्यान्डी ड्रप गर्न हामीलाई sqrt (c) समय चाहिन्छ।
यसैले, समय जटिलता sqrt (क्यान्डीज) हो।

ठाउँ जटिलता 

O (num_people): आकार num_people को एक एर्रे प्रयोग गरीन्छ। यसैले, स्पेस जटिलता ओ (num_people) हो।

दृष्टिकोण २ (बाइनरी खोज)

अघिल्लो दृष्टिकोणमा हामी एक-एक गरी प्रत्येक व्यक्तिलाई क्यान्डीहरू दिइरहेका थियौं। त्यसोभए, हामी फेरि चक्रीय रूपमा सुरुबाट क्यान्डीहरू दिन थाल्छौं। यो पक्कै पनि समय खपत गर्ने प्रक्रिया हो।
त्यसो भए यस दृष्टिकोणमा हामी मूल रूपमा निम्न चरणहरू कार्य गर्दछौं।

सर्वप्रथम, हामी क्यान्डीहरूको पूर्ण पूर्तिको कुल संख्या गणना गर्दछौं। अर्थात् हामीले कुल अनुसार व्यक्तिलाई नियम अनुसार सही क्यान्डीहरू भेट्टाउनेछौं।
वितरण १ बाट सुरु हुन्छ र १. ले वृद्धि गर्दछ। यसरी वितरण केहि यस्तो हुनुपर्दछ, १ २ 1 1 1. Now. अब मानौं हामीले सफलतापूर्वक ies पटक क्यान्डीहरू दिएका छौं। तब उपभोग कुल क्यान्डीहरूको संख्या पहिलो natural प्राकृतिक संख्याहरूको योग हो।
यसैले हामी भन्न सक्दछौं कि कुनै पनि बिन्दुमा, खपत गरिएका क्यान्डीहरूको संख्या n प्राकृतिक संख्याहरूको योग हुन्छ जहाँ n त्यो समयसम्म वितरण गरिन्छ।
अब हामी नियम अनुसार अधिकतम सफल वितरण चाहान्छौं। अर्थात् हामी n को अधिकतम मान चाहान्छौं कि n (n + १) / २ <= क्यान्डीहरूको कुल संख्या।

N को मान पत्ता लगाउनको लागि, हामीसँग बहुविध दृष्टिकोणहरू छन्। हामी n को लागी क्वाड्रैटिक प्रकार्य समाधान गर्न सक्छौं वा हामी n = १ को लागी आरम्भ गर्न सक्छौं र n को मान लाई १ क्रमशः बढाउँदै n राख्छौं। तर सब भन्दा उचित समाधान भनेको यहाँ बाइनरी खोज प्रयोग गर्नु हो।

बाइनरी खोज n को मान खोज्न।

यहाँ बाइनरी खोज प्रयोग गर्नका लागि हामीले बाउन्ड थाहा पाउनु पर्दछ जुन n आउन सक्छ। हामी भन्न सक्दछौं कि कम्तिमा n को मान १ हुन सक्छ किनकि, क्यान्डीको अवरोध कम्तिमा १ हो। त्यसैले, हामी कम्तिमा पहिलो व्यक्तिलाई १ क्यान्डी दिन सक्छौं, त्यसैले एउटा सफल वितरण (तल्लो तल्लो बाउन्ड l = १) । N को माथिल्लो बाउन्ड गणना गर्न जटिल हुन सक्छ, त्यसैले हामी यसलाई सजिलै हाम्रो आफ्नै इन्टिजर मान दिइरहेका छौं (माथिल्लो बाउन्ड r = 1)।

अब हामी l र r बिन्दु n चाहान्छौं जुन अधिकतम मान हो जसले समीकरणलाई सन्तुष्ट पार्छ।
n (n + १) / २ <= क्यान्डीहरूको कुल संख्या।
यदि कुनै पोइन्ट (एक बिन्दु मध्यमा राख्छ) l र r बीच माथिको समीकरणलाई सन्तुष्ट पार्दछ। र अर्को पोइन्ट (जस्तै मध्य + १) ले समीकरण सन्तुष्ट गर्न सक्दैन। त्यसपछि मध्य सफल वितरणको अधिकतम संख्या हुनेछ।

हामीले सफल पूर्तिहरूको संख्या (मध्य) फेला पारे पछि, हामी सजिलै वितरणको पूरा चक्रहरूको संख्या गणना गर्न सक्छौं, जुन k = mid / होnum_people.

अब हामी प्रत्येक व्यक्तिलाई k पूर्ण चक्र पछि क्यान्डीहरू गणना गर्दैछौं।

ब्यक्ति लाईट्कोड समाधानमा क्यान्डीहरू वितरण गर्नुहोस्

 

त्यसोभए, हामीले k पूर्ण चक्र पछि क्यान्डीहरूको संख्या गणना गर्न गणितीय पदहरू भेट्टायौं। के १ १ अध्याय अपूर्ण चक्रको बारेमा के।
K + १ औं अधूरो चक्रमा, हामी सजिलैसँग भन्न सक्छौं कि क्यान्डीहरूको सफल पूर्ति nth व्यक्तिहरूमा जानेछैन, हाम्रो क्यान्डीहरू बीचमा कतै समाप्त हुनेछ।

हामीले पहिले नै हिसाब गरिसकेका छौं कि हाम्रो अन्तिम सफल पूर्ति मध्य हो। र मध्य%num_people व्यक्तिले त्यो मध्य व्या क्यान्डी लिनेछ। र अर्को व्यक्ति बाँकी सबै क्यान्डीहरू पाउनेछ।

ब्यक्ति लाईट्कोड समाधानमा क्यान्डीहरू वितरण गर्नुहोस्
यसैले हामी हाम्रो अन्तिम मध्य% मा यो अन्तिम अपूर्ण चक्र वितरण जोड्नेछौंnum_people र १ + मध्य%num_people सबै बाँकी क्यान्डीहरू प्राप्त गर्दछ।

लोग्टकोड समाधानमा क्यान्डी वितरणको लागि कार्यान्वयन

C ++ कार्यक्रम

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        long l=0,r=1000000;
        long mid=0;
        /*
        searching the last successful fulfilment point mid
        */
        while(l<=r){
            mid=l+(r-l)/2;
            long a=((mid+1)*(mid))/2;
            long c=((mid+2)*(mid+1))/2;
            if(a<=candies && c>candies)break;
            else if(a>candies)r=mid;
            else l=mid;
        }
        long k=mid/num_people;
        /*
        here k is the number of complete cycles
        */
        long ans[num_people];
        int i=0;
        for(i=0;i<num_people;i++){
            ans[i]=((k*(k-1)*num_people)/2)+(i+1)*k;//calculating the number of candies to each person after k complete cycles.
        }
        for(i=0;i<mid%num_people;i++){
            ans[i]+=((k*num_people)+i+1);//giving candies to first mid%num_people in k+1 th incomplete cycle.
        }
        ans[i%num_people]+=candies-(mid*(mid+1)/2);// giving all the remaining candies to next person 
        vector<int> ans1;
        for(i=0;i<num_people;i++){
            ans1.push_back((int)(ans[i]));
        }
        return ans1;
        
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}
5 2 3

जावा कार्यक्रम

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
       
        long l=0,r=1000000;
        long mid=0;
        /*
        searching the last successful fulfilment point mid
        */
        while(l<=r){
            mid=l+(r-l)/2;
            long a=((mid+1)*(mid))/2;
            long c=((mid+2)*(mid+1))/2;
            if(a<=candies && c>candies)break;
            else if(a>candies)r=mid;
            else l=mid;
        }
        long k=mid/num_people;
        /*
        here k is the number of complete cycles
        */
        long[]ans=new long[num_people];
        int i=0;
        for(i=0;i<num_people;i++){
            ans[i]=((k*(k-1)*num_people)/2)+(i+1)*k;//calculating the number of candies to each person after k complete cycles.
        }
        for(i=0;i<mid%num_people;i++){
            ans[i]+=((k*num_people)+i+1);//giving candies to first mid%num_people in k+1 th incomplete cycle.
        }
        ans[i%num_people]+=candies-(mid*(mid+1)/2);// giving all the remaining candies to next person
        int[]ans1=new int[num_people];
        for(i=0;i<ans1.length;i++){
            ans1[i]=(int)(ans[i]);
        }
        return ans1;
    }
}
5 2 3

व्यक्ति लाईट्कोड समाधानमा क्यान्डी वितरणको लागि जटिलता विश्लेषण

समय जटिलता

O (num_people):  सक्सेसफुल पूर्तिको संख्या पत्ता लगाउन, हामी केही समयको लूप प्रयोग गर्दैछौं जुन around२ भन्दा नराम्रो स्थितिमा लग (१० ^)) पटक चलाउँदछ। त्यसपछि हामीले एक लूप लाईनियर num_people पटक चलायौं। यस प्रकार, समय जटिलता O (num_people + 10) वा O (num_people) हो।

नोट: यो एल्गोरिथ्म तब उत्तम हुन्छ जब क्यान्डीहरूको संख्या मानिसहरू भन्दा धेरै ठूलो हुन्छ। किनभने, यो एल्गोरिथ्म क्यान्डीको संख्यामा निर्भर हुँदैन।

ठाउँ जटिलता 

O (num_people): आकार num_people को एक एर्रे प्रयोग गरीन्छ। यसैले, स्पेस जटिलता ओ (num_people) हो।