સમાન રકમ લીટકોડ સોલ્યુશનવાળા ત્રણ ભાગોમાં પાર્ટીશન એરે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન માઈક્રોસોફ્ટ
અરે

સમસ્યા પાર્ટીશન અરે સમાન સરવાળા લીટકોડ સોલ્યુશનવાળા ત્રણ ભાગોમાં પ્રવેશ આપણને એરે અથવા વેક્ટર પ્રદાન કરે છે અને પૂછે છે કે ક્રમના ત્રણ પાર્ટીશનો શક્ય છે કે નહીં. અહીં, પાર્ટીશન દ્વારા અમારો મતલબ એ છે કે ત્યાં બે સૂચકાંકો છે i, j જેમ કે શરૂઆતથી આઈથ ઇન્ડેક્સ સુધીના તત્વોનો સરવાળો i + 1 થી jth અનુક્રમણિકાના તત્વોના સરવાળો સમાન છે. અને j + 1 અનુક્રમણિકાથી છેલ્લા તત્વ સુધીના તત્વોનો સરવાળો પણ એરેના પ્રથમ બે ભાગો જેટલો જ છે. જો આવા બે સૂચકાંકો અસ્તિત્વમાં છે, તો આપણે કહીએ છીએ કે એરે સમાન રકમ સાથે ત્રણ ભાગમાં વહેંચી શકાય છે, નહીં તો નહીં. સોલ્યુશનમાં જતા પહેલા ચાલો થોડા ઉદાહરણો જોઈએ.

સમાન રકમ લીટકોડ સોલ્યુશનવાળા ત્રણ ભાગોમાં પાર્ટીશન એરે

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

સમજૂતી: આપણે એરેને સમાન રકમના ત્રણ ભાગમાં વહેંચી શકીએ છીએ. આમ આપણે કહી શકીએ કે એરે ત્રણ સમાન સરવાળોમાં વહેંચી શકાય છે. વધુ formalપચારિક રીતે, 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 દ્વારા વિભાજીત ન થાય, તો જવાબ ખોટો છે. કારણ કે પછી એરેને ત્રણ સમાન પેટા ભાગોમાં વહેંચવાનો કોઈ રસ્તો નથી. પરંતુ જો સરવાળો by. વડે વહેંચી શકાય તેવું છે. જ્યાં સુધી અમને તત્વોનો કુલ સરવાળો / 3 ની સરખામણી ન મળે ત્યાં સુધી અમે સતત રકમનો સંગ્રહ કરીને આ પ્રક્રિયાનું અનુકરણ કરીએ છીએ. જો આપણને વર્તમાન તત્વ = સરવાળો / until સુધીનો કુલ મળે, તો અમે કુલને ० ઉપર ફરીથી સેટ કરીશું અને ફરી એકવાર, તત્વોનો કુલ = સરવાળો / finding શોધવાનું શરૂ કરો. જો આપણે આ પદ્ધતિ દ્વારા રકમ / 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), કારણ કે અમે સતત સંખ્યાબંધ તત્વોનો ઉપયોગ કર્યો છે અને દરેક અનુક્રમણિકા સંબંધિત કેટલીક વિશિષ્ટ માહિતી સ્ટોર કરી નથી. જગ્યાની જટિલતા સતત છે.