ਬਰਾਬਰ ਦੀ ਰਕਮ ਲੀਟਕੋਡ ਸਮਾਧਾਨ ਦੇ ਨਾਲ ਤਿੰਨ ਹਿੱਸਿਆਂ ਵਿਚ ਵਿਭਾਜਨ ਐਰੇ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ Microsoft ਦੇ
ਅਰੇ

ਸਮੱਸਿਆ ਪਾਰਟੀਸ਼ਨ ਅਰੇ ਤਿੰਨ ਹਿੱਸਿਆਂ ਵਿਚ ਸਮਾਨ ਜੋੜ ਲੈਟਕੋਡ ਹੱਲ਼ ਸਾਨੂੰ ਐਰੇ ਜਾਂ ਵੈਕਟਰ ਪ੍ਰਦਾਨ ਕਰਦਾ ਹੈ ਅਤੇ ਪੁੱਛਦਾ ਹੈ ਕਿ ਕੀ ਇਸ ਤਰਤੀਬ ਦੇ ਤਿੰਨ ਭਾਗ ਸੰਭਵ ਹਨ. ਇੱਥੇ, ਵਿਭਾਜਨ ਦੁਆਰਾ ਸਾਡਾ ਮਤਲਬ ਇਹ ਹੈ ਕਿ ਇੱਥੇ ਦੋ ਸੂਚਕ ਹਨ i, j ਜਿਵੇਂ ਕਿ ਸ਼ੁਰੂ ਤੋਂ ਲੈ ਕੇ ਆਈਥ ਇੰਡੈਕਸ ਤੱਕ ਦੇ ਤੱਤਾਂ ਦੀ ਜੋੜ 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

ਵਿਆਖਿਆ: ਕਿਉਂਕਿ ਐਰੇ ਨੂੰ ਤਿੰਨ ਵੱਖਰੇ ਭਾਗਾਂ ਵਿਚ ਵੰਡਣ ਦਾ ਕੋਈ ਤਰੀਕਾ ਨਹੀਂ ਹੈ ਜਿਸਦਾ ਇਕੋ ਰਕਮ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਜਵਾਬ ਗਲਤ ਹੈ.

ਬਰਾਬਰ ਦੀ ਰਕਮ ਲੈਟਕੋਡ ਹੱਲ਼ ਨਾਲ ਤਿੰਨ ਹਿੱਸਿਆਂ ਵਿੱਚ ਵਿਭਾਜਨ ਐਰੇ ਲਈ ਪਹੁੰਚ

ਸਮਾਨ ਜੋੜ ਲੀਟਕੋਡ ਸਲਿ Arਸ਼ਨ ਦੇ ਨਾਲ ਤਿੰਨ ਹਿੱਸਿਆਂ ਵਿਚ ਵਿਭਾਜਨ ਐਰੇ ਦੀ ਸਮੱਸਿਆ ਨੇ ਸਾਨੂੰ ਪੁੱਛਿਆ ਕਿ ਕੀ ਅਸੀਂ ਦਿੱਤੇ ਗਏ ਐਰੇ ਨੂੰ ਤਿੰਨ ਵਿਛੜੇ ਉਪਨਗਰਾਂ ਵਿਚ ਵੰਡ ਸਕਦੇ ਹਾਂ ਜਿਸ ਵਿਚ ਬਰਾਬਰ ਰਕਮ ਹੈ. ਇਸ ਲਈ, ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਪਹਿਲਾਂ ਸਾਨੂੰ ਐਰੇ ਦੀ ਕੁੱਲ ਰਕਮ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਜੇ ਕੁਲ ਜੋੜ 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), ਕਿਉਂਕਿ ਅਸੀਂ ਨਿਰੰਤਰ ਗਿਣਤੀ ਦੇ ਤੱਤ ਵਰਤੇ ਹਨ ਅਤੇ ਹਰੇਕ ਸੂਚਕਾਂਕ ਸੰਬੰਧੀ ਕੁਝ ਖਾਸ ਜਾਣਕਾਰੀ ਸਟੋਰ ਨਹੀਂ ਕੀਤੀ. ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ ਨਿਰੰਤਰ ਹੈ.