ගුණ කිරීම ආදේශ කිරීම සහ නිෂ්පාදනය සඳහා අරාව විමසීම්


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ කේඩන්ස් ඉන්දියාව ඩී ෂෝ Expedia ගූගල්
අරා විමසුම් ගැටළුව

“ගුණ කිරීම, ප්‍රතිස්ථාපනය සහ නිෂ්පාදනය සඳහා අරාව විමසීම්” ගැටළුව මඟින් ඔබට ලබා දී ඇති බව සඳහන් වේ අරාව of නිඛිල තවද පහත දැක්වෙන ආකාරයේ විමසීම් විසඳිය යුතු විමසුම් වර්ග තුනක් ඇත:

පළමු වර්ගය: වම්, දකුණ සහ X අංක තුනක් ඇත. මෙම ආකාරයේ විමසුමක දී, ඔබ අරාවෙහි සෑම අංගයක්ම පරාසයේ (වමේ, දකුණේ) එක්ස් අගය දක්වා ගුණ කළ යුතුය.

දෙවන වර්ගය: එය අගයක් ලෙස වමේ අගයන් තුනකින් සමන්විත වේ. ඔබ ලබා දී ඇති පරාසයේ ඇති මූලද්‍රව්‍ය Y, 2Y, 2Y, සහ යනාදිය සමඟ ප්‍රතිස්ථාපනය කළ යුතුය.

3 වන වර්ගය: පරාසයක් ලෙස වමේ සහ දකුණේ අගයන් දෙකක් ඇත. දී ඇති පරාසය තුළ ඇති සියලුම මූලද්‍රව්‍යයන්ගේ නිෂ්පාදිතය ඔබ සොයාගත යුතුය. සංඛ්යාව විශාල විය හැකි බැවින්. සියලුම Type3 විමසුම් වල ඇති පසුපස ශුන්‍ය ගණන ඔබ ගණන් කළ යුතුය.

උදාහරණයක්

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 * 2 = 3 පරාසය තුළ ඇති සියලුම මූලද්‍රව්‍යවල නිෂ්පාදිතයෙන් පසුව ටයිප් 4 (5, 120)

3 සහ 3 ⇒ 5 * 3 * 5 = 3 පරාසය තුළ ඇති සියලුම මූලද්‍රව්‍යවල නිෂ්පාදිතයෙන් පසුව ටයිප් 4 (5, 60)

ටයිප් 2 (1, 3, 1), එක් එක් මූලද්‍රව්‍යය y, 2y සහ 3y ලෙස ප්‍රතිස්ථාපනය කිරීමෙන් පසුව 1 සිට 3 දක්වා පරාසයක

Type1 (4, 5, 10), සෑම මූලද්‍රව්‍යයක්ම 10 සිට 4 සිට 5 දක්වා ගුණ කරන්න

3 සහ 2 ⇒ 4 * 3 * 5 = 2 පරාසය තුළ ඇති සියලුම මූලද්‍රව්‍යයන්ගේ නිෂ්පාදිතයෙන් පසුව ටයිප් 3 (40, 240)

නිමැවුම් ⇒ 3, එබැවින් 3 වන වර්ගයේ විමසුම් වලින් අප සොයාගෙන ඇති මුළු ශුන්‍ය 3 ක් ඇත, එබැවින් එය මුද්‍රණය කෙරේ.

ගුණ කිරීම, ප්‍රතිස්ථාපනය සහ නිෂ්පාදනය සඳහා අරාව විමසීම්

 

ඇල්ගොරිතම

  1. අරා දෙකම පිළිවෙලින් අංක 2 සහ 5 ට සාපේක්ෂව පසුපස ශුන්‍ය ගණන ගබඩා කරන අරා දෙකක් ප්‍රකාශ කරන්න.
  2. අපි ටයිප් 1 සඳහා අමතන්නේ නම්, 2 සහ 5 අනුව X හි පසුපස ශුන්‍ය ලබා ගන්න.
  3. දී ඇති පරාසයක් තුළ අරාව හරහා ගමන් කරන්න. එක් එක් අංක X අගය සමඟ ගුණ කරන්න. ඊට සමගාමීව, ශුන්‍යවල අගය 2 සහ 5 ගුණකයක් ලෙස අප විසින් නිර්මාණය කරන ලද අරාවෙහි ගබඩා කරන්න. zeroesInTwo සහ zeroesInFive.
  4. අපි ටයිප් 2 සඳහා අමතන්නේ නම්, නැවතත් 2 සහ 5 අනුව Y හි පසුපස ශුන්‍ය ලබා ගන්න.
  5. පරාසයේ පළමු ස්ථානයේ Y, දෙවනුව 2Y සහ එසේ ගබඩා කරන්න. ඊට සමගාමීව ශුන්‍යයන් පසුපසින් බිංදුව ගණනය කිරීම ශුන්‍යයට ඉන්ට්වෝ සහ ශුන්‍ය ඉන්ෆයිව් වෙත ගබඩා කරන්න.
  6. ටයිප් 3 සඳහා, ශුන්‍යයන් දෙකකින් සහ ශුන්‍ය ඉන්ෆයිව් පරාසයක ඇති සියලු අගයන්ගේ එකතුව ලබාගෙන, ශුන්‍ය ගණන අවම වශයෙන් හෝ ශුන්‍ය ගණන පහකින් සොයා ගන්න.
  7. අගය එකතුවෙන් මුද්‍රණය කරන්න.

