fork(11) download
copy 
  1. /* =========================================================
  2.  * Project Euler, Problem #52
  3.  *
  4.  * It can be seen that the number, 125874, and its double, 251748, contain exactly
  5.  * the same digits, but in a different order.
  6.  *
  7.  * Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain
  8.  * the same digits.
  9.  *
  10.  * Solution by: migf1
  11.  * =========================================================
  12.  */
  13. #include <stdio.h>
  14.  
  15. #define MAXDIGS		10+1				// max allowed digits in a num
  16. #define NMULS		5				// # of consecutive multiples
  17. 							// (5 means 2x, 3x, 4x, 5x, 6x)
  18.  
  19. typedef struct mul {					// structure for a multiple
  20. 	unsigned long val;				// numeric value
  21. 	char sval[ MAXDIGS ];				// converted to c-string
  22. }Mul;
  23.  
  24. // ---------------------------------------------------------------------------------
  25. // Function: s_isanagram
  26. // 	Return TRUE if c-string s is an angaram of c-string t, FALSE otherwise
  27. //
  28. int s_isanagram(const char *s, const char *t)
  29. {
  30. 	int val, hgram[256] = {0};			// init histogram for the ASCII table
  31. 	const char *ps=s, *pt=t;			// temp char pointers to s & t
  32.  
  33. 	if ( !s || !t )					// early exit
  34. 		return 0;
  35.  
  36. 	for (; *s || *t; ) {				// update histogram
  37. 		if ( *s )				// ...
  38. 			hgram[(int)(*s++)]++;		// ... +1 for every char in s
  39. 		if ( *t )				// ...
  40. 			hgram[(int)(*t++)]--;		// ... -1 for every char in t
  41. 	}
  42. 							// check in histogram for
  43. 	while( *ps && *pt++ && !(val=hgram[(int)(*ps++)]) )	// 1st non-zero mapped val
  44. 		;					// of all chars in s
  45. 	return val || *pt ? 0 : 1;			// val || *pt != 0 ? FALSE : TRUE
  46.  
  47. }
  48. // ---------------------------------------------------------------------------------
  49. // Function: set_muls
  50. // 	Put NMULS consecutive multiples of n into the muls array, starting from 2x.
  51. // 	Return FALSE if the numerical value of a multiple consists of more than MAXDIGS-1
  52. // 	digits, so it cannot get stored into its c-string counterpart (sval).
  53. //
  54. int set_muls( unsigned long n, Mul muls[] )
  55. {
  56. 	register int i=2, nchars;
  57.  
  58. 	for (i=2; i < NMULS+2; i++)
  59. 	{
  60. 		muls[i-2].val = i * n;				// numerical value
  61. 		nchars = snprintf(				// converted to c-string
  62. 				muls[i-2].sval, MAXDIGS, "%lu", muls[i-2].val );
  63. 		if (nchars >= MAXDIGS)
  64. 			return 0;
  65. 	}
  66.  
  67. 	return 1;
  68. }
  69. // ---------------------------------------------------------------------------------
  70. // Function: muls_anagrams:
  71. // 	Return TRUE if all multiples inside muls are anagrams of each other,
  72. //	FALSE otherwise
  73. //
  74. int muls_anagrams( Mul muls[] )
  75. {
  76. 	int is_anagram = 1;					// TRUE
  77. 	register int i;
  78. 	for (i=1; is_anagram && i < NMULS; i++) {
  79. 		is_anagram = is_anagram && s_isanagram( muls[0].sval, muls[i].sval );
  80. 	}
  81.  
  82. 	return is_anagram;
  83. }
  84. // ---------------------------------------------------------------------------------
  85. void print_muls( Mul muls[] )
  86. {
  87. 	register int i;
  88.  
  89. 	printf("muls of %lu: \n", muls[0].val/2 );
  90. 	for (i=0; i < NMULS; i++)
  91. 		printf("\t%dx = %lu\n", i+2, muls[i].val );
  92. 	putchar('\n');
  93.  
  94. 	return;
  95. }
  96. // ---------------------------------------------------------------------------------
  97. int main( void )
  98. {
  99. 	unsigned long i;
  100. 	Mul muls[ NMULS ] = {{0,NULL}};			// important initialization to 0s
  101.  
  102. 	int are_anagrams = 0;				// bool to control the basic loop
  103. 	for (i=1; !are_anagrams; i++)			// our basic loop
  104. 	{
  105. 		if ( !set_muls(i, muls ) ) {		// produce NMULS multiples of i
  106. 			printf("*** error: a multiple of %lu too big to have an sval", i);
  107. 			return 1;
  108. 		}
  109. 		are_anagrams = muls_anagrams( muls );	// are all multiples anagrams ?
  110. 	}
  111. //	printf("%lu\n", i-1);
  112. 	print_muls( muls );
  113.  
  114. 	return 0;
  115. }
  116.  
stdin
copy 
Standard input is empty
compilation info 
prog.c: In function ‘main’:
prog.c:100: warning: missing braces around initializer
prog.c:100: warning: (near initialization for ‘muls[0].sval’)
prog.c:100: warning: initialization makes integer from pointer without a cast
stdout
copy 
muls of 142857: 
	2x = 285714
	3x = 428571
	4x = 571428
	5x = 714285
	6x = 857142
https://ideone.com/Zmum3
language:
C (gcc 8.3)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!