ഗുണനം മാറ്റിസ്ഥാപിക്കുന്നതിനും ഉൽപ്പന്നത്തിനുമുള്ള അറേ അന്വേഷണങ്ങൾ


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു കഡെൻസ് ഇന്ത്യ ഡി.ഇ.ഷാ ബൈ ഗൂഗിൾ
അറേ അന്വേഷണ പ്രശ്നം

“ഗുണനം, മാറ്റിസ്ഥാപിക്കൽ, ഉൽ‌പ്പന്നം എന്നിവയ്‌ക്കായുള്ള അറേ അന്വേഷണങ്ങൾ” എന്ന പ്രശ്‌നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ശ്രേണി of പൂർണ്ണസംഖ്യ കൂടാതെ മൂന്ന് തരത്തിലുള്ള അന്വേഷണങ്ങൾ ഉണ്ടാകും, അവിടെ നിങ്ങൾ ഇനിപ്പറയുന്ന തരത്തിലുള്ള ചോദ്യങ്ങൾ പരിഹരിക്കേണ്ടതുണ്ട്:

ടൈപ്പ് 1: മൂന്ന് മൂല്യങ്ങൾ ഇടത്, വലത്, ഒരു നമ്പർ എക്സ് ഉണ്ടാകും. ഇത്തരത്തിലുള്ള അന്വേഷണത്തിൽ, നിങ്ങൾ അറേയുടെ ഓരോ ഘടകങ്ങളും ശ്രേണിയിലെ (ഇടത്, വലത്) എക്സ് മൂല്യത്തിലേക്ക് ഗുണിതമായി വർദ്ധിപ്പിക്കണം (ഇടത്, വലത്).

തരം 2: അതിൽ മൂന്ന് മൂല്യങ്ങൾ അവശേഷിക്കുന്നു, വലത് ഒരു ശ്രേണിയായി. തന്നിരിക്കുന്ന ശ്രേണിയിലെ ഘടകങ്ങളെ Y, 2Y, 3Y, എന്നിങ്ങനെയുള്ള സംഖ്യകൾ ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കണം.

തരം 3: ഒരു ശ്രേണിയായി ഇടതും വലതും രണ്ട് മൂല്യങ്ങൾ ഉണ്ടാകും. തന്നിരിക്കുന്ന പരിധിക്കുള്ളിലെ എല്ലാ ഘടകങ്ങളുടെയും ഉൽപ്പന്നം നിങ്ങൾ കണ്ടെത്തണം. എണ്ണം വലുതായിരിക്കാമെന്നതിനാൽ. എല്ലാ ടൈപ്പ് 3 ചോദ്യങ്ങളിലെയും മൊത്തം പൂജ്യങ്ങളുടെ എണ്ണം നിങ്ങൾ കണക്കാക്കണം.

ഉദാഹരണം

arr[] = {1, 2, 3, 4, 5}
Query: { (3,2,5), (3,4,5), (2,1,3,1), (1,4,5,10), (3,2,4)}
3

വിശദീകരണം

ടൈപ്പ് 3 (2, 5), 2, 5 range 2 * 3 * 4 * 5 = 120 പരിധിയിലെ എല്ലാ ഘടകങ്ങളുടെയും ഉൽ‌പ്പന്നത്തിന് ശേഷം

3, 3 ⇒ 5 * 3 * 5 = 3 പരിധിയിലെ എല്ലാ ഘടകങ്ങളുടെയും ഉൽ‌പ്പന്നത്തിന് ശേഷം ടൈപ്പ് 4 (5, 60)

ടൈപ്പ് 2 (1, 3, 1), ഓരോ ഘടകത്തെയും y, 2y, 3y എന്നിങ്ങനെ മാറ്റിസ്ഥാപിച്ചതിന് ശേഷം 1 മുതൽ 3 വരെയുള്ള ശ്രേണിയിൽ

ടൈപ്പ് 1 (4, 5, 10), ഓരോ ഘടകത്തെയും 10 മുതൽ 4 വരെയുള്ള പരിധിക്കുള്ളിൽ 5 കൊണ്ട് ഗുണിക്കുക

3, 2 ⇒ 4 * 3 * 5 = 2 പരിധിയിലെ എല്ലാ ഘടകങ്ങളുടെയും ഉൽ‌പ്പന്നത്തിന് ശേഷം ടൈപ്പ് 3 (40, 240)