පැහැදිලි කිරීම

විසඳීම සඳහා අපට පූර්ණ සංඛ්‍යා පෙළක් සහ විමසුම් වර්ග තුනක් ලබා දී ඇත. එක් විමසුමකින් කියවෙන්නේ ඔබ පරාසය තුළ යම් සංඛ්‍යාවක් ගුණ කළ යුතු බවයි. අනෙක ඔබ සංඛ්‍යා කිහිපයක් ආදේශ කළ යුතු බව පවසයි. අන්තිමයා පවසන්නේ ඔබ පරාසය තුළ සංඛ්‍යා වල නිෂ්පාදිතය සොයා ගත යුතු බවයි. එක් එක් විමසුම් සිදු කිරීම සඳහා අපි එක් එක් විමසුම සඳහා පිළිවෙලින් ඔවුන්ගේ කාර්යයන් ඉටු කරන කාර්යයන් තුන වෙන වෙනම කර ඇත. එවිට අපි පසුපස බිංදුව සොයා ගනිමු. ඒ සඳහා අපි අරා දෙකක් නිර්මාණය කර ඇත්තෙමු. එකක් 2 ට ද, අනෙක 5 ට ද වේ.

පළමු වර්ගයේ විමසුම විසඳීම සඳහා, ආරම්භක ස්ථානය සහ අවසන් ලක්ෂ්‍යය අනුව අපට X අංකයක් සහ පරාසයක් ලබා දෙනු ඇත. සිදුවිය හැකි පසුපස ශුන්‍යයන් සොයා ගැනීමට. දී ඇති අංකයට එම පසුපස ශුන්‍යයන් තිබේදැයි අපි සොයා බලමු. ඉන්පසු මෙම පසුපස ශුන්‍යයන් ගණනය කරන්න. එකම දෙය නම් පහට අනුව ශුන්‍යයන් සමඟ සම්බන්ධ වීමයි. අපි අරාව හරහා ගමන් කරන්නෙමු, පරාසයේ ආරම්භක ස්ථානයේ සිට පරාසයේ අවසානය දක්වා. එවිට අපි ගමන් කරන විට එක් එක් අංකය සමඟ X අගය ගුණ කරමු. ශුන්‍ය ගබඩා කිරීම සඳහා අප විසින් සාදන ලද අරාවෙහි එකතු කිරීම ද අපි එකවර සිදු කරන්නෙමු. එකම දෙය වන්නේ දෙවන වර්ගයේ විමසුමක යෙදීමයි, අපට අවශ්‍ය වන්නේ එක් එක් මූලද්‍රව්‍යය ලබා දී ඇති සංඛ්‍යාවෙන් ආදේශ කිරීම පමණි.

තුන්වන වර්ගයේ විමසුම විසඳීම සඳහා, අපි එහි අගය සකසමු sumOfTwos සහ sumOfFives සිට 0 දක්වා අපි sumOfTwos සහ sumOfFives නිර්මාණය කළ විචල්‍යයේ අගය ගබඩා කරන්නෙමු. එවිට අපි අවම වශයෙන් sumOfTwos සහ sumOfFives සොයා ගනිමු. එය අප නැවත පැමිණීමට අවශ්‍ය සහ අවසාන පිළිතුර වනු ඇත.

කේතය

ගුණ කිරීම, ප්‍රතිස්ථාපනය සහ නිෂ්පාදන සඳහා අරා විමසුම් සඳහා C ++ ක්‍රියාත්මක කිරීම

#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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. සෑම විමසුමකටම O (N) කාලය අවශ්‍ය වන්නේ අපට ලබා දී ඇති මුළු පරාසයම ගමන් කළ යුතු බැවිනි.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. අපි ආදානය හැර අරා දෙකක් නිර්මාණය කර ඇති බැවින්, ඇල්ගොරිතමයට රේඛීය අවකාශ සංකීර්ණතාවයක් ඇත.