બધા ઘટકોને સાથે કરતાં ઓછા અથવા સમાન લાવવા માટે ન્યૂનતમ સ્વેપ્સ આવશ્યક છે


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

સમસ્યા “બધા તત્વોને સાથે કરતાં ઓછી કે સમાન લાવવા માટે લઘુત્તમ સ્વેપ્સ આવશ્યક છે” કહે છે કે તમારી પાસે પૂર્ણાંક છે એરે. સમસ્યા નિવેદનમાં અદલાબદલીની સૌથી નાની ગણતરી શોધવા માટે પૂછવામાં આવે છે જે આપેલ નંબર કે કરતાં ઓછી અથવા તેના સમાન હોય તેવા તત્વોને એક સાથે મેળવવા માટે જરૂરી રહેશે.

ઉદાહરણ

arr[]={4,6,1,3,2}, k = 4
1

સમજૂતી

ફક્ત 1 સ્વેપ જરૂરી છે. 6 ને 2 સાથે બદલી શકાય છે જેથી 4, 2, 1, અને 3 એક સાથે આવે.

અલ્ગોરિધમ

  1. K ની બરાબર કરતા ઓછી હોય તેવા બધા તત્વોની ગણતરી મેળવો.
  2. K થી વધારે હોય તેવા બધા તત્વોની ગણતરી મેળવો.
  3. નાનાના મૂલ્ય પર આઉટપુટ સેટ કરો.
  4. I = 0 અને j = ગણતરીમાંથી એરેને પસાર કરો.
    1. એરે [i] k ના મૂલ્ય કરતા વધારે છે કે નહીં તે તપાસો, પછી, નાનાના મૂલ્યને 1 દ્વારા ઘટાડો.
    2. એરે [j] એ કેનાં મૂલ્ય કરતા વધારે છે કે નહીં તે તપાસો, પછી, નાનાનું મૂલ્ય 1 દ્વારા વધારવું.
    3. આઉટપુટ અને નાના વચ્ચે લઘુતમ શોધો અને તેને આઉટપુટમાં સ્ટોર કરો.
  5. આઉટપુટનું મૂલ્ય પાછું આપવું.

સમજૂતી

અમે એક આપ્યો છે એરે of પૂર્ણાંક, અને k નામનો પૂર્ણાંક મૂલ્ય, અમે બધા તત્વો એક સાથે મેળવવા માટે કેટલા ન્યૂનતમ સ્વેપ્સની આવશ્યકતા છે તે શોધવા માટે પૂછ્યું છે જે કે કરતા ઓછા અથવા સમાન હોય છે. યાદ રાખો કે આપણે ફક્ત ન્યૂનતમ સ્વેપ્સ શોધવાની જરૂર છે.

તેના માટે, આપણે એલિમેન્ટ્સની સંખ્યા ગણીશું જે k કરતાં ઓછી અથવા તેના સમાન છે, અને તેને નાના વેરીએબલ પર સંગ્રહિત કરીશું. તેથી નાના ચલ નાની સંખ્યાની ગણતરી ધરાવે છે જે કે કરતાં ઓછી અથવા તેના કરતા બરાબર છે. તે ગણતરીની જેમ, આપણે બધી સંખ્યાઓ ગણીશું કે જે સંખ્યા k કરતા વધારે છે. આઉટપુટનું મૂલ્ય નાનામાં સેટ કરો, પછીથી, આપણે આ આઉટપુટ સાથેના મૂલ્યોની તુલના કરીશું અને તેમાં એક સાથે સંગ્રહિત કરીશું. જો આપણે એક ઉદાહરણ લઈએ જે ઉપર જણાવેલ હતું, 4 એ નાનાની ગણતરી છે, અને 1 એ મોટી ગણતરી છે.

I = 0, j = નાના, એરે તપાસો [i] અને એરે [j] k ની કિંમત કરતા વધારે છે, જો એરે [i] વધારે હોય તો, એરે [j] નાનાં નાનાં ગણનામાં ઘટાડો જો એરે સાથે પસાર થવું. વધારે છે પછી નાનાની ગણતરીમાં વધારો.

તે સાથે જ આપણે આઉટપુટ અને નાની સંખ્યા વચ્ચેનું લઘુતમ શોધીશું, લૂપમાં આપણે બંને કામગીરી કરી રહ્યા છીએ, નાનાનું મૂલ્ય ઘટાડવા અને નાનાનું મૂલ્ય વધારવા માટે. અંતે, આપણે ફક્ત આઉટપુટનું મૂલ્ય પાછું આપવું પડશે. કારણ કે તેમાં ઇચ્છિત આઉટપુટ આવશે.

બધા ઘટકોને સાથે કરતાં ઓછા અથવા સમાન લાવવા માટે ન્યૂનતમ સ્વેપ્સ આવશ્યક છે

કોડ

બધા તત્વોને સાથે કરતાં ઓછા અથવા સમાન લાવવા માટે લઘુત્તમ સ્વેપ્સ મેળવવા માટે સી ++ કોડ

#include <iostream>

using namespace std;

int minimumSwapToK(int arr[], int n, int k)
{
    int count = 0;
    for (int i = 0; i < n; ++i)
        if (arr[i] <= k)
            ++count;

    int bad = 0;
    for (int i = 0; i < count; ++i)
        if (arr[i] > k)
            ++bad;

    int ans = bad;
    for (int i = 0, j = count; j < n; ++i, ++j)
    {

        if (arr[i] > k)
            --bad;

        if (arr[j] > k)
            ++bad;

        ans = min(ans, bad);
    }
    return ans;
}

int main()
{
    int arr[] = {4,6,1,3,2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
    int result = minimumSwapToK(arr, n, k);
    cout <<result;
    return 0;
}
1

બધા ઘટકોને સાથે કરતાં ઓછા અથવા સમાન લાવવા માટે જરૂરી ન્યુનત્તમ સ્વેપ્સ શોધવા માટે જાવા કોડ

class minimumSwaps
{
    public static int minimumSwapToK(int arr[], int n, int k)
    {

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

        int bad = 0;
        for (int i = 0; i < count; ++i)
            if (arr[i] > k)
                ++bad;

        int ans = bad;
        for (int i = 0, j = count; j < n; ++i, ++j)
        {

            if (arr[i] > k)
                --bad;

            if (arr[j] > k)
                ++bad;

            ans = Math.min(ans, bad);
        }
        return ans;
    }
    public static void main(String[] args)
    {
        int arr[] = {4,6,1,3,2};
        int n = arr.length;
        int k = 4;
        int result = minimumSwapToK(arr, n, k);
        System.out.println(result);

    }
}
1

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં "n” એરેમાં તત્વોની સંખ્યા છે. કારણ કે આપણી પાસે લૂપ્સ હતી જેમાં નેસ્ટ લૂપ્સ નથી. આમ સમય જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (1) કોઈ વધારાની જગ્યા જરૂરી છે. તેથી જગ્યા જટિલતા સતત છે.