an array problem (plz, help out) ......
hi,
I have a range of number between 1-101 ... the second thing i have is an array of capacity 100 (i.e on less than range i have)...
The problem is : if i fill array with no. from the range randomly without any repeatition..... how can i find the left integer in range
plz, don't iterate through the array or any other recursive looping stuff.
[377 byte] By [
yeshendra] at [2007-11-11 8:48:42]

# 2 Re: an array problem (plz, help out) ......
thanx for your concern ... here is the description of problem
The sequence is an example =>
STEP:1
List of nos : {1,2,3,.....,101} ; arr[] = new arr[100]
STEP:2
List of nos : {1,2,3,4,6,7...,101} ; arr[0]=5
STEP:3
List of nos : {1,2,3,.,72,74..,101} ; arr[1]=73
STEP: n-1
List of nos : {88,20} ; arr[98]= 50
STEP: n
List of nos : {88} ; arr[99]= 20
Now Given is i) Range{1-101}
ii) arr[] with nos populated as above (i.e randomly)
what is the best way to find out the no. missing in the array with minimum no. of steps required and effecient toooo......
what do you mean by that?
you fill the array with random non repreating nos. that's clear.
are the numbers somehow sorted, or do you iterate through the array and set any random number into the actual array place?
and what is the "left integer in range"? the smallest number in the array?
could you post your code to fill the array?
# 3 Re: an array problem (plz, help out) ......
ok, i understand, that you randomly put numbers from your list to an array.
this can be done through the following code
import java.util.Random;
public class Randomly {
/**
* @param args
*/
public static void main(String[] args) {
// initialize list
int [] listOfNos = new int[101];
int [] unusedNoPositionsInList = new int[101];
for (int i=0; i<=100; i++){
listOfNos[i] = i+1;
unusedNoPositionsInList[i] = i;
}
// System.out.println("list of nos: "+toString(listOfNos));
// prepare random selector
Random RND = new Random(System.currentTimeMillis());
int [] arr = new int[100];
int noPositionInUnusedNoPositionsInList;
int nextFreePositionInArr = 0;
int lastUnusedNoPosition;
while (nextFreePositionInArr<100){
lastUnusedNoPosition = 100-nextFreePositionInArr;
System.out.println("nextFreePositionInArr: "+nextFreePositionInArr);
System.out.println("lastUnusedNoPosition: "+(lastUnusedNoPosition));
System.out.println("list of nos: "+toString(listOfNos, unusedNoPositionsInList, lastUnusedNoPosition));
System.out.println("unusedNoPositionsInList: "+toString(unusedNoPositionsInList, lastUnusedNoPosition));
noPositionInUnusedNoPositionsInList = RND.nextInt(lastUnusedNoPosition);
System.out.println("noPositionInUnusedNoPositionsInList(rnd): "+noPositionInUnusedNoPositionsInList);
arr[nextFreePositionInArr] = listOfNos[unusedNoPositionsInList[noPositionInUnusedNoPositionsInList]];
System.out.println("no: "+arr[nextFreePositionInArr]);
if (unusedNoPositionsInList[noPositionInUnusedNoPositionsInList]!=lastUnusedNoPosition){
System.out.println("moving index");
unusedNoPositionsInList[noPositionInUnusedNoPositionsInList]=unusedNoPositionsInList[lastUnusedNoPosition];
System.out.println("unusedNoPositionsInList: "+toString(unusedNoPositionsInList, lastUnusedNoPosition));
}
nextFreePositionInArr++;
System.out.println("list of nos: "+toString(listOfNos, unusedNoPositionsInList, lastUnusedNoPosition-1));
System.out.println("arr: "+toString(arr, nextFreePositionInArr));
System.out.println("---");
}
System.out.println("finish");
System.out.println("list of nos: "+toString(listOfNos, unusedNoPositionsInList, 1));
System.out.println("unusedNoPositionsInList: "+toString(unusedNoPositionsInList, 1));
}
public static final String toString(int [] listOfNos, int [] unusedIndices, int len){
final StringBuffer sb = new StringBuffer(300);
for (int i=0; i<len; i++){
sb.append(listOfNos[unusedIndices[i]]);
if (i<len-1) sb.append(", ");
}
return sb.toString();
}
public static final String toString(int [] array){
return toString(array, array.length);
}
public static final String toString(int [] array, int len){
final StringBuffer sb = new StringBuffer(300);
int maxIndex = Math.min(len, array.length);
for (int i=0; i<maxIndex; i++){
sb.append(array[i]);
if (i<maxIndex-1) sb.append(", ");
}
return sb.toString();
}
}
but what i still dont understand is, what "no. missing in the array with minimum no. " means. can you show it in the example you provided?
by the way:
STEP: n-1
List of nos : {88,20} ; arr[98]= 50
should be
STEP: n-1
List of nos : {20,88} ; arr[98]= 50
# 5 Re: an array problem (plz, help out) ......
thanx, graviton & sjalle
by the way graviton here my code for the same:
import java.util.Random;
public class RandomNumbers {
public static void main(String args[]){
Random r = new Random(154785654);
int filled = 0;
int arr[] = new int[101];
int no=0;
for(;filled<100;
r = new Random(System.currentTimeMillis()*5)){
no = r.nextInt(101)+1;
filled += (arr[no-1]==0)?1:0;
arr[no-1] += ((arr[no-1]==0)?1:0);
}
// THE ISSUE:
for(int i=0;i<arr.length;i++) {
System.out.println("arr["+i+"]:"+arr[i]);
}
System.out.println("done");
}
}
Now the issue is after getting the 'arr' what is the best way to find out the missing number (beside checking for '0' in array), or is it the only way to find out the no
thanx
You must either check what is left in the list or what is missing in the array. If you store the array values at their index position offset one (e.g. a[n]=n+1), then the left value will stand out as a vacant slot (provided that you initialize the array w. say the minimum int value, Integer.MIN_VALUE). But...you will have to loop the array once to find it.