Skip to content

Instantly share code, notes, and snippets.

@AmalJossy
Last active October 10, 2020 15:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save AmalJossy/a8e8bdadbc67bff14f9bb53a4424b25c to your computer and use it in GitHub Desktop.
Save AmalJossy/a8e8bdadbc67bff14f9bb53a4424b25c to your computer and use it in GitHub Desktop.
Size of largest subset of numbers that share a digit directly OR INDIRECTLY
#include <iostream>
using namespace std;
int counters[10];
int* ref[10];
void init(){
for(int i=0;i<10;i++){
counters[i]=0;
ref[i]=&counters[i];
}
}
void syncCounterRefs(int* keyRef, int* relatedRef){
for(int i=0;i<10;i++){
if(ref[i]==relatedRef){
ref[i]=keyRef;
}
}
}
void processNumber(int num){
int keyDigit=-1;
while(num>0){
int digit=num%10;
num=num/10;
if(keyDigit==-1){
keyDigit=digit;
*ref[keyDigit]+=1;
}
if(ref[digit]!=ref[keyDigit]){
*ref[keyDigit]+=*ref[digit];
syncCounterRefs(ref[keyDigit],ref[digit]);
}
}
}
int main() {
init();
int inputs[]={346,56734,432,10,9,64,354,46,46,235,57,765,35,38,7,45,70};
int inputSize = sizeof(inputs)/sizeof(inputs[0]);
for(int i=0;i<inputSize;i++){
processNumber(inputs[i]);
}
int max=counters[0];
for(int j=0;j<10;j++){
if(counters[j]>max){
max=counters[j];
}
}
cout<<"MAX="<<max;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment