1 বিট লেটকোড সলিউশন এর সংখ্যা অনুসারে পূর্ণসংখ্যাগুলি সাজান


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক
বিট ম্যানিপুলেশন শ্রেণীবিভাজন

সমস্যা বিবৃতি

"1 বিটের সংখ্যা অনুসারে পূর্ণসংখ্যাগুলি বাছাই করুন" সমস্যাটিতে আমাদের একটি অ্যারে অ্যারে দেওয়া হয়। আমাদের টাস্কটি 1 বিটের সংখ্যা অনুসারে অ্যারেতে উপাদানগুলি বাছাই করা বাইনারি আরোহী ক্রম সংখ্যা প্রতিনিধিত্ব।

যদি দুটি বা ততোধিক সংখ্যায় তাদের বাইনারি উপস্থাপনায় 1 বিটের সমান সংখ্যা থাকে তবে সেই ক্ষেত্রে আমাদের তাদের ক্রমবর্ধমান ক্রম অনুসারে বাছাই করতে হবে। আর [i] 0 এবং 10000 এর মধ্যে রয়েছে।

উদাহরণ

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

ব্যাখ্যা:

অ্যারেতে প্রতিটি সংখ্যার বাইনারি উপস্থাপনা:

1 বিট লেটকোড সলিউশন এর সংখ্যা অনুসারে পূর্ণসংখ্যাগুলি সাজান

7 3 XNUMX বিট থাকে।

1 1 XNUMX বিট থাকে।

6 6 XNUMX বিট থাকে।

5 5 XNUMX বিট থাকে।

সুতরাং শর্ত অনুসারে বাছাইয়ের পরে এটি হয়ে যায়: [1,5,6,7]।

1 বিট লেটকোড সমাধানের সংখ্যা অনুসারে বাছাইয়ের পূর্ণসংখ্যার জন্য দৃষ্টিভঙ্গি

এই সমস্যাটি সমাধানের জন্য খুব প্রাথমিক পদ্ধতির মধ্যে অ্যারের প্রতিটি উপাদানগুলিতে 1 বিটের সংখ্যা গণনা করা এবং তারপরে অ্যারে বাছাই করার জন্য একটি তুলনামূলক ফাংশন ব্যবহার করা। তুলনামূলক ফাংশন দুটি উপাদানের সাথে তুলনা করে। যদি উভয় উপাদানগুলির মধ্যে 1 বিটের একটি পৃথক সংখ্যা থাকে তবে যে সংখ্যাটিতে 1 বিটের কম সংখ্যা রয়েছে সেটিতে প্রথমে আসে অন্যথায় ছোট সংখ্যাটি প্রথম আসে।

আমরা এই সমস্যাটি আরও স্মার্ট পদ্ধতিতে সমাধান করতে পারি। যেহেতু আমরা ইতিমধ্যে জেনেছি যে আর্ট [i] 0 এবং 10000 এর মধ্যে রয়েছে We আমরা এক বিটের সংখ্যা এবং অ্যারের মান উভয় সংরক্ষণ করতে পারি [i] নিজেই আরআর [i]। এর জন্য, আমরা আরআর 1 বিটের সংখ্যাকে 10001 দিয়ে গুণ করব এবং আরআর যুক্ত করব [i]। এটি মূলত: এর মতো দেখায়:

আরআর [i] = আরআর [i] + 10001 * (আর্টে 1 বিটের সংখ্যা [i])

এখন আমরা অ্যারে বাছাই করব। যেহেতু আমাদের বাছাই করা অ্যারেটি ফিরিয়ে আনতে হবে তাই আমরা অ্যারে [i]% 10001 এআর [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) কারণ আমরা উত্তর সংরক্ষণের জন্য কেবল একটি পরিবর্তনশীল ব্যবহার করছি।

তথ্যসূত্র