how to sort number that in integer (int)

Question

1.00/5 (2 votes)

See more:

how to sort number that in integer (int) without the use of array and string????
for example

Java

int x=7324

sort of (x) number is : 2347

Posted 7-Apr-15 9:26am

jehat hassan

Add a Solution

Comments

ZurdoDev 7-Apr-15 15:40pm

Wouldn't you have to break it out into characters? How else would you do it?

Sergey Alexandrovich Kryukov 7-Apr-15 15:49pm

No, the trick is to use only numeric container and no arrays. It needs thinking.
—SA

Sergey Alexandrovich Kryukov 7-Apr-15 16:03pm

Pretty interesting test problem. I found a quick solution, but I'm afraid it's not elegant enough. It is actually trivial. Please see Solution 1.
—SA

Maciej Los 7-Apr-15 15:40pm

I do not understand your "sort criteria"...

Sergey Alexandrovich Kryukov 7-Apr-15 15:51pm

Most likely, minimal digit goes on left, maximum on right, value of each digit monotonously grows left to right. This is a tricky (highly artificial) problem aimed to check up person's inventiveness and thinking. (So, it's good to solve it not telling our inquirer the answer, to prevent unfair competition :-)
—SA

Sergey Alexandrovich Kryukov 7-Apr-15 15:56pm

One solution is trivial: use some other int object as a temporary container representing "array of digits". Say, int takes 32 bytes. But maximum 32-bit int takes only 10 decimal digit. So one can use the integer as an array of 32 bytes (even though a decimal integer needs only 4 bits).

I decided to post a formal answer. Please see Solution 1.

—SA

Maciej Los 7-Apr-15 16:07pm

I know that, Sergey, but OP wrote: "without the use of array or string". This part is no underandable to me ;)
Happy After-Easter ;)

Sergey Alexandrovich Kryukov 7-Apr-15 16:18pm

I think it's more or less clear. In case of C# (one of the languages allowed in the formulation): System.String is not used and '[]' is not used.
The solution is quite possible.
The new limitation ("only % and /") is really not certain. Say, can we use very important < or not?
—SA

Sergey Alexandrovich Kryukov 7-Apr-15 16:19pm

