1 ಬಿಟ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಂಖ್ಯೆಯಿಂದ ಪೂರ್ಣಾಂಕಗಳನ್ನು ವಿಂಗಡಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್
ಬಿಟ್ ಮ್ಯಾನಿಪ್ಯುಲೇಷನ್ ವಿಂಗಡಿಸಲಾಗುತ್ತಿದೆ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

"1 ಬಿಟ್ ಸಂಖ್ಯೆಯಿಂದ ಪೂರ್ಣಾಂಕಗಳನ್ನು ವಿಂಗಡಿಸಿ" ಎಂಬ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ನಮ್ಮ ಕಾರ್ಯವು ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳನ್ನು 1 ಬಿಟ್‌ನ ಸಂಖ್ಯೆಗೆ ಅನುಗುಣವಾಗಿ ವಿಂಗಡಿಸುವುದು ಬೈನರಿ ಆರೋಹಣ ಕ್ರಮದಲ್ಲಿ ಸಂಖ್ಯೆಯ ಪ್ರಾತಿನಿಧ್ಯ.

ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯು ಅವುಗಳ ಬೈನರಿ ಪ್ರಾತಿನಿಧ್ಯದಲ್ಲಿ 1 ಬಿಟ್‌ನ ಸಮಾನ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿದ್ದರೆ, ಆ ಸಂದರ್ಭದಲ್ಲಿ ನಾವು ಅವುಗಳನ್ನು ಹೆಚ್ಚಿಸುವ ಕ್ರಮದಲ್ಲಿ ವಿಂಗಡಿಸಬೇಕಾಗುತ್ತದೆ. arr [i] 0 ಮತ್ತು 10000 ರ ನಡುವೆ ಇರುತ್ತದೆ.

ಉದಾಹರಣೆ

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

ವಿವರಣೆ:

ಶ್ರೇಣಿಯಲ್ಲಿನ ಪ್ರತಿ ಸಂಖ್ಯೆಯ ಬೈನರಿ ಪ್ರಾತಿನಿಧ್ಯ:

1 ಬಿಟ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಂಖ್ಯೆಯಿಂದ ಪೂರ್ಣಾಂಕಗಳನ್ನು ವಿಂಗಡಿಸಿ

7 3 ಒಂದು ಬಿಟ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ.

1 1 ಒಂದು ಬಿಟ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ.

6 6 ಒಂದು ಬಿಟ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ.

5 5 ಒಂದು ಬಿಟ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ.

ಆದ್ದರಿಂದ ಸ್ಥಿತಿಗೆ ಅನುಗುಣವಾಗಿ ವಿಂಗಡಿಸಿದ ನಂತರ ಅದು ಹೀಗಾಗುತ್ತದೆ: [1,5,6,7].

1 ಬಿಟ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಂಖ್ಯೆಯಿಂದ ಪೂರ್ಣಾಂಕಗಳನ್ನು ವಿಂಗಡಿಸಿ

ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಮೂಲಭೂತ ವಿಧಾನವೆಂದರೆ ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಅಂಶಗಳಲ್ಲಿ 1 ಬಿಟ್ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುವುದು ಮತ್ತು ನಂತರ ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸಲು ಹೋಲಿಕೆದಾರರ ಕಾರ್ಯವನ್ನು ಬಳಸುವುದು. ತುಲನಾತ್ಮಕ ಕಾರ್ಯವು ಎರಡು ಅಂಶಗಳನ್ನು ಹೋಲಿಸುತ್ತದೆ. ಎರಡೂ ಅಂಶಗಳು 1 ಬಿಟ್‌ನ ವಿಭಿನ್ನ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿದ್ದರೆ, ಕಡಿಮೆ ಸಂಖ್ಯೆಯ 1 ಬಿಟ್ ಹೊಂದಿರುವ ಸಂಖ್ಯೆ ಮೊದಲು ಬರುತ್ತದೆ, ಇಲ್ಲದಿದ್ದರೆ ಸಣ್ಣ ಸಂಖ್ಯೆ ಮೊದಲು ಬರುತ್ತದೆ.

