గుణకార పున ments స్థాపన మరియు ఉత్పత్తి కోసం శ్రేణి ప్రశ్నలు


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది కాడెన్స్ ఇండియా డిఇ షా Expedia ద్వారా గూగుల్
అర్రే ప్రశ్న సమస్య

“గుణకారం, పున ments స్థాపనలు మరియు ఉత్పత్తి కోసం శ్రేణి ప్రశ్నలు” సమస్య మీకు ఇవ్వబడింది అమరిక of పూర్ణ సంఖ్య మరియు మూడు రకాల ప్రశ్నలు ఉంటాయి, ఇక్కడ మీరు ఈ క్రింది రకమైన ప్రశ్నలను పరిష్కరించాలి:

రకం 1: ఎడమ, కుడి మరియు సంఖ్య X అనే మూడు విలువలు ఉంటాయి. ఈ రకమైన ప్రశ్నలో, మీరు శ్రేణిలోని ప్రతి మూలకాన్ని పరిధిలో (ఎడమ, కుడి) కలిపి X విలువకు గుణించాలి.

రకం 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 ⇒ 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 పరిధిలోని అన్ని మూలకాల ఉత్పత్తి తరువాత

అవుట్పుట్ ⇒ 3, కాబట్టి టైప్ 3 ప్రశ్నలలో మేము కనుగొన్న మొత్తం 3 వెనుకంజలో ఉన్న సున్నాలు ఉంటాయి, కాబట్టి ఇది ముద్రించబడుతుంది.

గుణకారం, పున ments స్థాపన మరియు ఉత్పత్తి కోసం శ్రేణి ప్రశ్నలు

 

అల్గారిథం

  1. రెండు శ్రేణులను ప్రకటించండి, రెండు శ్రేణులు వరుసగా 2 మరియు 5 సంఖ్యలకు సంబంధించి వెనుకంజలో ఉన్న సున్నాల సంఖ్యను నిల్వ చేస్తాయి.
  2. మేము టైప్ 1 కోసం పిలుస్తుంటే, 2 మరియు 5 పరంగా, X యొక్క వెనుకంజలో ఉన్న సున్నాలను పొందండి.
  3. ఇచ్చిన పరిధిలో శ్రేణి ద్వారా ప్రయాణించండి. ప్రతి సంఖ్యను X విలువతో గుణించండి. అదే సమయంలో, సున్నాల విలువను 2 మరియు 5 గుణకారంగా మనం సృష్టించిన శ్రేణిలో నిల్వ చేయండి సున్నాలు మరియు జీరోస్ఇన్ఫైవ్.
  4. మేము టైప్ 2 కోసం పిలుస్తుంటే, 2 మరియు 5 పరంగా, Y యొక్క వెనుకంజలో ఉన్న సున్నాలను మళ్ళీ పొందండి.
  5. పరిధి యొక్క మొదటి స్థానంలో Y ని, రెండవ స్థానంలో 2Y ని నిల్వ చేయండి. అదే సమయంలో సున్నాల వెనుకంజలో ఉన్న సున్నాల సంఖ్యను సున్నాలకు నిల్వ చేయండి.
  6. మరియు టైప్ 3 కోసం, జీరోస్ఇన్ట్వో మరియు జీరోస్ఇన్ఫైవ్ పరిధిలో ఉన్న అన్ని విలువల మొత్తాన్ని పొందండి మరియు సున్నాల సంఖ్యను రెండుగా లేదా ఐదులో సున్నాల సంఖ్యను కనిపెట్టండి.
  7. మొత్తాన్ని విలువను ముద్రించండి.

వివరణ

పరిష్కరించడానికి మాకు పూర్ణాంక శ్రేణి మరియు మూడు రకాల ప్రశ్నలు ఇవ్వబడ్డాయి. ప్రశ్నలలో ఒకటి మీరు పరిధిలో కొంత సంఖ్యను గుణించాలి అని చెప్పారు. మరొకటి మీరు కొన్ని సంఖ్యలను మార్చవలసి ఉంటుందని చెప్పారు. చివరిది మీరు పరిధిలోని సంఖ్యల ఉత్పత్తిని కనుగొనవలసి ఉందని చెప్పారు. అప్పుడు ప్రతి ప్రశ్నలను నిర్వహించడానికి మేము విడిగా చేసిన మూడు ఫంక్షన్లను వరుసగా ప్రతి ప్రశ్నకు వారి భాగాన్ని నిర్వహిస్తాము. అప్పుడు మేము వెనుకంజలో ఉన్న సున్నాలను కనుగొంటాము. దాని కోసం మేము రెండు శ్రేణులను సృష్టించాము, ఒకటి 2 పరంగా, మరొకటి 5 పరంగా.

మొదటి రకం ప్రశ్నను పరిష్కరించడానికి, ప్రారంభ స్థానం మరియు ముగింపు పాయింట్ పరంగా మాకు సంఖ్య X మరియు పరిధి ఇవ్వబడుతుంది. సంభవించే వెనుకంజలో ఉన్న సున్నాలను తెలుసుకోవడానికి. ఇచ్చిన సంఖ్యకు వెనుకంజలో ఉన్న సున్నాలు ఉన్నాయా అని మేము కనుగొంటాము. అప్పుడు ఈ వెనుకంజలో ఉన్న సున్నాల సంఖ్యను పొందండి. ఐదు పరంగా సున్నాలతో చేయటం అదే విషయం. మేము శ్రేణి యొక్క ప్రారంభ స్థానం నుండి పరిధి యొక్క ముగింపు స్థానం వరకు శ్రేణిని దాటుతాము. అప్పుడు మేము ప్రయాణించేటప్పుడు ప్రతి సంఖ్యతో X విలువను గుణించాలి. సున్నాలను నిల్వ చేయడానికి మేము సృష్టించిన శ్రేణిలో అదనంగా ఏకకాలంలో కూడా చేస్తాము. టైప్ 2 ప్రశ్నలో అదే పని, మనం ప్రతి మూలకాన్ని ఇచ్చిన సంఖ్య ద్వారా, సిరీస్ రూపంలో భర్తీ చేయాలి.

టైప్ త్రీ ప్రశ్నను పరిష్కరించడానికి, మేము విలువను సెట్ చేస్తాము sumOfTwos మరియు sumOfFives to 0. మేము sumOfTwos మరియు sumOfFives ను సృష్టించిన వేరియబుల్‌లో విలువను నిల్వ చేస్తాము. అప్పుడు మేము కనీస sumOfTwos మరియు sumOfFives ను కనుగొంటాము. మేము తిరిగి వచ్చే అవసరమైన మరియు చివరి సమాధానం అది.

కోడ్

గుణకారం, పున ments స్థాపన మరియు ఉత్పత్తి కోసం శ్రేణి ప్రశ్నల కోసం 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

గుణకారం, పున ments స్థాపన మరియు ఉత్పత్తి కోసం శ్రేణి ప్రశ్నల కోసం జావాలో అమలు

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” శ్రేణిలోని మూలకాల సంఖ్య. ప్రతి ప్రశ్నకు O (N) సమయం అవసరం ఎందుకంటే మనకు ఇచ్చిన పరిధి మొత్తాన్ని మనం దాటాలి.

అంతరిక్ష సంక్లిష్టత

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. మేము ఇన్పుట్ కాకుండా రెండు శ్రేణులను సృష్టించాము కాబట్టి, అల్గోరిథం సరళ స్థల సంక్లిష్టతను కలిగి ఉంది.