Put ട്ട്‌പുട്ട് ⇒ 3, അതിനാൽ ടൈപ്പ് 3 ചോദ്യങ്ങളിൽ ഞങ്ങൾ കണ്ടെത്തിയ ആകെ 3 ട്രെയിലിംഗ് പൂജ്യങ്ങൾ ഉണ്ടാകും, അതിനാൽ ഇത് അച്ചടിക്കുന്നു.

ഗുണനം, മാറ്റിസ്ഥാപിക്കൽ, ഉൽ‌പ്പന്നം എന്നിവയ്‌ക്കായുള്ള അറേ അന്വേഷണങ്ങൾ

 

അൽഗോരിതം

  1. രണ്ട് അറേകൾ പ്രഖ്യാപിക്കുക, അതായത് രണ്ട് അറേകളും യഥാക്രമം 2, 5 അക്കങ്ങളുമായി താരതമ്യപ്പെടുത്തുമ്പോൾ പിന്നിലുള്ള പൂജ്യങ്ങളുടെ എണ്ണം സംഭരിക്കും.
  2. ഞങ്ങൾ ടൈപ്പ് 1 നാണ് വിളിക്കുന്നതെങ്കിൽ, 2, 5 എന്നിവയുടെ അടിസ്ഥാനത്തിൽ എക്‌സിന്റെ പിന്നിലുള്ള പൂജ്യങ്ങൾ നേടുക.
  3. ഒരു നിശ്ചിത പരിധിക്കുള്ളിൽ അറേയിലൂടെ സഞ്ചരിക്കുക. ഓരോ സംഖ്യയും X മൂല്യത്തോടെ ഗുണിക്കുക. അതോടൊപ്പം, പൂജ്യങ്ങളുടെ മൂല്യം 2, 5 എന്നിവയുടെ ഗുണിതമായി ഞങ്ങൾ സൃഷ്ടിച്ച അറേയിൽ സംഭരിക്കുക പൂജ്യം ഒപ്പം zeroesInFive.
  4. ഞങ്ങൾ ടൈപ്പ് 2 നാണ് വിളിക്കുന്നതെങ്കിൽ, 2, 5 എന്നിവയുടെ അടിസ്ഥാനത്തിൽ Y യുടെ പിന്നിലുള്ള പൂജ്യങ്ങൾ വീണ്ടും നേടുക.
  5. ശ്രേണിയുടെ ആദ്യ സ്ഥാനത്ത് Y, രണ്ടാമത്തേതിൽ 2Y എന്നിങ്ങനെ സംഭരിക്കുക. അതോടൊപ്പം സീറോസ്ഇൻ‌ടോ, സീറോസ് ഇൻ‌ഫൈവ് എന്നിവയിലേക്ക് പൂജ്യങ്ങളുടെ എണ്ണം സംഭരിക്കുക.
  6. ടൈപ്പ് 3 നായി, സീറോസ്ഇൻ‌ടോ, സീറോസ് ഇൻ‌ഫൈവ് എന്നിവയിലെ ഒരു ശ്രേണിയിലുള്ള എല്ലാ മൂല്യങ്ങളുടെയും ആകെത്തുക നേടുക, കൂടാതെ പൂജ്യങ്ങളുടെ എണ്ണത്തിന്റെ ഏറ്റവും കുറഞ്ഞത് രണ്ടെണ്ണത്തിൽ കണ്ടെത്തുക അല്ലെങ്കിൽ അഞ്ചിൽ പൂജ്യങ്ങളുടെ എണ്ണം കണ്ടെത്തുക.
  7. മൂല്യം ആകെ അച്ചടിക്കുക.

വിശദീകരണം

പരിഹരിക്കാൻ ഞങ്ങൾക്ക് ഒരു പൂർണ്ണ സംഖ്യയും മൂന്ന് തരം അന്വേഷണങ്ങളും നൽകിയിരിക്കുന്നു. ഒരു പരിധിവരെ നിങ്ങൾ പരിധിക്കുള്ളിൽ കുറച്ച് സംഖ്യകൾ ഗുണിക്കണമെന്ന് പറയുന്നു. മറ്റൊന്ന് നിങ്ങൾ കുറച്ച് നമ്പറുകൾ മാറ്റിസ്ഥാപിക്കണമെന്ന് പറയുന്നു. അവസാനത്തേത് നിങ്ങൾ പരിധിക്കുള്ളിൽ അക്കങ്ങളുടെ ഉൽപ്പന്നം കണ്ടെത്തണമെന്ന് പറയുന്നു. ഓരോ ചോദ്യങ്ങളും നിർവ്വഹിക്കുന്നതിന് ഞങ്ങൾ ഓരോ ചോദ്യത്തിനും യഥാക്രമം മൂന്ന് ഫംഗ്ഷനുകൾ ഉണ്ടാക്കിയിട്ടുണ്ട്. പിന്നെയുള്ള പൂജ്യങ്ങൾ ഞങ്ങൾ കണ്ടെത്തും. അതിനായി ഞങ്ങൾ രണ്ട് അറേകൾ സൃഷ്ടിച്ചു, ഒന്ന് 2 ന്റെ കാര്യത്തിലും മറ്റൊന്ന് 5 ന്റെ കാര്യത്തിലും.