ನಾವು ಈ ಸಮಸ್ಯೆಯನ್ನು ಚುರುಕಾದ ರೀತಿಯಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ನಾವು ಈಗಾಗಲೇ ತಿಳಿದಿರುವಂತೆ 0 [10000] 1 ಮತ್ತು 10001 ರ ನಡುವೆ ಇದೆ. ನಾವು ಒಂದು ಬಿಟ್‌ನ ಸಂಖ್ಯೆ ಮತ್ತು ಅರ್ [i] ನ ಮೌಲ್ಯವನ್ನು ಎರಡನ್ನೂ ಶೇಖರಿಸಿಡಬಹುದು. ಇದಕ್ಕಾಗಿ, ನಾವು XNUMX [ಬಿಟ್] ನಲ್ಲಿ XNUMX ಬಿಟ್ ಸಂಖ್ಯೆಯನ್ನು XNUMX ನೊಂದಿಗೆ ಗುಣಿಸುತ್ತೇವೆ ಮತ್ತು ಅರ್ [i] ಅನ್ನು ಸೇರಿಸುತ್ತೇವೆ. ಇದು ಮೂಲತಃ ಈ ರೀತಿ ಕಾಣುತ್ತದೆ:

arr [i] = arr [i] + 10001 * (arr [i] ನಲ್ಲಿ 1 ಬಿಟ್‌ನ ಸಂಖ್ಯೆ)

ಈಗ ನಾವು ರಚನೆಯನ್ನು ವಿಂಗಡಿಸುತ್ತೇವೆ. ನಾವು ವಿಂಗಡಿಸಲಾದ ಶ್ರೇಣಿಯನ್ನು ಹಿಂತಿರುಗಿಸಬೇಕಾಗಿರುವುದರಿಂದ ನಾವು arr [i]% 10001 ಅನ್ನು arr [i] ನಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ ಮತ್ತು ನಂತರ ಶ್ರೇಣಿಯನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ.

ಅನುಷ್ಠಾನ

1 ಬಿಟ್‌ನ ಸಂಖ್ಯೆಯಿಂದ ವಿಂಗಡಿಸುವ ಪೂರ್ಣಾಂಕಗಳಿಗಾಗಿ ಸಿ ++ ಕೋಡ್

#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 ಬಿಟ್‌ನ ಸಂಖ್ಯೆಯಿಂದ ವಿಂಗಡಿಸುವ ಪೂರ್ಣಾಂಕಗಳಿಗಾಗಿ ಜಾವಾ ಕೋಡ್

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 ಬಿಟ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಂಖ್ಯೆಯಿಂದ ವಿಂಗಡಿಸುವ ಪೂರ್ಣಾಂಕಗಳ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯದ ಸಂಕೀರ್ಣತೆ

ಮೇಲಿನ ಕೋಡ್‌ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಓ (ಎನ್) ಏಕೆಂದರೆ ನಾವು ಕೊಟ್ಟಿರುವ ಅರೇ ಅರೇ ಅನ್ನು ಒಮ್ಮೆ ಮಾತ್ರ ಹಾದುಹೋಗುತ್ತಿದ್ದೇವೆ. ಇಲ್ಲಿ n ಎಂಬುದು ಕೊಟ್ಟಿರುವ ಅರೇ ರಚನೆಯ ಉದ್ದವಾಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಮೇಲಿನ ಕೋಡ್‌ನ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಒ (1) ಏಕೆಂದರೆ ನಾವು ಉತ್ತರವನ್ನು ಸಂಗ್ರಹಿಸಲು ವೇರಿಯೇಬಲ್ ಅನ್ನು ಮಾತ್ರ ಬಳಸುತ್ತಿದ್ದೇವೆ.

ಉಲ್ಲೇಖಗಳು