Jumlah bilangan nombor dalam julat tanpa pendua

Dalam artikel ini, kita akan membincangkan cara berbeza untuk mengira bilangan integer positif tanpa mengulangi nombor antara julat yang diberikan Rendah hingga Tinggi. Kaedah pertama ialah kaedah kekerasan yang berulang ke atas semua nombor dalam julat dan menyemak sama ada ia mengandungi nombor pendua. Dalam kaedah kedua kita mengira kiraan yang diperlukan menggunakan tatasusunan awalan dan dalam kaedah terakhir kita menggunakan konsep memori daripada pengaturcaraan dinamik untuk mendapatkan hasil yang diperlukan.

Pernyataan Masalah: Diberi dua nombor, dari rendah ke tinggi, kita perlu mencari kiraan semua nombor antara rendah dan tinggi supaya nombor itu tidak mengandungi sebarang digit pendua.

Kaedah 1

Ini ialah kaedah brute force, kami hanya mengulangi semua nombor dari rendah ke tinggi dan semak sama ada ia mengandungi sebarang nombor pendua. Ini adalah penyelesaian paling mudah untuk masalah kami.

Contoh

Penyelesaian kod untuk perkara yang sama diberikan di bawah:

#include <bits/stdc++.h>
using namespace std;
// function that checks whether or not the number contains any repeated digits
int count(int number){
	int arr[10] = {0};
	while(number != 0) {
		int digit = number % 10;
		if(arr[digit]>=1)
		{
			return 0;
		}
		arr[digit]++;
		number = number / 10;
	}
	return 1;
}
// this function iterates over all the numbers in the range from low to high and adds the count of numbers having no repeated digits to the result
int numberofnums(int l , int h)
{
	int res = 0;
	for(int iterator = l; iterator < h + 1; ++iterator)
	{
		res = res + count(iterator);
	}

	return res ;
}
int main()
{
	int low = 1, high = 90;
	cout << "The count of numbers with no repeated digits from " << low << " to "<< high << " is "<<numberofnums(low, high);
	return 0;
}

Output

The count of numbers with no repeated digits from 1 to 90 is 82

Kaedah 2

Dalam kaedah ini kita akan menggunakan tatasusunan awalan untuk menyimpan kiraan integer tanpa nombor pendua sehingga indeks "iterator".

Langkah-langkah yang terlibat dalam kaedah ini ialah:

• Tentukan fungsi untuk menyemak sama ada nombor mempunyai digit pendua.

• Mulakan tatasusunan awalan dengan sifar. Tatasusunan awalan akan menyimpan bilangan digit bererti sehingga indeks yang diberikan "iterator".

• Lelar melalui setiap nombor dari rendah ke tinggi, semak jika terdapat nombor pendua. Jika tiada nombor pendua, tambahkan 1 pada tatasusunan awalan pada indeks yang sepadan.

• Kira jumlah awalan tatasusunan awalan. Jumlah awalan akan memberi anda jumlah bilangan digit bererti dalam julat.

• Kembalikan jumlah awalan.

Contoh

Kod untuk pendekatan ini diberikan di bawah -

#include <bits/stdc++.h>
using namespace std;
bool isvalid(int number)
{
	int arr[10] = {0};
	while(number != 0)
	{
		int digit = number % 10;
		if(arr[digit]>=1)
		{
			return false;
		}
		arr[digit]++;
		number = number / 10;
	}
	return true;
}

int count(int low, int high) {
    vector<int> prefarray(high+1, 0);
    for (int iterator = low; iterator <= high; iterator++) {
        if (isvalid(iterator)) {
            prefarray[iterator] = 1;
        }
    }
    for (int iterator = 1; iterator <= high; iterator++) {
        prefarray[iterator] += prefarray[iterator-1];
    }
    return prefarray[high] - prefarray[low-1];
}

int main() {
    int low = 21, high = 200;
    int c = count(low, high);
    cout << "The count of numbers with no repeated digits from " << low << " to "<< high << " is "<< c;
    return 0;
}

Output

The count of numbers with no repeated digits from 21 to 200 is 143

Kerumitan masa - O(nlogn), dengan n ialah (tinggi - rendah).

Kerumitan ruang - O(n)

Kaedah 3 Kaedah Pengaturcaraan Dinamik

Dalam pendekatan ini, kami menguraikan masalah kepada sub-masalah dan menyimpan keputusan sub-masalah dalam jadual memori

Program ini mengira jumlah bilangan digit bererti dalam julat tertentu, iaitu nombor tanpa digit berulang. Ia menggunakan pendekatan pengaturcaraan dinamik di mana fungsi dp("iterator",digunakan) mengembalikan bilangan digit bererti yang boleh dibentuk bermula dari kedudukan "iterator" dan dalam nombor "digunakan".

Kami menggunakan memtable untuk menyimpan hasil fungsi dp dan mengulangi julat nombor untuk memanggil fungsi dp bagi setiap nombor. Jumlah hasil fungsi dp untuk semua "iterator" permulaan ialah jumlah bilangan digit bererti dalam julat.

Contoh

#include <bits/stdc++.h>
using namespace std;
int dp(int iterator, set<int>& used, unordered_map<string, int>& memo, const string& high_str) {
    if ( memo.count(to_string(iterator) + "|" + to_string(used.size() ))) {
        return memo[to_string(iterator) + "|" + to_string(used.size())];
    }
    if (iterator == high_str.length())
    {
        return 1;
    }
    int count = 0;
    for (int digit = 0; digit < 10; digit++) {
        if (digit == 0 && iterator == 0) {
            continue;
        }
        if (!used.count(digit)) {
            used.insert(digit);
            count += dp(iterator+1, used, memo, high_str);
            used.erase(digit);
        }
    }
    memo[to_string(iterator) + "|" + to_string(used.size())] = count;
    return count;
}

int count_valid_numbers(int low, int high) {
    unordered_map<string, int> memo;
    string high_str = to_string(high);
    int count = 0;
    for (int num = low; num <= high; num++) {
        set<int> used;
        count += dp(0, used, memo, high_str);
    }
    return count;
}

int main() {
    int low = 21, high = 200;
    int count = count_valid_numbers(low, high);
        cout << "The count of numbers with no repeated digits from " << low   <<  " to " << high << " is "<< count;
    return 0;
}

Output

The count of numbers with no repeated digits from 21 to 200 is 116640

Kesimpulan - Dalam kod ini, kami membincangkan tiga cara untuk mengira jumlah nombor dalam julat dari rendah ke tinggi tanpa mengulangi.

Atas ialah kandungan terperinci Jumlah bilangan nombor dalam julat tanpa pendua. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!