சம அளவு லீட்கோட் தீர்வுடன் மூன்று பகுதிகளாக பகிர்வு வரிசை


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் மைக்ரோசாப்ட்
அணி

சிக்கல் பகிர்வு அணி சமமான லீட்கோட் தீர்வுடன் மூன்று பகுதிகளுக்குள் எங்களுக்கு ஒரு வரிசை அல்லது திசையன் வழங்குகிறது மற்றும் வரிசையில் மூன்று பகிர்வுகள் சாத்தியமா என்று கேட்கிறது. இங்கே, பகிர்வு மூலம் நாம் இரண்டு குறியீடுகள் 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), நாங்கள் நிலையான எண்ணிக்கையிலான கூறுகளைப் பயன்படுத்தினோம், மேலும் ஒவ்வொரு குறியீட்டையும் பற்றிய சில குறிப்பிட்ட தகவல்களைச் சேமிக்கவில்லை. விண்வெளி சிக்கலானது நிலையானது.