1 બિટ લેટકોડ સોલ્યુશનની સંખ્યા દ્વારા પૂર્ણાંકો સortર્ટ કરો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ
બિટ મેનિપ્યુલેશન સોર્ટિંગ

સમસ્યા નિવેદન

સમસ્યામાં "1 બિટની સંખ્યા દ્વારા પૂર્ણાંકો સortર્ટ કરો," અમને એરે એરે આપવામાં આવે છે. અમારું કાર્ય એમાં 1 બીટની સંખ્યા અનુસાર એરેમાં તત્વોને સ sortર્ટ કરવાનું છે દ્વિસંગી ચડતા ક્રમમાં સંખ્યા રજૂ.

જો બે અથવા વધુ સંખ્યામાં તેમની દ્વિસંગી રજૂઆતમાં 1 બીટની સમાન સંખ્યા હોય, તો તે કિસ્સામાં આપણે તેમને વધતા ક્રમમાં ગોઠવવાની જરૂર છે. એઆર [i] 0 અને 10000 ની વચ્ચે આવેલું છે.

ઉદાહરણ

arr=[7,1,6,5]
[1,5,6,7]

સમજૂતી:

એરેમાં દરેક સંખ્યાની દ્વિસંગી રજૂઆત:

1 બિટ લેટકોડ સોલ્યુશનની સંખ્યા દ્વારા પૂર્ણાંકો સortર્ટ કરો

7 માં 3 એક બીટ છે.

1 માં 1 એક બીટ છે.

6 માં 6 એક બીટ છે.

5 માં 5 એક બીટ છે.

તેથી તે સ્થિતિ મુજબ વર્ગીકરણ કર્યા પછી તે બને છે: [1,5,6,7].

1 બિટ લેટકોડ સોલ્યુશનની સંખ્યા દ્વારા સortર્ટ પૂર્ણાંકો માટેનો અભિગમ

આ સમસ્યાને હલ કરવા માટેનો ખૂબ જ મૂળ અભિગમ એરેના દરેક તત્વમાં 1 બીટની સંખ્યાની ગણતરી અને પછી એરેને સ sortર્ટ કરવા માટે કમ્પેરેટર ફંક્શનનો ઉપયોગ કરવો. તુલનાત્મક કાર્ય બે તત્વોની તુલના કરે છે. જો બંને તત્વોમાં 1 બીટની જુદી સંખ્યા હોય તો તે નંબર જેમાં 1 બીટની ઓછી સંખ્યા હોય તે પહેલા આવે છે અન્યથા નાની સંખ્યા પ્રથમ આવે છે.

આપણે આ સમસ્યાને ચાલાક રીતે પણ હલ કરી શકીએ છીએ. જેમ આપણે પહેલાથી જાણીએ છીએ એઆર [i] 0 અને 10000 ની વચ્ચે આવેલું છે. આપણે એક બીટની સંખ્યા અને એઆરઆરનું મૂલ્ય બંને [i] એઆરમાં જ સ્ટોર કરી શકીએ છીએ [i]. આ માટે, આપણે એરિટમાં 1 બીટની સંખ્યાને 10001 સાથે ગુણાકાર કરીશું અને એઆર [i] ઉમેરીશું. આ મૂળભૂત રીતે આના જેવું લાગે છે:

એઆરઆર [i] = એઆરઆર [i] + 10001 * (અરરમાં 1 બીટની સંખ્યા [i])

હવે આપણે એરે સ sortર્ટ કરીશું. જેમકે અમને સ .ર્ટ થયેલ એરે પરત કરવાની જરૂર છે તેથી આપણે એઆરઆર [i]% 10001 એઆરમાં સંગ્રહિત કરીશું [i] અને પછી એરે પરત કરીશું.

અમલીકરણ

1 બિટની સંખ્યા દ્વારા સortર્ટ પૂર્ણાંકો માટે સી ++ કોડ

#include <bits/stdc++.h> 
using namespace std; 
    vector<int> sortByBits(vector<int>& arr) {
        int n=arr.size();
        for(int i=0;i<n;i++)
        arr[i]+=10001*__builtin_popcount(arr[i]);
        sort(arr.begin(),arr.end());
        for(int i=0;i<n;i++)
        arr[i]=arr[i]%10001;
        return arr;
    }
int main() 
{ 
 vector<int> arr = {7,1,6,5}; 
  vector<int>ans=sortByBits(arr); 
 for(int i=0;i<arr.size();i++)
 cout<<ans[i]<<" ";
 cout<<endl;
 return 0;
}
[1,5,6,7]

સંખ્યા 1 બિટ દ્વારા સ Inteર્ટ પૂર્ણાંકો માટે જાવા કોડ

import java.util.Arrays; 
public class Tutorialcup {
    public static int[] sortByBits(int[] arr) {
        int n=arr.length;
        for(int i=0;i<n;i++)
        arr[i]+=10001*Integer.bitCount(arr[i]);
        Arrays.sort(arr);
        for(int i=0;i<n;i++)
        arr[i]=arr[i]%10001;
        return arr;
    }
  public static void main(String[] args) {
        int [] arr = {7,1,6,5}; 
        int[]ans=sortByBits(arr); 
        System.out.println(Arrays.toString(ans));
  }
}
[1,5,6,7]

1 બિટ લેટકોડ સોલ્યુશનની સંખ્યા દ્વારા સortર્ટ પૂર્ણાંકોનું જટિલતા વિશ્લેષણ

સમયની જટિલતા

ઉપરોક્ત કોડની સમય જટિલતા છે ઓ (એન) કારણ કે આપણે આપેલ એરે એરે ફક્ત એક જ વાર કરી રહ્યા છીએ. અહીં n આપેલ એરે એરેની લંબાઈ છે.

જગ્યાની જટિલતા

ઉપરોક્ત કોડની અવકાશ જટિલતા છે ઓ (1) કારણ કે આપણે જવાબ સંગ્રહવા માટે માત્ર એક વેરીએબલ વાપરી રહ્યા છીએ.

સંદર્ભ