ആദ്യ തരം അന്വേഷണം പരിഹരിക്കുന്നതിന്, ആരംഭ പോയിന്റും അവസാനിക്കുന്ന പോയിന്റും അനുസരിച്ച് ഞങ്ങൾക്ക് ഒരു നമ്പറും ഒരു ശ്രേണിയും നൽകും. സംഭവിക്കാനിടയുള്ള പൂജ്യങ്ങൾ കണ്ടെത്തുന്നതിന്. തന്നിരിക്കുന്ന നമ്പറിന് പിന്നിൽ പൂജ്യങ്ങളുണ്ടോ എന്ന് ഞങ്ങൾ കണ്ടെത്തും. ഈ പൂജ്യങ്ങളുടെ എണ്ണം നേടുക. അഞ്ചിന്റെ കാര്യത്തിൽ പൂജ്യങ്ങളുമായി ബന്ധപ്പെടുന്നതും സമാനമാണ്. ശ്രേണിയുടെ ആരംഭ പോയിന്റ് മുതൽ ശ്രേണിയുടെ അവസാന പോയിന്റ് വരെ ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിക്കും. സഞ്ചരിക്കുമ്പോൾ ഞങ്ങൾ ഓരോ മൂല്യത്തിലും X മൂല്യം ഗുണിക്കും. പൂജ്യങ്ങൾ സംഭരിക്കുന്നതിനായി ഞങ്ങൾ സൃഷ്ടിക്കുന്ന അറേയിലെ കൂട്ടിച്ചേർക്കലും ഞങ്ങൾ ഒരേസമയം നിർവഹിക്കും. ടൈപ്പ് 2 ചോദ്യത്തിൽ ചെയ്യേണ്ടത് സമാനമാണ്, ഓരോ ഘടകത്തെയും തന്നിരിക്കുന്ന സംഖ്യ ഉപയോഗിച്ച് ഒരു ശ്രേണിയിൽ മാറ്റിസ്ഥാപിക്കേണ്ടതുണ്ട്.

ടൈപ്പ് ത്രീ അന്വേഷണം പരിഹരിക്കുന്നതിന്, ഞങ്ങൾ അതിന്റെ മൂല്യം സജ്ജീകരിക്കും sumOfTwos ഒപ്പം sumOfFives to 0. ഞങ്ങൾ sumOfTwos, sumOfFives എന്നിവ സൃഷ്ടിച്ച വേരിയബിളിൽ മൂല്യം സംഭരിക്കും. അപ്പോൾ ഞങ്ങൾ ചുരുങ്ങിയ തുക sumOfTwos, sumOfFives എന്നിവ കണ്ടെത്തും. അത് ആവശ്യമായതും അന്തിമവുമായ ഉത്തരമായിരിക്കും.

കോഡ്

ഗുണനം, മാറ്റിസ്ഥാപിക്കൽ, ഉൽ‌പ്പന്നം എന്നിവയ്‌ക്കായുള്ള അറേ അന്വേഷണങ്ങൾ‌ക്കായി സി ++ ൽ നടപ്പിലാക്കൽ

#include<vector>
#include<iostream>

using namespace std;

vector<int> zeroesInTwo(1000,0);

vector<int> zeroesInFive(1000,0);

int sum = 0;

int getTwosZeroes(int val)
{
    int count = 0;
    while (val % 2 == 0 && val != 0)
    {

        val = val / 2;
        count++;
    }

    return count;
}

int getFivesZeroes(int val)
{
    int count = 0;
    while (val % 5 == 0 && val != 0)
    {

        val = val / 5;
        count++;
    }

    return count;
}

void type1(int arr[],int ql, int qr, int x)
{
    int twoCount = getTwosZeroes(x);
    int fiveCount = getFivesZeroes(x);

    for (int i = ql - 1; i < qr; i++)
    {
        arr[i] = arr[i] * x;

        zeroesInTwo[i] += twoCount;
        zeroesInFive[i] += fiveCount;
    }
}

