There are N
doors with a number on each door. You have a golden key(K
) and you can open with it only doors on which the numbers are magic and can be reduced to the number of the key (With key 7
you can open
doors on which the magic numbers can be reduced to 7). A number is magic if it can be reduce to a one digit number.
The method to reduce the number is the following: turn each digit of the number to the subtraction of the digit from the max digit
of the number. And repeat the process. For example: 1234
->3210
->123
->210
->12
->10
->1
.
Note that some numbers can't be reduced to a one digit number. For example: 1204
->3240
->1204
->3240
->1204
...
You have to find how many doors can be opened with the magic K
key and the max even number.
The input is N
(number of doors), K
(magic key) and numbers on each door.
The output is the max even number and the number of doors that can be opened with K
key.
7 ≤ N ≤ 10000
0 ≤ K ≤ 9
Each number on the doors is a 10-32800 number. There is at least one even number.
#include <stdio.h>
#include <stdlib.h>
int checkForZero( int number )
{
while( number )
{
if( number % 10 == 0 )
{
return 1;
}
number /= 10;
}
return 0;
}
int findMaxDigit( int len ,int number[len] )//returns max digit of the number
{
int digit = 0;
int i;
for( i = 0; i < len; i++ )
{
if( number[i] > digit )
{
digit = number[i];
}
}
return digit;
}
int length(int arg)
{
//returns number of digits of a number
return snprintf(NULL, 0, "%d", arg) - (arg < 0);
}
int poww(int a)//returns 10 ^ a
{
int c = 10, i;
for(i = 1; i < a; i++)
{
c *= 10;
}
return c / 10;
}
int main()
{
int N;//number of doors
scanf( "%d", &N );
int K;//magic key
scanf( "%d", &K );
int numberA[5] = {1};
int doorsToOpen = 0;//number of doors that can be opened with K key
int maxEvenNumber = 0;
int i;
for( i = 0; i < N; i++ )
{
int doorNumber;//number on the door
scanf( "%d", &doorNumber );
if( doorNumber > maxEvenNumber ) maxEvenNumber = doorNumber;
int numberLength = length( doorNumber );
//I assumed that every number that contains a `0` is no a magical number
//except the powers of 10
//100->11->0
int power = poww( numberLength );
//if the current number is not magical go to next door
if( checkForZero( doorNumber ) && ( doorNumber != power )) continue;
//put number in an array
int j;
for( j = numberLength - 1; j >= 0; j-- )
{
numberA[j] = doorNumber % 10;
doorNumber /= 10;
}
while( numberLength > 1 )//If the number is not a one digit number
{
int maxDigit = findMaxDigit( numberLength, numberA );
if( numberA[0] == 0 )//if the first digit of the number is 0 deletes it. [0][1][2] will turn into [1][2]
{
numberLength--;
for( j = 0; j < numberLength; j++ )
{
numberA[j] = numberA[j + 1];
}
}
//transform the number
for( j = 0; j < numberLength; j++ )
{
numberA[j] = maxDigit - numberA[j];
}
//create the number to check if it is equal to the initial number
doorNumber = 0;//I will work with this number because i have saved it
//save the transformed number from array to this variable
for( j = 0; j < numberLength; j++ )
{
doorNumber *= 10; doorNumber += numberA[j];
}
if( doorNumber == K )
{
doorsToOpen++;
}
}
}
printf("%d", maxEvenNumber);
printf("\n%d", doorsToOpen);
return 0;
}
My code is working fine, but I need a faster solution. Could you please help me giving me some tips on how to make a faster algorithm to this problem?