పీపుల్ లీట్‌కోడ్ సొల్యూషన్‌కు క్యాండీలను పంపిణీ చేయండి


కఠినత స్థాయి సులువు
బైనరీ శోధన మఠం

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు రెండు సంఖ్యలు ఇవ్వబడ్డాయి కాండీలను మరియు num_people. మొదటి సంఖ్య క్యాండీలు మన వద్ద ఉన్న క్యాండీల సంఖ్య. num_people మేము క్యాండీలను పంపిణీ చేయాల్సిన వ్యక్తి సంఖ్యను చూపుతుంది.

క్యాండీల పంపిణీ నియమం:
మేము ఎడమవైపు ఉన్న వ్యక్తి నుండి 1 మిఠాయిని ఇస్తాము, అప్పుడు మేము 2 క్యాండీలను 2 వ వ్యక్తికి, 3 క్యాండీలను 3 వ వ్యక్తికి n క్యాండీలు వరకు n వ వ్యక్తికి ఇస్తాము. ఆ తరువాత మనం మళ్ళీ ఎడమ వైపు నుండి అతనికి n + 1 క్యాండీలు ఇవ్వడం మొదలుపెడతాము, తరువాత n + 2, n + 3. మేము మిఠాయిలు అయిపోయే వరకు ఈ చక్రీయ పంపిణీ కొనసాగుతుంది, అంటే మన మిగిలిన క్యాండీలు ప్రస్తుత అవసరం కంటే తక్కువగా ఉన్నప్పుడు, మిగిలిన మిఠాయిలను ప్రస్తుత వ్యక్తికి ఇస్తాము, ఆపై మేము ఆగిపోతాము.

ఉదాహరణ

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

వివరణ:

మొదటి మలుపులో, జవాబు [0] + = 1, మరియు శ్రేణి [1,0,0,0].
రెండవ మలుపులో, జవాబు [1] + = 2, మరియు శ్రేణి [1,2,0,0].
మూడవ మలుపు, జవాబు [2] + = 3, మరియు శ్రేణి [1,2,3,0].
నాల్గవ మలుపు, జవాబు [3] + = 1 (ఎందుకంటే ఒక మిఠాయి మాత్రమే మిగిలి ఉంది), మరియు చివరి శ్రేణి [1,2,3,1].

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

వివరణ:

మొదటి మలుపులో, జవాబు [0] + = 1, మరియు శ్రేణి [1,0,0].
రెండవ మలుపులో, జవాబు [1] + = 2, మరియు శ్రేణి [1,2,0].
మూడవ మలుపు, జవాబు [2] + = 3, మరియు శ్రేణి [1,2,3].
నాల్గవ మలుపు, జవాబు [0] + = 4, మరియు చివరి శ్రేణి [5,2,3].

అప్రోచ్ 1 (బ్రూట్ ఫోర్స్)

సరళమైన విధానం ఏమిటంటే మొదటి వ్యక్తికి ఎల్ మిఠాయి ఇవ్వడం మరియు 2 నుండి 2 వ వ్యక్తికి ఇవ్వడం మరియు చివరి వ్యక్తికి వెళ్లడం. మొదటి వ్యక్తి అతనికి క్యాండీలు ఇవ్వడం నుండి మళ్ళీ ప్రారంభించండి.
దీనిని ఉపయోగించి చేయవచ్చు సమూహ లూప్, దీనిలో బయటి లూప్ ఏదైనా మిఠాయి మిగిలి ఉందా లేదా అనే పరిస్థితి కోసం నడుస్తుంది. లోపలి లూప్ ఎడమ నుండి కుడికి నడుస్తుంది, ఇది ఇవ్వవలసిన ప్రస్తుత క్యాండీలతో ప్రతి స్థాన విలువలను సంకలనం చేస్తుంది. కానీ ప్రస్తుతం మిగిలి ఉన్న క్యాండీలు ప్రస్తుత అవసరాల కంటే తక్కువగా ఉండే పరిస్థితి ఉండవచ్చు. ఈ విధంగా, లోపలి లూప్‌లో if if పరిస్థితి ఉంది.

ప్రస్తుతం అవసరమైన క్యాండీలు మిగిలిన మిఠాయిల కంటే ఎక్కువగా ఉన్నప్పుడు, మిగిలిన క్యాండీలు ప్రస్తుత వ్యక్తికి ఇవ్వబడతాయి. లేకపోతే, ప్రస్తుత అవసరమైన క్యాండీలు ప్రస్తుత వ్యక్తికి ఇవ్వబడతాయి.

పీపుల్ లీట్‌కోడ్ సొల్యూషన్‌కు క్యాండీలను పంపిణీ చేయడానికి అమలు

