Welcome to Subscribe On Youtube

3717. Minimum Operations to Make the Array Beautiful 🔒

Description

You are given an integer array nums.

An array is called beautiful if for every index i > 0, the value at nums[i] is divisible by nums[i - 1].

In one operation, you may increment any element nums[i] (with i > 0) by 1.

Return the minimum number of operations required to make the array beautiful.

 

Example 1:

Input: nums = [3,7,9]

Output: 2

Explanation:

Applying the operation twice on nums[1] makes the array beautiful: [3,9,9]

Example 2:

Input: nums = [1,1,1]

Output: 0

Explanation:

The given array is already beautiful.

Example 3:

Input: nums = [4]

Output: 0

Explanation:

The array has only one element, so it's already beautiful.

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 50​​​

Solutions

Solution 1

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public int minOperations(int[] nums) {
          Map<Integer, Integer> f = new HashMap<>();
          f.put(nums[0], 0);
  
          for (int i = 1; i < nums.length; i++) {
              int x = nums[i];
              Map<Integer, Integer> g = new HashMap<>();
  
              for (var entry : f.entrySet()) {
                  int pre = entry.getKey();
                  int s = entry.getValue();
  
                  int cur = (x + pre - 1) / pre * pre;
                  while (cur <= 100) {
                      int val = s + (cur - x);
                      if (!g.containsKey(cur) || g.get(cur) > val) {
                          g.put(cur, val);
                      }
                      cur += pre;
                  }
              }
              f = g;
          }
  
          int ans = Integer.MAX_VALUE;
          for (int v : f.values()) {
              ans = Math.min(ans, v);
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      int minOperations(vector<int>& nums) {
          unordered_map<int, int> f;
          f[nums[0]] = 0;
  
          for (int i = 1; i < nums.size(); i++) {
              int x = nums[i];
              unordered_map<int, int> g;
              for (auto [pre, s] : f) {
                  int cur = (x + pre - 1) / pre * pre;
                  while (cur <= 100) {
                      int val = s + (cur - x);
                      auto jt = g.find(cur);
                      if (jt == g.end() || jt->second > val) {
                          g[cur] = val;
                      }
                      cur += pre;
                  }
              }
              f = move(g);
          }
  
          int ans = INT_MAX;
          for (auto& it : f) {
              ans = min(ans, it.second);
          }
          return ans;
      }
  };
  
  

• class Solution:
      def minOperations(self, nums: List[int]) -> int:
          f = {nums[0]: 0}
          for x in nums[1:]:
              g = {}
              for pre, s in f.items():
                  cur = (x + pre - 1) // pre * pre
                  while cur <= 100:
                      if cur not in g or g[cur] > s + cur - x:
                          g[cur] = s + cur - x
                      cur += pre
              f = g
          return min(f.values())
  
  

• func minOperations(nums []int) int {
  	f := map[int]int{nums[0]: 0}
  
  	for i := 1; i < len(nums); i++ {
  		x := nums[i]
  		g := make(map[int]int)
  		for pre, s := range f {
  			cur := (x + pre - 1) / pre * pre
  			for cur <= 100 {
  				val := s + (cur - x)
  				if old, ok := g[cur]; !ok || old > val {
  					g[cur] = val
  				}
  				cur += pre
  			}
  		}
  		f = g
  	}
  
  	ans := math.MaxInt32
  	for _, v := range f {
  		ans = min(ans, v)
  	}
  	return ans
  }
  
  

• function minOperations(nums: number[]): number {
      let f = new Map<number, number>();
      f.set(nums[0], 0);
  
      for (let i = 1; i < nums.length; i++) {
          const x = nums[i];
          const g = new Map<number, number>();
  
          for (const [pre, s] of f.entries()) {
              let cur = Math.floor((x + pre - 1) / pre) * pre;
              while (cur <= 100) {
                  const val = s + (cur - x);
                  const old = g.get(cur);
                  if (old === undefined || old > val) {
                      g.set(cur, val);
                  }
                  cur += pre;
              }
          }
          f = g;
      }
  
      return Math.min(...f.values());
  }
  
  

• use std::collections::HashMap;
  
  impl Solution {
      pub fn min_operations(nums: Vec<i32>) -> i32 {
          let mut f: HashMap<i32, i32> = HashMap::new();
          f.insert(nums[0], 0);
  
          for i in 1..nums.len() {
              let x = nums[i];
              let mut g: HashMap<i32, i32> = HashMap::new();
  
              for (&pre, &s) in f.iter() {
                  let mut cur = ((x + pre - 1) / pre) * pre;
                  while cur <= 100 {
                      let val = s + (cur - x);
                      match g.get(&cur) {
                          None => {
                              g.insert(cur, val);
                          }
                          Some(&old) => {
                              if val < old {
                                  g.insert(cur, val);
                              }
                          }
                      }
                      cur += pre;
                  }
              }
              f = g;
          }
  
          *f.values().min().unwrap()
      }
  }
  
  

All Problems

All Solutions