Happy After-Easter! Too bad we could not contact; I was busy. That day we even did not celebrate. :-(
We modestly had pizza with wine, did not even do our traditional egg fight.
—SA

Maciej Los 7-Apr-15 16:25pm

In keeping with tradition i spend my time with family.

Sergey Alexandrovich Kryukov 7-Apr-15 16:28pm

That's great. We still have a chance to get in synch with Orthodox tradition... :-)
But more usually we celebrated it in Catholic/Protestant calendar.
—SA

jehat hassan 7-Apr-15 16:02pm

Only note
Using only% and /

Sergey Alexandrovich Kryukov 7-Apr-15 16:06pm

Not fair! This is way too essential limitation. I already spent time on thinking at the problem. You should have specified everything in first place.
This is bad; no more solutions for you, even if I solve it; all next steps are on you. Thank you for sharing.
—SA

5 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Answer 1 · 2015-04-07T10:02:00

So far, I came up with only some trivial solution: use one more intermediate int object. This is not prohibited by the problems formulation. You can use it to represent a kind of "array of digits". You have only 10 digit, so a digit object needs only 4 bits (half-byte) to represent. But maximum, say, 32-bit int value takes only 10 decimal digits, so you can even dedicate whole byte to represent one decimal digit.

Then all you need is simple bit arithmetic to extract, set and move bytes withing such integer object, and any suitable sorting algorithm.

I'm afraid this is not the most elegant solution, but there is what I was able to create immediately after my first glance at the problem. I already told you too much so I'm afraid of giving you a benefit in possible unfair competition. So, not source code. Anyone can solve the problem now. Anyway, you did not even specify the language…

[DISCLAIMER]

When I was writing this solution I did not know anything about the condition of using only % and / operators. Inquirer added it in comment later.

—SA

User 59241 · Answer 2 · 2015-04-11T03:03:00

This will do it. It will handle multiple occurrences of digits but not 0 of course (at present 0 is ignored). If required 0 would have to be placed after 9. Easy enough to do.

C++

#include <stdio.h>

int main () {
	const __int64 input = 456120;
	__int64 output = 0, temp1;
	int len = 0;

	// Calculate the number of digits.
	temp1 = input;
	while(temp1 > 0)
	{
		temp1/=10;
		len++;
	}

	// Work through the digits 0-9.
	for (int i=0; i <= 9; i++)
	{
		// Will catch multiple occurences.
		for (temp1 = input; temp1 > 0; temp1 /= 10)
		{
			if (temp1%10 == i)
			{
				// Put the digit in its correct position in output integer.
				__int64 temp2 = i;
				--len;

				for(int count = len; count > 0; count--)
					temp2*=10;

				output += temp2;
			}
		}
	}

	printf("%d\n", output);
}

Maciej Los · Answer 3 · 2015-04-07T10:03:00

Solution 2

Preliminary note: Please, read my comment to the question. You did not provide enough information. Later additions and amendments have been ignored.

~~No, it's impossible to "change the order of digits inside the number"! So, "conversion" from 7324 to 2347 whithout using array of chars (string) or integers is not possible!~~ - I have to "strike through" this part of my answer, because of Sergey's comments. Yes, theoretically it's possible to moves digits in ascending order - see Solution 1.

The best way is to convert 7324 value to string (char array) or integer array then loop through the array of chars/integers and change the sort order.
See:
http://www.csharp-examples.net/sort-array/[^]
Visualization and comparison of sorting algorithms in C#[^]
Sorting Algorithms Codes in C#.NET[^]

Another way is to use Array.Sort[^] method.

Or... using Linq:

C#

int x=7324;
var sortOfX = x.ToString().OrderBy(c=>Convert.ToInt32(c)).Select(a=>a.ToString()).Aggregate((a,b) => string.Concat(a, b));
//returns: 2347

Posted 7-Apr-15 10:03am

Maciej Los

Updated 7-Apr-15 11:22am

v3

Comments

Sergey Alexandrovich Kryukov 7-Apr-15 16:09pm

The claim "it is impossible" is not trivial. Can you formally prove it? If not, you should not make such claims.

I already provided a solution (not a very good one) which disproves your claim. My solution does not take into account the last condition (only % and /), but you claimed that the solution cannot be found even without this limitation, so my solution still proves you're wrong. Admit it.

Sorry,
—SA

Maciej Los 7-Apr-15 16:16pm

Prove it? I don't need to prove it. Number is a number. The only way to "sort digits inside number" is to treat it as an array of integers or chars. I saw your answer, Sergey. And you proved my claim (statement).

Sergey Alexandrovich Kryukov 7-Apr-15 16:27pm

You would not need it if it wasn't a pure algorithmic problem. If it was a practical problem, we would never even tried to solve it, we would just use the array.
But for such a theoretical problem, the only acceptable rule of the game is to provide mathematically strict proves of all claims.
My solution, formally, using no string and no array. I used the expression "array of digits" in quotation, to express that this is a figurative expression. Formally, this is not an array at all, '[]' won't be used anywhere. Even char won't be used, not only strings. So, it does not prove your claim, it proves the opposite: solution without arrays and strings is quite possible. It is proven by reduction to known facts though; if you think the formulation of the prove lacks some detail, I can provide them. It's only formulation of the proof, not the proof itself. Yes, it's possible.
—SA

Maciej Los 7-Apr-15 17:15pm

I think it's strictly academic discussion. As i mentioned in comment to the question: i do not understand OP's "sort criteria".

Sergey Alexandrovich Kryukov 7-Apr-15 17:32pm

There is no academic and non-academic discussions, because the truth is only one. You see, the question itself is "poorly academic", that's why. The whole topic would not make any practical sense. It's pure algorithmic exercises, and it would not make any sense without those proofs. We can only discuss it "academically", or not discuss at all. Oh yes, sorting criteria were not formulated, but I assumed it's growing values per digit, left to right. This is the simplest assumption which could be made.
—SA

Maciej Los 7-Apr-15 16:22pm

By the way: i do not deserved for 1 ;(

jehat hassan 7-Apr-15 16:17pm

There is a way that uses roughly like this:

int a= 7314,index=0,t=7314,num=0;
for (int i = 0;t>0; i++)
{
t/=10;
index++;
}
for (int i = 0; i < 10; i++)
{
int x=a%10;
a/=10;
int y=a%10;
if (x<y) {="" int="" temp="x;" a="" =10;="" a*="100;" a+="y;" }="" else=""  ="" <="" pre="">
But this is not true code, but I almost have thus resolved

Sergey Alexandrovich Kryukov 7-Apr-15 17:37pm

So, your condition on using "only % and /" is not met. There is ≶, ++ >... You need to formulate all conditions accurately.
Yes, this is the way to extract digits, but not enough to solve the problem. I say, my answer gives the idea on how to do it. You still need comparisons and ++ in the loop...
—SA

Maciej Los 7-Apr-15 17:24pm

I'd like to know the down-voter's opinion. I'd have a chance to improve my answer.

Sergey Alexandrovich Kryukov 7-Apr-15 17:34pm

Maciej, I explained it immediately at the moment of down-voting: the claim which is not true. You claimed it's impossible, but I think I proved it possible.
Sorry, but this is my conclusion.
—SA

Maciej Los 7-Apr-15 17:44pm

Sergey, i know your opinion. As you can see, i updated my answer. Above comment has been posted "just in case of further down-votes".

Sergey Alexandrovich Kryukov 7-Apr-15 17:51pm

All right, we agree, so I up-voted it. I don't know what do you mean by "theoretically possible". This is obviously possible: the proof (or its skeleton) is constructive; it tells how to achieve this algorithm. And yes, inquirer's condition to use only % and / might be incorrect. It's just a hint, a way to extract decimal digits. But I don't believe it's possible to do it without comparison and ++ or --. (But I don't claim it; what if that is possible?) Generally, such condition as permission to use some operators are not strict, because an operator are just of form of the syntax for some operation. Strict formulation, language-independent, could include such boring stuff as defining the set of allowed operations, etc. The problem was pretty good in its first formulation, no arrays, no strings...
—SA

Maciej Los 7-Apr-15 17:58pm

It's getting late for me (23:54). I'm not pretty good with words as you're, so let "theoretically possible" is equal to "obviously possible". Cheers, Maciej.

Sergey Alexandrovich Kryukov 7-Apr-15 18:32pm

:-)
Good night.
Cheers,
—SA

OriginalGriff · Answer 4 · 2015-04-07T10:04:00

This is your homework, so we won't give you code.
But... I can understand you not knowing quite where to go here.
So a couple of hints:
1) Have you ever heard of Binary Coded Decimal? Look it up...
2) You can extracted individual hex digits (or groups of for bits) with AND, OR, and NOT operations.
3) You can move mask values with SHIFT operations.
4) int values are 32 bit, you also have long values, which are 64 bit if you need a little extra room.

Sugar Richard · Answer 5 · 2015-04-10T04:10:00

A little bit fuzzy on the exact spec. Hope this helps.

C++

uint32_t merge_digit(uint32_t hi, uint32_t lo, uint32_t base)
{
	uint32_t r = 0;
	uint32_t m = 1;

	while ( lo != 0 && hi != 0 ) {
	   uint32_t p1 = lo % base * m;
	   uint32_t p2 = hi % base * m;
	   m *= base;

	   if (p1 < p2) {
	      r += p2; hi /= base;
	   } else {
	      r += p1; lo /= base;
	   }
	}
	return r + (lo + hi) * m;
}

C++

uint32_t sort_digit(uint32_t x, uint32_t base)
{
	uint64_t b;
	/* loop until b^2 will overflow. */
	for ( b = base; b <= UINT32_MAX; b *= b ) {
	   uint32_t r = 0;
	   uint32_t m = 1;
	   while ( x != 0 ) {
	      r += merge_digit(x/b%b, x%b, base) * m;
	      m *= b*b;
	      x /= b*b;
	   }
	   x = r;
	}
	return x;
}

Edit: Alternate solution (after viewing pwasser's answer).

C++

uint32_t sort_digit(uint32_t x, uint32_t base)
{
	uint32_t result = 0;
	uint32_t i;
	for ( i = 1; i < base; i++ ) {
	   uint32_t temp;
	   for ( temp = x; temp != 0; temp /= base )
	      if (temp%base == i)
	         result = result * base + i;
	}
	return result;
}

Edit: Test.

C++

int main(int argc, char* argv[])
{
	int x = (argc >= 2) ? strtol(argv[1], (char**) 0, 0) : 7324;
	printf("before (dec): %u\n", x);
	printf("after  (dec): %u\n", sort_digit(x, 10));
	printf("before (oct): %o\n", x);
	printf("after  (oct): %o\n", sort_digit(x, 8));
	printf("before (hex): %X\n", x);
	printf("after  (hex): %X\n", sort_digit(x, 16));
	return 0;
}

how to sort number that in integer (int)

5 solutions

Solution 1

Solution 6

Solution 2

Solution 3

Solution 5

Add your solution here

Preview 0