sauravsahu02
BAN USERTaking carry over into consideration:
public static void main(String[] args) {
int []arr = new int[] {1, 4, 4, 2, 1, 2, 3, 3, 2};
int maxV = Arrays.stream(arr).max().getAsInt();
Set<Integer> values = Arrays.stream(arr).boxed().collect(Collectors.toSet());
Map<Integer, Integer> valueToCountMap = new HashMap<>();
boolean []valueFound = new boolean[maxV+1];
int discrepencies = values.size();
int numOfGroupsOfAll = 0;
for (int v : arr) {
if (valueFound[v] == false) {
discrepencies--;
valueFound[v] = true;
}
else {
// in current group, this value is already found.
if (valueToCountMap.putIfAbsent(v, 1) != null) {
valueToCountMap.compute(v, (key, val)->val+1);
}
}
// Adjust Discrepancies Using CarryOver
if (valueToCountMap.size() >= discrepencies) {
for (int value : values) {
if (valueFound[value] == false && valueToCountMap.containsKey(value)) {
System.out.println("Value carried " + value);
discrepencies--;
valueFound[value] = true;
valueToCountMap.compute(value, (key, val)-> val-1);
if (valueToCountMap.get(value) == 0) valueToCountMap.remove(value);
}
}
}
if (discrepencies == 0) {
numOfGroupsOfAll++;
discrepencies = values.size();
resetFlags(valueFound, values);
}
}
System.out.println(numOfGroupsOfAll+1);
}
public static void resetFlags(boolean[] valuesFound, Set<Integer> values) {
for (int val : values) {
valuesFound[val] = false;
}
}
The best answer. space complexity wise.
- sauravsahu02 September 11, 2020Doing this `from[i] = to[i];` is based on wrong logic. Consider an example :
jake -> bake -> bike -> pike. According to you code, the first character of "from" string must not be changed to something other than 'p' which is the first character of "to" string.
Handles zeroes. Considers '01' as invalid candidate number i.e. a number either must start with a non-zero digit or be equal to a zero.
public class MinSumOfTwoFormedNum {
public static void main(String[] args) {
int []digits = new int[] {2, 7, 9, 8, 1};
int expectedAns = 129+78; // (= 207)
Assert.assertEquals(expectedAns, minSum(digits));
digits = new int[] {1, 0, 0, 0, 0};
expectedAns = 1000+0; // (= 1000)
Assert.assertEquals(expectedAns, minSum(digits));
digits = new int[] {1, 0, 0, 1, 0};
expectedAns = 100+10; // (= 110)
digits = new int[] {1, 0, 0, 1, 3, 0};
expectedAns = 100+103; // (= 203)
Assert.assertEquals(expectedAns, minSum(digits));
System.out.println("All good!");
}
private static int minSum(int[] digits) {
int sum = 0;
countSort(digits);
int nonZeroDigits = digits.length;
int zeroDigits = 0;
while(digits[zeroDigits] == 0) {
nonZeroDigits--;
zeroDigits++;
}
if (nonZeroDigits == 0) return 0;
if (nonZeroDigits == 1) return (int) (digits[digits.length-1]*Math.pow(10, zeroDigits-1));
if (zeroDigits >= 1) {
digits[0] = digits[zeroDigits];
digits[zeroDigits] = 0;
}
if (zeroDigits >= 2) {
digits[1] = digits[zeroDigits+1];
digits[zeroDigits+1] = 0;
}
long factor = 1;
for (int i = digits.length-1; i >= 0;) {
sum += factor*digits[i--];
if (i >= 0) sum += factor*digits[i--];
factor *= 10;
}
return sum;
}
private static void countSort(int[] digits) {
int counts[] = new int[10];
for (int i = 0; i < digits.length; i++) {
counts[digits[i]]++;
}
int idx = 0;
for (int i = 0; i < counts.length; i++) {
while(counts[i]-- > 0) {
digits[idx++] = i;
}
}
}
}
O(n) time complexity. Tested code.:
- sauravsahu02 September 18, 2020