void type2(int arr[], int ql, int qr, int y)
{
    int twoCount = getTwosZeroes(y);
    int fiveCount = getFivesZeroes(y);

    for (int i = ql - 1; i < qr; i++)
    {
        arr[i] = (i - ql + 2) * y;

        zeroesInTwo[i] = getTwosZeroes(i - ql + 2) + twoCount;
        zeroesInFive[i] = getFivesZeroes(i - ql + 2) + fiveCount;
    }
}

void type3(int arr[],int ql, int qr)
{
    int sumtwos = 0;
    int sumfives = 0;

    for (int i = ql - 1; i < qr; i++)
    {
        sumtwos += zeroesInTwo[i];
        sumfives += zeroesInFive[i];
    }
    sum += min(sumtwos, sumfives);

}

int main()
{
    int arr[]= {1,2,3,4,5};

    int n=sizeof(arr)/sizeof(arr[0]);

    for (int i = 0; i < n; i++)
    {
        zeroesInTwo[i] = getTwosZeroes(arr[i]);
        zeroesInFive[i] = getFivesZeroes(arr[i]);
    }
    type3(arr,2,5);
    type3(arr,4,5);

    type2(arr,1,3,1);
    type1(arr,4,5,10);

    type3(arr,2,4);

    cout << sum << endl;
    return 0;
}
3

ഗുണനം, മാറ്റിസ്ഥാപിക്കൽ, ഉൽ‌പ്പന്നം എന്നിവയ്‌ക്കായുള്ള അറേ അന്വേഷണങ്ങൾ‌ക്കായി ജാവയിൽ‌ നടപ്പിലാക്കൽ

import java.util.*;

class type123
{
    private static int zeroesInTwo[]=new int[1000];

    private static int zeroesInFive[]=new int[1000];



    private static int sum = 0;

    private static int getTwosZeroes(int val)
    {
        int count = 0;
        while (val % 2 == 0 && val != 0)
        {

            val = val / 2;
            count++;
        }

        return count;
    }

    private static int getFivesZeroes(int val)
    {
        int count = 0;
        while (val % 5 == 0 && val != 0)
        {

            val = val / 5;
            count++;
        }

        return count;
    }

    private static void type1(int arr[],int ql, int qr, int x)
    {
        int twoCount = getTwosZeroes(x);
        int fiveCount = getFivesZeroes(x);

        for (int i = ql - 1; i < qr; i++)
        {
            arr[i] = arr[i] * x;

            zeroesInTwo[i] += twoCount;
            zeroesInFive[i] += fiveCount;
        }
    }

    private static void type2(int arr[], int ql, int qr, int y)
    {
        int twoCount = getTwosZeroes(y);
        int fiveCount = getFivesZeroes(y);

        for (int i = ql - 1; i < qr; i++)
        {
            arr[i] = (i - ql + 2) * y;

            zeroesInTwo[i] = getTwosZeroes(i - ql + 2) + twoCount;
            zeroesInFive[i] = getFivesZeroes(i - ql + 2) + fiveCount;
        }
    }

    private static void type3(int arr[],int ql, int qr)
    {
        int sumtwos = 0;
        int sumfives = 0;

        for (int i = ql - 1; i < qr; i++)
        {
            sumtwos += zeroesInTwo[i];
            sumfives += zeroesInFive[i];
        }
        sum += Math.min(sumtwos, sumfives);

    }

    public static void main(String []args)
    {
        int arr[]= {1,2,3,4,5};

        int n=arr.length;

        Arrays.fill(zeroesInTwo,0);

        Arrays.fill(zeroesInFive,0);

        for (int i = 0; i < n; i++)
        {
            zeroesInTwo[i] = getTwosZeroes(arr[i]);
            zeroesInFive[i] = getFivesZeroes(arr[i]);
        }

        type3(arr,2,5);
        type3(arr,4,5);

        type2(arr,1,3,1);
        type1(arr,4,5,10);

        type3(arr,2,4);

        System.out.println(sum);

    }
}
3

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഓരോ ചോദ്യത്തിനും O (N) സമയം ആവശ്യമാണ്, കാരണം ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്ന ശ്രേണി മുഴുവൻ സഞ്ചരിക്കേണ്ടതുണ്ട്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഇൻ‌പുട്ട് ഒഴികെയുള്ള രണ്ട് അറേകൾ‌ ഞങ്ങൾ‌ സൃഷ്‌ടിച്ചതിനാൽ‌, അൽ‌ഗോരിതം ലീനിയർ‌ സ്‌പേസ് സങ്കീർ‌ണ്ണതയുണ്ട്.