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


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ మైక్రోసాఫ్ట్
అర్రే

విభజన సమస్య అర్రే ఈక్వల్ సమ్ లీట్‌కోడ్ సొల్యూషన్‌తో మూడు భాగాలుగా మనకు శ్రేణి లేదా వెక్టర్‌ను అందిస్తుంది మరియు క్రమం యొక్క మూడు విభజనలు ఉన్నాయా అని అడుగుతుంది. ఇక్కడ, విభజన ద్వారా మనం రెండు సూచికలు i, j అని అర్ధం, అంటే ప్రారంభం నుండి ith సూచిక వరకు మూలకాల మొత్తం i + 1 నుండి jth సూచిక వరకు ఉన్న మూలకాల మొత్తానికి సమానం. మరియు j + 1 సూచిక నుండి చివరి మూలకం వరకు ఉన్న మూలకాల మొత్తం శ్రేణి యొక్క మొదటి రెండు విభాగాలకు సమానం. అటువంటి రెండు సూచికలు ఉంటే, శ్రేణిని సమాన మొత్తంతో మూడు భాగాలుగా విభజించవచ్చు, లేకపోతే లేదు. పరిష్కారంలోకి వెళ్ళే ముందు కొన్ని ఉదాహరణలు చూద్దాం.

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

arr = [0,2,1,-6,6,-7,9,1,2,0,1]
true

వివరణ: మేము శ్రేణిని సమాన మొత్తంలో మూడు భాగాలుగా విభజించవచ్చు కాబట్టి. ఈ విధంగా శ్రేణిని మూడు సమాన మొత్తాలుగా విభజించవచ్చని చెప్పగలను. మరింత అధికారికంగా, 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1.

arr = [0,2,1,-6,6,7,9,-1,2,0,1]
false

వివరణ: శ్రేణిని ఒకే మొత్తాలను కలిగి ఉన్న మూడు వేర్వేరు విభాగాలుగా విభజించడానికి మార్గం లేదు కాబట్టి. అందువలన సమాధానం తప్పు.

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

సమాన మొత్తంతో మూడు భాగాలుగా విభజన శ్రేణి సమస్య లీట్‌కోడ్ సొల్యూషన్, ఇచ్చిన శ్రేణిని సమాన మొత్తాలను కలిగి ఉన్న మూడు డిజాయింట్ సబ్‌రేలుగా విభజించగలమా అని అడిగారు. కాబట్టి, మొదట సమస్యను పరిష్కరించడానికి మేము శ్రేణి యొక్క మొత్తం మొత్తాన్ని కనుగొనాలి. మొత్తం మొత్తాన్ని 3 ద్వారా విభజించకపోతే, సమాధానం తప్పు. ఎందుకంటే అప్పుడు శ్రేణిని మూడు సమాన ఉప భాగాలుగా విభజించడానికి మార్గం లేదు. మొత్తాన్ని 3 ద్వారా భాగించినట్లయితే, మనం మొత్తం / 3 ను పొందగలమా అని తనిఖీ చేస్తాము. మూలకాల యొక్క మొత్తం మొత్తాన్ని మొత్తం / 3 కు సమానంగా కనుగొనే వరకు నిరంతర మొత్తాన్ని నిల్వ చేయడం ద్వారా మేము ఈ ప్రక్రియను అనుకరిస్తాము. ప్రస్తుత మూలకం = మొత్తం / 3 వరకు మనకు మొత్తం లభిస్తే, మేము మొత్తాన్ని 0 కి రీసెట్ చేస్తాము. మరోసారి, మొత్తం మూలకాలు = మొత్తం / 3 ను కనుగొనడం ప్రారంభించండి. ఈ పద్ధతి ద్వారా మనం మొత్తాన్ని / 3 సార్లు పొందగలిగితే. మేము శ్రేణిని 3 భాగాలుగా విభజించగలమని భరోసా ఇవ్వవచ్చు.

కోడ్

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

#include <bits/stdc++.h>
using namespace std;

bool canThreePartsEqualSum(vector<int>& arr) {
    int sum = 0;
    for(int i=0;i<arr.size();i++)
        sum += arr[i];
    if(sum % 3 != 0)
        return false;
    int sum3 = sum/3, partitions = 0;
    sum = 0;
    for(int i=0;i<arr.size();i++){
        sum += arr[i];
        if(sum == sum3){
            ++partitions;
            sum = 0;
        }
    }
    return partitions >= 3;
}

int main() {
  vector<int> arr({0,2,1,-6,6,-7,9,1,2,0,1}); 
  cout<<canThreePartsEqualSum(arr);
  return 0;
}
true

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
  public static boolean canThreePartsEqualSum(int[] arr) {
        int sum = 0;
        for(int i=0;i<arr.length;i++)
            sum += arr[i];
        if(sum % 3 != 0)
            return false;
        int sum3 = sum/3, partitions = 0;
        sum = 0;
        for(int i=0;i<arr.length;i++){
            sum += arr[i];
            if(sum == sum3){
                ++partitions;
                sum = 0;
            }
        }
        return partitions >= 3;
    }
 
  public static void main (String[] args) throws java.lang.Exception{
    int[] arr = {0,2,1,-6,6,-7,9,1,2,0,1};
 
    System.out.print(canThreePartsEqualSum(arr));
  }
}
true

సంక్లిష్టత విశ్లేషణ

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

పై), మేము శ్రేణిని రెండుసార్లు దాటినప్పటికీ. కానీ ఇది సరళ సమయ సంక్లిష్టతగా లెక్కించబడుతుంది ఎందుకంటే మనం శ్రేణిని దాటిన సమయాలు దాని పరిమాణంపై ఆధారపడవు.

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

ఓ (1), మేము స్థిరమైన సంఖ్యల సంఖ్యను ఉపయోగించాము మరియు ప్రతి సూచికకు సంబంధించి కొన్ని నిర్దిష్ట సమాచారాన్ని నిల్వ చేయలేదు. స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.