Поделите бомбоне људима Леетцоде Солутион


Ниво тешкоће Лако
Бинарна претрага Математика

Изјава о проблему

У овом проблему добили смо два броја бомбоне нум_пеопле. Први број бомбона је број слаткиша које имамо. нум_пеопле показује број особе код које морамо да делимо бомбоне.

Правило дистрибуције бомбона је:
Почињемо од крајње леве особе, дајемо му 1 бомбон, а затим дајемо 2 бомбона другој особи, 2 бомбоне трећој особи, до н бомбона новој особи. После тога опет крећемо од крајње леве особе дајући му н + 3 бомбона, затим н + 3, н + 1. Ова циклична дистрибуција се наставља све док нам не понестане бомбона, тј. Када ће нам преостали слаткиши бити мањи од тренутних потреба, даћемо преостале бомбоне тренутној особи и онда ћемо престати.

Пример

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

objašnjenje:

На првом завоју, анс [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]

objašnjenje:

На првом завоју, анс [0] + = 1, а низ је [1,0,0].
На другом завоју, анс [1] + = 2, а низ је [1,2,0].
Треће окретање, анс [2] + = 3, а низ је [1,2,3].
Четврти окрет, анс [0] + = 4, а коначни низ је [5,2,3].

Приступ 1 (Бруте Форце)

Најједноставнији приступ је давање бомбона првом лицу и давање 2 другом лицу и тако даље прелазак на последње лице. Затим почните од првог лица које му даје бомбоне у складу с тим.
То се може урадити помоћу а угнежђена петља, у којем ће се спољна петља приказивати под условом да ли је остало слаткиша или не. Унутрашња петља ће се изводити слева надесно, што ће сумирати вредности сваке позиције са тренутним бомбонима које треба дати. Али можда постоји ситуација у којој ће тренутно преостали бомбони бити мањи од тренутних потреба. Дакле, у унутрашњој петљи постоји услов иф елсе.

када су тренутно потребни бомбони већи од преосталих бомбона, преостали бомбони ће се дати тренутној особи. У супротном, тренутни потребни бомбони биће дати тренутној особи.

Примена решења за дистрибуцију бомбона људима са Леетцоде решењем

Програм Ц ++

#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

Анализа сложености решења за дистрибуцију бомбона људима са Леетцоде решењем

Сложеност времена

О (макс. (Скрт (бомбони))): Тренутни захтев се повећава за један у свакој петљи. Дакле, број бомбона се прво смањи за 1, а затим смањи за 2 и тако даље.
Дакле, након времена т, број испуштених бомбона је т * (т + 1) / 2 или око т ^ 2 бомбона падне након времена т.
Тако да за испуштање ц бомбона треба скрт (ц) времена.
Дакле, временска сложеност је скрт (бомбоне).

Сложеност простора 

О (број_људи): Користи се низ величине нум_пеопле. Дакле, сложеност простора је О (број_људи).

Приступ 2 (Бинарна претрага)

У претходном приступу давали смо бомбоне свакој особи једну по једну. Затим, опет циклично почињемо да дајемо бомбоне од почетка. Ово је дефинитивно дуготрајан процес.
Дакле, у овом приступу у основи ћемо извршити следеће кораке.

Прво израчунавамо укупан број комплетних испуњења бомбона. тј. открићемо укупан број људи који добију тачне бомбоне у складу са правилом.
Дистрибуција почиње од 1 и увећава се за 1. Дакле, дистрибуција мора бити отприлике 1 2 3 4 5 6. Претпоставимо сада да смо бомбоне дали 6 пута. Тада је број укупних конзумираних бомбона збир првих 6 природних бројева.
Према томе, можемо рећи да је у било ком тренутку број конзумираних бомбона збир н природних бројева, где је н дистрибуција извршена до тог тренутка.
Сада желимо максимално успешну дистрибуцију према правилу. тј. желимо да је максимална вредност н таква да је н (н + 1) / 2 <= укупан број бомбона.

Да бисмо сазнали вредност н, имамо више приступа. Квадратну функцију можемо решити за н или можемо започети за н = 1 и наставити замењивати вредност н са увећавањем вредности н за 1 линеарно. Али најприкладније решење је овде користити бинарну претрагу.

Бинарна претрага за проналажење вредности н.

Да бисмо овде користили бинарну претрагу, морамо знати границу у којој н може доћи. Можемо рећи да најмање вредност н може бити 1, јер је ограничење бомбона најмање 1. Дакле, можемо дати најмање 1 слаткиш првом лицу, тако да извршавамо једну успешну дистрибуцију (Дакле, доња граница л = 1) . Горњу границу н може бити компликовано израчунати, па јој једноставно дајемо врло велику целобројну вредност од себе (нека је горња граница р = 1000000).

Сада желимо тачку н између л и р која је максимална вредност која задовољава једначину.
н (н + 1) / 2 <= укупан број бомбона.
Ако било која тачка (нека тачка средина) између л и р задовољава горњу једначину. а следећа тачка (тј. средина + 1) не може задовољити једначину. Тада ће средина бити максималан број успешне дистрибуције.

Након што смо пронашли број успешних испуњења (средина), лако можемо израчунати број комплетних циклуса расподеле, који је к = средњи /нум_пеопле.

Сада израчунавамо бомбоне свакој особи након к комплетних циклуса.

Поделите бомбоне људима Леетцоде Солутион

 

Дакле, пронашли смо математичке појмове за израчунавање броја бомбона након к комплетних циклуса. Шта је са к + 1-им непотпуним циклусом.
У к + 1 некомплетном циклусу можемо лако рећи да успешно испуњавање бомбона неће доћи до н-их људи, наши бомбони ће бити готови негде између.

Већ смо израчунали да је наше последње успешно испуњење средина. И средина%нум_пеопле особа ће узимати оне бомбоне средином. А следећа особа ће добити све преостале бомбоне.

Поделите бомбоне људима Леетцоде Солутион
Тако ћемо додати ову последњу непотпуну расподелу циклуса нашим првих средњих%нум_пеопле и 1 + средњи%нум_пеопле добиће све преостале бомбоне.

Примена решења за дистрибуцију бомбона људима са Леетцоде решењем

Програм Ц ++

#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

Анализа сложености решења за дистрибуцију бомбона људима са Леетцоде решењем

Сложеност времена

О (број_људи):  Да бисмо пронашли број успешног испуњења, користимо вхиле петљу која ће се покретати за лог (10 ^ 6) пута у најгорем случају који је око 32. Затим смо петљу покренули линеарно нум_пеопле пута. Дакле, временска сложеност је О (број_људи + 32) или О (број_људи).

Напомена: Овај алгоритам ће бити најбољи када је број бомбона много већи од броја људи. Јер, овај алгоритам не зависи од броја бомбона.

Сложеност простора 

О (број_људи): Користи се низ величине нум_пеопле. Дакле, сложеност простора је О (број_људи).