సి ++ ప్రోగ్రామ్

#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

ప్రజలకు లీట్‌కోడ్ సొల్యూషన్‌కు క్యాండీలను పంపిణీ చేయడానికి సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (గరిష్టంగా (చదరపు (క్యాండీలు)): ప్రస్తుత అవసరం ప్రతి లూప్‌లో ఒకటి పెరుగుతుంది. కాబట్టి, క్యాండీల సంఖ్య మొదట 1 తగ్గుతుంది, తరువాత 2 తగ్గుతుంది.
కాబట్టి, సమయం t తరువాత, పడిపోయిన క్యాండీల సంఖ్య t * (t + 1) / 2 లేదా సమయం t తర్వాత t ^ 2 క్యాండీలు పడిపోతాయి.
ఈ విధంగా సి క్యాండీలను వదలడానికి మనకు చదరపు (సి) సమయం అవసరం.
అందువలన, సమయం సంక్లిష్టత sqrt (క్యాండీలు).

అంతరిక్ష సంక్లిష్టత 

O (సంఖ్యా_ ప్రజలు): పరిమాణం_ సంఖ్యల శ్రేణి ఉపయోగించబడుతుంది. అందువల్ల, స్థల సంక్లిష్టత O (num_people).

అప్రోచ్ 2 (బైనరీ శోధన)

మునుపటి విధానంలో, మేము ప్రతి వ్యక్తికి ఒక్కొక్కటిగా క్యాండీలు ఇస్తున్నాము. అప్పుడు, మళ్ళీ మేము చక్రీయంగా ప్రారంభం నుండి క్యాండీలు ఇవ్వడం ప్రారంభిస్తాము. ఇది ఖచ్చితంగా సమయం తీసుకునే ప్రక్రియ.
కాబట్టి, ఈ విధానంలో, మేము ప్రాథమికంగా ఈ క్రింది దశలను చేస్తాము.

మొదట, మేము మిఠాయిల పూర్తి నెరవేర్పు సంఖ్యను లెక్కిస్తాము. అంటే నియమం ప్రకారం ఖచ్చితమైన క్యాండీలు పొందిన మొత్తం వ్యక్తులను మేము కనుగొంటాము.
పంపిణీ 1 నుండి మొదలవుతుంది మరియు 1 ద్వారా ఇంక్రిమెంట్ అవుతుంది. అందువల్ల పంపిణీ 1 2 3 4 5 6 లాగా ఉండాలి. ఇప్పుడు మనం విజయవంతంగా 6 సార్లు క్యాండీలు ఇచ్చాము. అప్పుడు వినియోగించే మొత్తం క్యాండీల సంఖ్య మొదటి 6 సహజ సంఖ్యల మొత్తం.
అందువల్ల మనం ఏ సమయంలోనైనా, మిఠాయిల సంఖ్య n సహజ సంఖ్యల మొత్తం అని చెప్పవచ్చు, ఇక్కడ n అనేది ఆ సమయం వరకు పంపిణీ.
ఇప్పుడు మేము నియమం ప్రకారం గరిష్ట విజయవంతమైన పంపిణీని కోరుకుంటున్నాము. అంటే n యొక్క గరిష్ట విలువ n (n + 1) / 2 <= మొత్తం క్యాండీల సంఖ్య కావాలి.

N యొక్క విలువను తెలుసుకోవడానికి, మాకు బహుళ విధానాలు ఉన్నాయి. మేము n కోసం క్వాడ్రాటిక్ ఫంక్షన్‌ను పరిష్కరించగలము లేదా మనం n = 1 కొరకు ప్రారంభించవచ్చు మరియు n యొక్క విలువను 1 సరళంగా n తో పెంచే విలువతో ప్రత్యామ్నాయంగా ఉంచవచ్చు. కానీ ఇక్కడ సరైన పరిష్కారం బైనరీ శోధనను ఉపయోగించడం.

N విలువను కనుగొనడానికి బైనరీ శోధన.

ఇక్కడ బైనరీ శోధనను ఉపయోగించడానికి, n రాగల సరిహద్దును మనం తెలుసుకోవాలి. N యొక్క కనీసం విలువ 1 కావచ్చు అని మేము చెప్పగలం, ఎందుకంటే, క్యాండీల పరిమితి కనీసం 1 గా ఉంటుంది. కాబట్టి, మనం కనీసం 1 మిఠాయిని మొదటి వ్యక్తికి ఇవ్వగలము, కాబట్టి ఒక విజయవంతమైన పంపిణీని చేస్తాము (కాబట్టి, తక్కువ బౌండ్ l = 1) . N యొక్క ఎగువ బౌండ్ లెక్కించడానికి సంక్లిష్టంగా ఉంటుంది, కాబట్టి మనం దానిని మన స్వయం ద్వారా చాలా పెద్ద పూర్ణాంక విలువను ఇస్తున్నాము (ఎగువ బౌండ్ r = 1000000 లెట్).

ఇప్పుడు మనకు l మరియు r ల మధ్య ఒక పాయింట్ n కావాలి, ఇది సమీకరణాన్ని సంతృప్తిపరిచే గరిష్ట విలువ.
n (n + 1) / 2 <= మొత్తం క్యాండీల సంఖ్య.
L మరియు r మధ్య ఏదైనా పాయింట్ (ఒక పాయింట్ మధ్యలో ఉండనివ్వండి) పై సమీకరణాన్ని సంతృప్తిపరిస్తే. మరియు తదుపరి పాయింట్ (అనగా మధ్య + 1) సమీకరణాన్ని సంతృప్తిపరచదు. అప్పుడు విజయవంతమైన పంపిణీ యొక్క గరిష్ట సంఖ్య మధ్యలో ఉంటుంది.

మేము విజయవంతమైన నెరవేర్పుల సంఖ్యను కనుగొన్న తరువాత (మధ్య), పంపిణీ యొక్క పూర్తి చక్రాల సంఖ్యను మనం సులభంగా లెక్కించవచ్చు, ఇది k = mid /num_people.

K పూర్తి చక్రాల తర్వాత ఇప్పుడు మేము ప్రతి వ్యక్తికి క్యాండీలను లెక్కిస్తున్నాము.

పీపుల్ లీట్‌కోడ్ సొల్యూషన్‌కు క్యాండీలను పంపిణీ చేయండి

 

కాబట్టి, k పూర్తి చక్రాల తర్వాత క్యాండీల సంఖ్యను లెక్కించడానికి గణిత పదాలను కనుగొన్నాము. K + 1 వ అసంపూర్ణ చక్రం గురించి ఏమిటి.
K + 1 వ అసంపూర్ణ చక్రంలో, క్యాండీలను విజయవంతంగా నెరవేర్చడం n వ వ్యక్తులకు వెళ్ళదని మేము సులభంగా చెప్పగలం, మా క్యాండీలు మధ్యలో ఎక్కడో పూర్తవుతాయి.

మా చివరి విజయవంతమైన నెరవేర్పు మధ్యలో ఉందని మేము ఇప్పటికే లెక్కించాము. మరియు మధ్య%num_people వ్యక్తి ఆ మధ్య క్యాండీలు తీసుకుంటాడు. మరియు తరువాతి వ్యక్తి మిగిలిన మిఠాయిలు పొందుతారు.

పీపుల్ లీట్‌కోడ్ సొల్యూషన్‌కు క్యాండీలను పంపిణీ చేయండి
ఈ విధంగా మేము ఈ చివరి అసంపూర్ణ చక్ర పంపిణీని మా మొదటి మధ్య% కు జోడిస్తాముnum_people మరియు 1 + మధ్య%num_people మిగిలిన అన్ని క్యాండీలను పొందుతారు.

పీపుల్ లీట్‌కోడ్ సొల్యూషన్‌కు క్యాండీలను పంపిణీ చేయడానికి అమలు

సి ++ ప్రోగ్రామ్

#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 (సంఖ్యా_ ప్రజలు):  విజయవంతమైన నెరవేర్పు సంఖ్యను కనుగొనడానికి, మేము కాసేపు లూప్‌ను ఉపయోగిస్తున్నాము, ఇది 10 చుట్టూ ఉన్న చెత్త సందర్భంలో లాగ్ (6 ^ 32) సార్లు నడుస్తుంది. అప్పుడు మేము ఒక లూప్‌ను సరళంగా num_people సార్లు అమలు చేసాము. అందువల్ల, సమయ సంపూర్ణత O (num_people + 32) లేదా O (num_people).

గమనిక: మిఠాయిల సంఖ్య ప్రజల సంఖ్య కంటే ఎక్కువగా ఉన్నప్పుడు ఈ అల్గోరిథం ఉత్తమంగా ఉంటుంది. ఎందుకంటే, ఈ అల్గోరిథం క్యాండీల సంఖ్యపై ఆధారపడి ఉండదు.

అంతరిక్ష సంక్లిష్టత 

O (సంఖ్యా_ ప్రజలు): పరిమాణం_ సంఖ్యల శ్రేణి ఉపయోగించబడుతుంది. అందువల్ల, స్థల సంక్లిష్టత O (num_people).