කොටස් එකතුව ලීට්කෝඩ් විසඳුම සමඟ කොටස් තුනකට බෙදීම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් මයික්රොසොෆ්ට්
අරා

කොටස බෙදීම අරා කොටස් තුනකට සමාන මුදලක් ලීට්කෝඩ් විසඳුම මඟින් අපට අරාව හෝ දෛශිකයක් ලබා දෙන අතර අනුක්‍රමය සඳහා කොටස් තුනක් තිබේදැයි විමසයි. මෙහිදී, බෙදීමෙන් අපි අදහස් කරන්නේ 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 වතාවක් ලබා ගත හැකි නම්. අපට අරාව කොටස් 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), අපි නියත මූලද්‍රව්‍ය සංඛ්‍යාවක් භාවිතා කළ නිසා සහ එක් එක් දර්ශකය පිළිබඳ නිශ්චිත තොරතුරු ගබඩා නොකළ නිසා. අවකාශයේ සංකීර්ණතාව නියත ය.