The total number of numbers in a range without duplicates
In this article, we will discuss different ways to count the number of positive integers without repeating numbers between a given range Low to High. The first method is a brute force method which iterates over all numbers in the range and checks if they contain duplicate numbers. In the second method we calculate the required count using prefix array and in the last method we use the memory concept from dynamic programming to obtain the required result.
Problem Statement: Given two numbers, from low to high, we have to find the count of all numbers between low and high such that the number does not contain any repeated digits.
method 1
This is the brute force method, we just iterate through all the numbers from low to high and check if they contain any duplicate numbers. This is the simplest solution to our problem.
Example
The same code solution is given below:
#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
Method 2
In this approach we will use a prefix array to store the count of integers without duplicate numbers up to the index "iterator".
The steps involved in this method are:
Define a function to check if a number has duplicate digits.
Initialize the prefix array with zeros. The prefix array will store the number of significant digits up to the given index "iterator".
Traverse each number from low to high, checking if there are duplicate numbers. If there are no duplicate numbers, add 1 to the prefix array at the corresponding index.
Calculate the prefix sum of the prefix array. The prefix sum will give you the total number of significant digits in the range.
Return the prefix sum.
Example
The code for this method is given below -
#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
Time complexity - O(nlogn), where n is (high - low).
Space complexity - O(n)
Method 3 Dynamic programming method
In this approach, we decompose the problem into sub-problems and store the results of the sub-problems in a memory table
The program counts the total number of significant digits in a given range, i.e. numbers without repeated digits. It uses a dynamic programming approach where the function dp("iterator",used) returns the number of significant digits that can be formed starting from position "iterator" and in the number "used".
We use a memtable to store the results of the dp function and iterate over the range of numbers to call the dp function for each number. The sum of the results of the dp function for all starting "iterators" is the total number of significant digits in the range.
Example
#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
Conclusion - In this code, we have discussed three ways to count the total number of numbers in the range from low to high without duplicates.
The above is the detailed content of The total number of numbers in a range without duplicates. For more information, please follow other related articles on the PHP Chinese website!

C isnotdying;it'sevolving.1)C remainsrelevantduetoitsversatilityandefficiencyinperformance-criticalapplications.2)Thelanguageiscontinuouslyupdated,withC 20introducingfeatureslikemodulesandcoroutinestoimproveusabilityandperformance.3)Despitechallen

C is widely used and important in the modern world. 1) In game development, C is widely used for its high performance and polymorphism, such as UnrealEngine and Unity. 2) In financial trading systems, C's low latency and high throughput make it the first choice, suitable for high-frequency trading and real-time data analysis.

There are four commonly used XML libraries in C: TinyXML-2, PugiXML, Xerces-C, and RapidXML. 1.TinyXML-2 is suitable for environments with limited resources, lightweight but limited functions. 2. PugiXML is fast and supports XPath query, suitable for complex XML structures. 3.Xerces-C is powerful, supports DOM and SAX resolution, and is suitable for complex processing. 4. RapidXML focuses on performance and parses extremely fast, but does not support XPath queries.

C interacts with XML through third-party libraries (such as TinyXML, Pugixml, Xerces-C). 1) Use the library to parse XML files and convert them into C-processable data structures. 2) When generating XML, convert the C data structure to XML format. 3) In practical applications, XML is often used for configuration files and data exchange to improve development efficiency.

The main differences between C# and C are syntax, performance and application scenarios. 1) The C# syntax is more concise, supports garbage collection, and is suitable for .NET framework development. 2) C has higher performance and requires manual memory management, which is often used in system programming and game development.

The history and evolution of C# and C are unique, and the future prospects are also different. 1.C was invented by BjarneStroustrup in 1983 to introduce object-oriented programming into the C language. Its evolution process includes multiple standardizations, such as C 11 introducing auto keywords and lambda expressions, C 20 introducing concepts and coroutines, and will focus on performance and system-level programming in the future. 2.C# was released by Microsoft in 2000. Combining the advantages of C and Java, its evolution focuses on simplicity and productivity. For example, C#2.0 introduced generics and C#5.0 introduced asynchronous programming, which will focus on developers' productivity and cloud computing in the future.

There are significant differences in the learning curves of C# and C and developer experience. 1) The learning curve of C# is relatively flat and is suitable for rapid development and enterprise-level applications. 2) The learning curve of C is steep and is suitable for high-performance and low-level control scenarios.

There are significant differences in how C# and C implement and features in object-oriented programming (OOP). 1) The class definition and syntax of C# are more concise and support advanced features such as LINQ. 2) C provides finer granular control, suitable for system programming and high performance needs. Both have their own advantages, and the choice should be based on the specific application scenario.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

MantisBT
Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

SecLists
SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.

Atom editor mac version download
The most popular open source editor

EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function

SublimeText3 Mac version
God-level code editing software (SublimeText3)
