Эхний элементийг хоёр дахин нэмэгдүүлж, тэгийг төгсгөл рүү шилжүүлнэ


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Microsoft- Zoho
Array

Асуудлын мэдэгдэл

Танд массив байна гэж бодъё бүхэл тоо. Энд "0" нь оролт гэж тооцогдох тоо биш юм. Энд буруу оруулсан байна. "Эхний элементийг хоёр дахин нэмэгдүүлж, тэгийг төгсгөл рүү шилжүүл" гэсэн асуудал нь массивыг 0-ээс өөр тоо олдсон бөгөөд түүний дараагийн тоо нь ижил тоогоор дараа нь тоог хоёр дахин нэмэгдүүлж, дараагийн тоо 0. Эцэст нь бүх тэгийг эцэст нь тулгана.

Жишээ нь

arr[] = {3, 3, 5, 0, 1, 0, 0, 1, 0}
6 5 1 1 0 0 0 0 0

Тайлбар: 3 нь дараалан гарч буй тоо тул эхний 3-ыг хоёр дахин нэмэгдүүлж 6 болгоод дараагийн 3-ыг 0 гэж тэмдэглэе. Мөн бүх тэгүүд сүүл рүү шилжсэн болно.

Эхний элементийг хоёр дахин нэмэгдүүлж, тэгийг төгсгөл рүү шилжүүлнэ

1. Traverse the array from 0 to n-1(inclusively).
2. Check if arr[i] is not equal to 0 and arr[i]==arr[i+1](next value is same as current value).
  1. If true, then make the current value twice of the self.
  2. Update next element as 0 and do i++.
3. Traverse the array from i = 0 to n-1(step of shifting all the zeroes to the end).
  1. Check if arr[i] != 0.
    1. Arr[count]=arr[i] and do count++.
4. From the traversal of till count is less than n.
  1. Arr[count]=0 and do count++.
5. Print the array.

Тайлбар

Үүнийг өгөгдсөн байдлаар дахин байрлуулах массив өгсөн. Одоогийн дугаар дараагийн дугаартай ижил байвал бид дараагийн дугаарыг өөрчлөхийг хүссэн. Өөрчлөлт бол бид одоогийн тоог хоёр дахин нэмэгдүүлэх ёстой. Хэрэв тухайн нөхцөл хангагдсан бол дараагийн тоог 0 гэж тэмдэглэнэ. Энэ өөрчлөлтийг хийсний дараа бид хийсэн эсвэл массивт байгаа массивын сүүлчийн бүх тэгийг шилжүүлэх ёстой. Дараа нь гаралтыг буцааж өгөх ёстой.

Массивыг 0-ээс n - 1 хүртэл гүйлгэн харуул. Утга тус бүр нь 0-тэй тэнцүү биш эсэхийг шалгана уу. Учир нь бид 0-ийн утгад ямар нэгэн өөрчлөлт хийх эрхгүй. Одоогийн элемент нь дараагийн элементтэй тэнцүү байгаа эсэхийг arr [i] = = arr [i + 1] гэж шалгана. Одоогийн дугаарын дараагийн дугаарыг хайж байгаа тул бид n-1-ийг хамгийн сүүлчийн цэг болгон авч үзсэн. Тиймээс бид хамгийн сүүлд хайж байгаа элемент болох n гэж орвол null заагчийн онцгой тохиолдол гарах болно. Хэрэв өгөгдсөн нөхцлүүд хангагдсан бол бид одоогийн элементийг сонгоод одоогийн утгаас хоёр дахин нэмэгдүүлж дараагийн утгыг 0 болгоно. Үүнийг массивын бүх утгын хувьд хийх хэрэгтэй.

Одоо бүх утгыг 0 гэж сүүлчийнх рүү шилжүүлээрэй. Энэ массивыг дахин туулж, утга нь тэнцүү биш байгаа эсэхийг шалгаад дараа нь зүүн тийш шилжүүлээд бүх утгыг зүүн тийш шилжүүлсний дараа хамгийн сүүлд шилжсэн утгын индекстэй болно. давталт ба энэ тооллоос n-ийн утга хүртэл бүх утгыг 0 болгоно. Эцэст нь массивыг хэвлэ.

Эхний элементийг хоёр дахин нэмэгдүүлж, тэгийг төгсгөл рүү шилжүүлнэ

код

Эхний элементийг хоёр дахин нэмэгдүүлж, тэгийг шилжүүлснээр асуудлыг эцэслэнэ

#include<iostream>

using namespace std;

void shiftZeroAtLast(int arr[], int n)
{
    int count = 0;

    for (int i = 0; i < n; i++)
        if (arr[i] != 0)
            arr[count++] = arr[i];

    while (count < n)
        arr[count++] = 0;
}
void arrayModification(int arr[], int n)
{
    if (n == 1)
        return;
    for (int i = 0; i < n - 1; i++)
    {
        if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
        {
            arr[i] = 2 * arr[i];

            arr[i + 1] = 0;

            i++;
        }
    }
    shiftZeroAtLast(arr, n);
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {3,3,5,0,1,0,0,1,0};
    int n = sizeof(arr) / sizeof(arr[0]);

    arrayModification(arr, n);

    cout << "Modified array: ";
    printArray(arr, n);

    return 0;
}
Modified array: 6 5 1 1 0 0 0 0 0

Эхний элементийг хоёр дахин нэмэгдүүлж, тэгийг шилжүүлснээр асуудлыг эцэслэнэ

class arrayRearrange
{
    public static void shiftZeroAtLast(int arr[], int n)
    {
        int count = 0;

        for (int i = 0; i < n; i++)
            if (arr[i] != 0)

                arr[count++] = arr[i];

        while (count < n)
            arr[count++] = 0;
    }
    public static void arrayModification(int arr[], int n)
    {
        if (n == 1)
            return;

        for (int i = 0; i < n - 1; i++)
        {
            if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
            {
                arr[i] = 2 * arr[i];

                arr[i + 1] = 0;

                i++;
            }
        }
        shiftZeroAtLast(arr, n);
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = {3,3,5,0,1,0,0,1,0};
        int n = arr.length;


        arrayModification(arr, n);

        System.out.print("Modified array: ");
        printArray(arr, n);
    }
}
Modified array: 6 5 1 1 0 0 0 0 0

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Бид алгоритмыг шугаман хугацаанд ажиллуулах массивыг хоёр удаа туулсан.

Сансрын нарийн төвөгтэй байдал

Алгоритм шаардлагатай O (1) нэмэлт зай, гэхдээ програм нь оролтыг хадгалахын тулд O (N) нийт зайг эзэлнэ.