Rightmost Repeated Lottery Digit
National Olympiad — Municipal round (2012 season)
Submission name: lottery.cpp
Problem summary
Print the rightmost digit whose value occurs at least twice in the given number. If every digit is different, print No.
Input
One positive integer n.
Output
The rightmost repeated digit, or the exact word No.
Constraints
9 < n < 2,000,000,000.
Worked example
Input and output for the worked example discussed below.
Input
676678
Output
7
Solution analysis
- A digit’s eligibility depends on its total frequency, while the answer depends on position. First count all ten digit frequencies, then scan the number from right to left.
- The first position encountered whose digit frequency is at least two is the required answer. A two-pass solution makes the distinction between repeated value and rightmost position explicit.
- In 676678, the values 6 and 7 both repeat. The last 8 is unique, while the next digit to its left is 7 and occurs twice. Therefore print 7, even though 6 appears more often. For 2345 no digit qualifies, so print No.
Why it works
Frequency counting marks exactly the digits occurring more than once. Reverse scanning examines positions from rightmost to leftmost, so the first eligible position is exactly the rightmost repeated digit. If there is none, no repeated value exists.
Watch out. Do not choose the most frequent digit or the numerically largest repeated digit. Capitalization of No matters. The repeated digit may be zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
string number;
cin>>number;
int frequency[10]={};
for(char digit:number){
frequency[digit-'0']++;
}
for(int index=int(number.size())-1;index>=0;index--){
// The first eligible position from the right is the answer.
if(frequency[number[index]-'0']>1){
cout<<number[index]<<'\n';
return 0;
}
}
cout<<"No\n";
}